Вычисление n-ной степени числа

@john_jerome · Регистрация: 27.11.2010

Author24 — интернет-сервис помощи студентам

Вычислить X^n

@Mikl___ · 01.12.2010, 14:48

john_jerome, строка для Гугла "примеры на ассемблере для вычисления возведения в степень"

@vital792 · 01.12.2010, 14:54

john_jerome, показатель степени целое число? или любое?

@Mikl___ · 01.12.2010, 14:55

vital792, ему без разницы -- лишь бы самому не делать

@john_jerome · 01.12.2010, 15:16 **[ТС]**

vital792, целое число
Mikl___, не слишком ли ты самоуверен?

@Mikl___ · 01.12.2010, 15:20

john_jerome, для чего?

@vital792 · 01.12.2010, 15:24

Mikl___, действительно, можно чуть повежливее? Не все тут специалисты.

john_jerome,

Assembler

...
mov cx, показатель
dec cx
mov ax, основание
mov bx, ax
@1:
mul bx
loop @1
...

результат будет в паре dx:ax

@john_jerome · 01.12.2010, 16:12 **[ТС]**

Благодарю!

murderer · 01.12.2010, 18:35

vital792
У тебя алгоритм сложности O(n).

Вот алгоритм из модуля Math для Delphi. Выполняется за log2(n) итераций.

Delphi

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;

@vital792 · 01.12.2010, 21:59

murderer, неплохо. Даже красиво. Но я надеюсь что ТС будет сдавать мой вариант

@Mikl___ · 02.12.2010, 04:46

vital792, murderer
Алгоритм быстрого возведения в степень
Используется представление числа x^m: http://upload.wikimedia.org/ma... 330a9e.png
на паскале

Pascal

function power(t, k: integer): integer; //возведение числа t в степень k
var
  res:integer;
begin
  res := 1;
  while (k > 0) do
  begin
    if (k mod 2 = 1) then  //   {или напишите "if (k and 1 = 1)" для большей скорости выполнения} 
      res := res * t;
    t := t * t;
    k := k div 2;     //   {или напишите "k := k shr 1;" для большей скорости выполнения}
  end;
  power := res;
end;

на Си

C

int power(int t, int k) {
// возведение t в степень k
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
}

Чтобы узнать, сколько умножений потребуется для возведения числа x в степень n алгоритмом быстрого возведения в степень, нужно произвести вычисления по следующей формуле: k = H + 2(E − 1), где H — количество нулей, а E — количество единиц в двоичной записи числа n.
Так, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 умножений.
Таким образом количество умножений равно O(lnn).

@Mikl___ · 02.12.2010, 15:24

рисунок к предыдущему сообщению

@vital792 · 02.12.2010, 15:33

Mikl___, неплохо. Не знал этот алгоритм

@vital792 2014 / 1286 / 61 Регистрация: 05.06.2010 Сообщений: 2,213
	02.12.2010, 15:33	13
	Mikl___, неплохо. Не знал этот алгоритм 0

@john_jerome 47 / 47 / 1 Регистрация: 27.11.2010 Сообщений: 95
		1
	Вычисление n-ной степени числа 01.12.2010, 14:39. Показов 11415. Ответов 12 Метки нет (Все метки) Вычислить X^n 1

@Mikl___ Ушел с форума 16279 / 7604 / 1065 Регистрация: 11.11.2010 Сообщений: 13,617
	01.12.2010, 14:48	2
	john_jerome, строка для Гугла "примеры на ассемблере для вычисления возведения в степень" 1

@vital792 2014 / 1286 / 61 Регистрация: 05.06.2010 Сообщений: 2,213
	01.12.2010, 14:54	3
	john_jerome, показатель степени целое число? или любое? 1

@Mikl___ Ушел с форума 16279 / 7604 / 1065 Регистрация: 11.11.2010 Сообщений: 13,617
	01.12.2010, 14:55	4
	vital792, ему без разницы -- лишь бы самому не делать 0

@john_jerome 47 / 47 / 1 Регистрация: 27.11.2010 Сообщений: 95
	01.12.2010, 15:16 [ТС]	5
	vital792, целое число Mikl___, не слишком ли ты самоуверен? 1

@Mikl___ Ушел с форума 16279 / 7604 / 1065 Регистрация: 11.11.2010 Сообщений: 13,617
	01.12.2010, 15:20	6
	john_jerome, для чего? 0

@john_jerome 47 / 47 / 1 Регистрация: 27.11.2010 Сообщений: 95
	01.12.2010, 16:12 [ТС]	8
	Благодарю! 1

@vital792 2014 / 1286 / 61 Регистрация: 05.06.2010 Сообщений: 2,213
	01.12.2010, 21:59	10
	murderer, неплохо. Даже красиво. Но я надеюсь что ТС будет сдавать мой вариант 0

@Mikl___ Ушел с форума 16279 / 7604 / 1065 Регистрация: 11.11.2010 Сообщений: 13,617
	02.12.2010, 15:24	12
	рисунок к предыдущему сообщению Миниатюры 0