кстати я был не прав. в большинстве прямо компилирующихся языков под любой платформой sin(cos, tg, и так далее) будет превращаться в первую очередь в вызов библиотечной. ф., а та уже в свою очередь задействует сопроцессор. что явно больше времени доступа к массиву даже с предвычислением индекса. да.

объясните пожалуста. почему деление путем вычитания быстрее натурального деления?
вот код:

Код

public void TestS()  {    long ll=45000;    long ts = System.currentTimeMillis();    for(int i=0;i<1000000;i++)    {      for (; ll > 1; )      {        ll -= 5000;      }    }    long te = System.currentTimeMillis();        System.out.println("del by minus " + (te-ts) + " milliseconds");    ts = System.currentTimeMillis();    for(int i=0;i<1000000;i++)    {      ll/=5000;    }    te = System.currentTimeMillis();        System.out.println("del by del " + (te-ts) + " milliseconds");  }

вот результат:
del by minus 16 milliseconds
del by del 62 milliseconds

все-ж - от чего так происходит?
само деление - уже не вызов метода - это оператор, который вполне может быть выполнен на сопроцессоре, как в прочем и приведение типа.
Однако как сказад DomesticCat - так оно и получается, деление путем вычитания быстрее
Спасибо!
PS: что еще интересно - результат в ll для ll/=5000; всегда будет 0. ...


Это сообщение отредактировал(а) Sleepy_PIP - 27.11.2004, 19:18

Цитата(Sleepy_PIP @ 27.11.2004, 10:04)

del by minus 16 milliseconds del by del 62 milliseconds

Ну не настолько же быстрее
Просто у тебя ошибка: после первого прохода цикла

Код

for (; ll > 1; ) {        ll -= 5000; }

ll становится равным 0. Тогда все оставшиеся 999999 раз этот цикл пропускается. Во втором с,лучае ноль получается из-за того, что ты делишь 45000 на 5000 1000000 раз. После девятого деления ll становится равным 1, а 1/5000 дает 0, т.к. оба числа целые и выполняется целочисленное деление (остаток = 1, результат = 0) .
Я сделал так:

Код

public class Test1 { public static void main(String [] args)  {    long ll=45000;    long ts = System.currentTimeMillis();    for(int i=0;i<1000000;i++)    { ll=45000;      for (; ll > 1; )      {        ll -= 5000;      }    }    long te = System.currentTimeMillis();    System.out.println("del by minus " + (te-ts) + " milliseconds"); ts = System.currentTimeMillis();    for(int i=0;i<1000000;i++)    { ll=45000;      ll/=5000;    }    te = System.currentTimeMillis();    System.out.println("del by del " + (te-ts) + " milliseconds");  } }

и получил:

Цитата

del by minus 330 milliseconds del by del 320 milliseconds

то есть скорость приблизительно одинакова.

Спасибо. ошибку я проглядел .

а вот дельфевый код

Код

procedure TForm1.Button1Click(Sender: TObject); var i: longint; ll: longint; ds, de: TDateTime; dd: double; begin     ll:=45000;     ds:=now;     for i:=0 to 1000000000 do     begin       ll:=45000;       while ll>1 do          ll:=ll-5000;     end;     de:=Now;     ShowMessage(TimeToStr(ds-de));     ds:=now;     for i:=0 to 1000000000 do     begin          ll:=45000;          dd:=ll/5000;     end;     de:=Now;     ShowMessage(TimeToStr(ds-de)); end;

выполняется в более чем 10 раз быстрее для деления. Правда тут есть одна тонкость - результат деления засовывается в вещественную переменную ...

Это сообщение отредактировал(а) Sleepy_PIP - 27.11.2004, 20:27

Цитата(Sleepy_PIP @ 27.11.2004, 11:25)

выполняется в более чем 10 раз быстрее для деления. Правда тут есть одна тонкость - результат деления засовывается в вещественную переменную ...

Ну, Делфи я не знаю, так что сказать не могу ничего. Если изменить так в Java коде:

Код

ll=45000; double d = ll/5000;

то замедление незначительное: 330 мс против 390 мс.

сделал аналог дельфевому коду, с исправлением ошибок

Код

public void TestS()  {    long ll=45000;    double dd;    long ts = System.currentTimeMillis();    for(int i=0;i<1000000;i++)    {      ll=45000;            for (; ll > 1; )      {        ll -= 5000;      }    }    long te = System.currentTimeMillis();    System.out.println("del by minus " + (te-ts) + " milliseconds");    ts = System.currentTimeMillis();    ll=45000;    for(int i=0;i<1000000;i++)    {      ll=45000;      dd=ll/5000;    }    te = System.currentTimeMillis();    System.out.println("del by del " + (te-ts) + " milliseconds");  }

но результаты все равно я не понимаю:
del by minus 47 milliseconds
del by del 93 milliseconds
правда тут может влиять ll=45000; в цикле. неужели из-а этого?
нет, не из-а этого.
закоментаринивание в цикле ll=45000;
дает все равно:

del by minus 47 milliseconds

del by del 94 milliseconds

учусь! и еще на долго ...

Ну деление-то остается делением, оно все-таки медленнее К тому же тут ты используешь (неявно) еще один оператор - конвертации лонга в дабл :

Код

dd = ll/5000; эквивалентно: dd = (double) (ll / 5000);

