Конференция "Прочее" » Возведение в степень - что быстрее?
 
  • Xenus (27.10.08 18:32) [0]
    Есть два целых числа. Нужно возвести их в степень.

    X, Y

    Что быстрее:

    IntPower(X, Y);
    или
    Exp(X * ln(Y)) ?
    Или может еще есть функции из стандартных?

    Чтобы не рыться вот исходные коды обоих функций.

    function Exp(X: Real): Real; System.pas  :
    procedure       _EXP;  
    asm
           {       e**x = 2**(x*log2(e))   }

           FLDL2E              { y := x*log2e;      }
           FMUL
           FLD     ST(0)       { i := round(y);     }
           FRNDINT
           FSUB    ST(1), ST   { f := y - i;        }
           FXCH    ST(1)       { z := 2**f          }
           F2XM1
           FLD1
           FADD
           FSCALE              { result := z * 2**i }
           FSTP    ST(1)
    end;



    (+ ln)

    function IntPower(const Base: Extended; const Exponent: Integer): Extended;
    asm
           mov     ecx, eax
           cdq
           fld1                      { Result := 1 }
           xor     eax, edx
           sub     eax, edx          { eax := Abs(Exponent) }
           jz      @@3
           fld     Base
           jmp     @@2
    @@1:    fmul    ST, ST            { X := Base * Base }
    @@2:    shr     eax,1
           jnc     @@1
           fmul    ST(1),ST          { Result := Result * X }
           jnz     @@1
           fstp    st                { pop X from FPU stack }
           cmp     ecx, 0
           jge     @@3
           fld1
           fdivrp                    { Result := 1 / Result }
    @@3:
           fwait
    end;

  • Jeer © (27.10.08 18:40) [1]
    Так проверь, потом доложишь.
  • БарЛог © (27.10.08 19:37) [2]
    IntPower
    ИМХО
  • TUser © (27.10.08 20:17) [3]
    А вот все эти FADD и FSCALE за один таккт все выполняются, за такое же время, как xor? Что-то подозревается, что это от процессора зависит.

    Ламерское мнение, правда.
  • БарЛог © (27.10.08 20:34) [4]
    > А вот все эти FADD и FSCALE за один таккт все выполняются, за такое же время, как xor? Что-то подозревается, что это от процессора зависит.

    Ну... тип процессора в сабже не уточняется :) Может, там 386.
  • Anatoly Podgoretsky © (27.10.08 21:11) [5]
    > TUser  (27.10.2008 20:17:03)  [3]

    Не так, на современных процессорах за такт выполняется несколько операций, до CORE 2 было 5, с CORE 2 чуть поменьше.
  • TUser © (27.10.08 21:16) [6]
    Ну вот xor'ов и этой экзотики одинаковое число за так пройдет? Что-то мне подсказывает, что нет, и даже не стандартизовано. А значит - зависит от типа проца, хъотя бы теоретически.
  • Омлет (27.10.08 23:03) [7]
    1. Смотри http://www.rsdn.ru/article/alg/fastpow.xml

    2. Еще один, чисто академический вариант ;)


    function Pow(x, n: Integer): Integer;
    var x1: Integer;
    begin
      if n = 0 then Result := 1
      else begin
         x1 := Pow(x, n shr 1);
         Result := x1*x1;
         if (n and 1 <> 0) then Result := Result*x;
      end;
    end;

  • Xenus (28.10.08 00:29) [8]

    > Омлет   (27.10.08 23:03) [7]


    Да но хотелось бы по факту стандартных функций.

    У автора статьтьи очень похож код на
    код функции
    function Exp(X: Real): Real; System.pas  :
    (procedure       _EXP; )
    в первом варианте кода в статьте.

    Т.е. получаем что вариант Exp( X * ln(Y) ) быстрее чем IntPower(X, Y)
    на современных процессорах?
  • Xenus (28.10.08 00:29) [9]

    > У автора статьтьи очень похож код на
    > код функции


    Практически один в один.
  • Xenus (28.10.08 00:30) [10]

    > У автора статьтьи очень похож код на
    > код функции


    Практически один в один.

    А такой вопрос паралльельно - есть ли функция возводящая двойку в целую степень?
  • Xenus (28.10.08 00:37) [11]
    И еще я хотел спросить, не раз замечал в исходниках когда пишут так:

    IntPower(1.0 + R, N)
    вместо просто целого числа, без нуля. А зачем?
  • Юрий Зотов © (28.10.08 04:09) [12]
    > Xenus   (28.10.08 00:37) [11]

    1 + R - сложение целого с вещественным. Тратится время на предварительное преобразование младшего типа к старшему.

    1.0 + R сложение вещественного с вещественным. Преобразование не требуется.

    Если компилятор умный, то он и в первом случае сгенерит вещественную (а не целую) константу. Но лучше на его ум не надеяться.
  • Омлет (28.10.08 07:22) [13]
    > Xenus

    Ты статью всю прочитай. Автор показал, что основание логарифма 2 дает большую точность и теоретически немного быстрее.

    Возведение двойки в целую степень:  2^n = 1 shl n
    умножение на степень двойки:  x*(2^n) = x shl n
  • Дуб © (28.10.08 09:32) [14]
    А вообще - Кнут, Глава 4. :) Там много отчудных ожидает.
  • isasa © (28.10.08 13:51) [15]
    Юрий Зотов ©   (28.10.08 04:09) [12]

    Если компилятор умный,


    :)

    Не все такие умные :)

    В Паскале и Дельфи
    x:=1/3; x:=1.0/3.0; эквивалентны,
    а в C и C++ можно так нарваться .... :)
  • @!!ex © (29.10.08 19:46) [16]
    > а в C и C++ можно так нарваться .... :)

    Нарваться можно если не знать операторов С.
    А не знаение операторов языка - это равносильно не знанию языка.
    Не зная язык писать вообще нельзя.

    P.S.
    Каюсь, сам нарывался. :)
    Но мнение от этого не меняется. Скорее научило, что надо читать стандарт, прежде чем лезть прогать.
 
Конференция "Прочее" » Возведение в степень - что быстрее?
Есть новые Нет новых   [134446   +30][b:0][p:0.002]