а конвертация - медленная штука.

Это сообщение отредактировал(а) Domestic Cat - 27.11.2004, 20:46

Цитата(Domestic @ 27.11.2004, 20:40)

Ну деление-то остается делением, оно все-таки медленнее

сории, я еще не освоил дизасм (или как там в яве?) - не мог-бы ты привести во что выражается в байткоде вычитание и деление? случаем не в вызовы методов?
Сильно похоже что jvm действительно не использует сопроцессор вообще ... только догадки ...

Добавлено @ 20:46

Цитата(Domestic @ 27.11.2004, 20:40)

Ну деление-то остается делением, оно все-таки медленнее К тому же тут ты используешь (неявно) еще один оператор - конвертации интежера в дабл : Код dd = ll/5000; эквивалентно: dd = (double) (ll / 5000); а конвертация - медленная штука.

дело в том, что конвертацией так-же может заведовать сопроцессор ... но увы и ах, я так и не понимаю на чем теряется время ....

Цитата

дело в том, что конвертацией так-же может заведовать сопроцессор ... но увы и ах, я так и не понимаю на чем теряется время ....

конвертацией занимается JVM, опкод l2d (в данном случае)

Цитата

не мог-бы ты привести во что выражается в байткоде вычитание и деление?

опкоды lsub и ldiv (для лонгов).

Все это ни о чем не говорит, т.к. JVM всегда вызывает методы ОС, она не работает с процессором напрямую.

Это сообщение отредактировал(а) Domestic Cat - 27.11.2004, 20:51

Цитата(Domestic @ 27.11.2004, 20:50)

Цитата дело в том, что конвертацией так-же может заведовать сопроцессор ... но увы и ах, я так и не понимаю на чем теряется время .... конвертацией занимается JVM, опкод l2d (в данном случае) Цитата не мог-бы ты привести во что выражается в байткоде вычитание и деление? опкоды lsub и ldiv (для лонгов). Все это ни о чем не говорит, т.к. JVM всегда вызывает методы ОС, она не работает с процессором напрямую.

ааа. вот тыт понятно. Спасибо! а жаль между прочим! JVM все одно на всех платформах своя - могли-б и сопр. задействовать на прямую ...

Добавлено @ 20:59

Цитата(Sleepy_PIP @ 27.11.2004, 20:55)

Цитата(Domestic @ 27.11.2004, 20:50) Цитата дело в том, что конвертацией так-же может заведовать сопроцессор ... но увы и ах, я так и не понимаю на чем теряется время .... конвертацией занимается JVM, опкод l2d (в данном случае) Цитата не мог-бы ты привести во что выражается в байткоде вычитание и деление? опкоды lsub и ldiv (для лонгов). Все это ни о чем не говорит, т.к. JVM всегда вызывает методы ОС, она не работает с процессором напрямую. ааа. вот тыт понятно. Спасибо! а жаль между прочим! JVM все одно на всех платформах своя - могли-б и сопр. задействовать на прямую ...

хотя я не прав опять - хочется выжать все из конкретной системы - пиши на компилирующихся в системный код языках. и все проблеммы будут разрешены

Ребята, зачем деление вычитанием? Причем просто вот так в цикле!
Вчера вечером вспомнил, что можно делить столбиком, и что битовые операции очень быстрые. В общем вот что получилось:

Код

static int div( int a, int b) {         if (b == 0) {             throw new ArithmeticException( "divide by zero");         }         int r = 0, t = 1;         boolean plus = (a ^ b) >= 0; //        if (a < 0) { // alternative to 'a = -a;' (but probably less efficient) is  //            a = ~a; //            a++; //        }         if (a < 0) a = -a;         if (b < 0) b = -b;         while ( a > b) {             b <<= 1;             t <<= 1;         }         while ( t > 0) {             if (a >= b) {                 a -= b;                 r += t;             }             b >>= 1;             t >>= 1;         }         return plus ? r : -r;     }

Кому не лень, сравните сскорости с делением методом вычитания в случаях, когда
а) число делится на бОльшее (т.е. нуль в результате)
б) очень большое число делится на единицу, например.
в) что-нибудь на что-нибудь, когда ответ - первые единицы (1, 2, 3, ...)
Вот случай (б) должен оказаться показательным

Это сообщение отредактировал(а) Zandr - 17.3.2005, 08:37

Ой, жалко - то как...... Тута ошибочка есть неразрешимая почти...
может вылазить при |a| > 0x40000000. Эх.

Это сообщение отредактировал(а) Zandr - 18.3.2005, 07:52

прикольно, запустил тест "деление путём вычитания" c ключом -server (взят выше)

del by minus 31 milliseconds
del by del 0 milliseconds

без него, что-то порядка

del by minus 47 milliseconds
del by del 78 milliseconds

%)
Оптимизации это великолепно.


Хотя вполне возможно, это следствие оптимизации цикла, в режиме -server.

Так и есть.

Если заменить 5000, на рандомный делитель int by = r.nextInt(4000)+1000;
то обычное деление выигрывает в обычном и сервер моде.
Короче говоря то, что делить вычитанием быстрее - тоже заблуждение.
В случае -server / выигрывает в 2 раза, -client / выигрывает на 15-20% (1782 vs 1468 ms).

Это сообщение отредактировал(а) NotGonnaGetUs - 17.3.2005, 18:29