Реализации алгоритмов/Быстрое возведение в степень: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 55: | Строка 55: | ||
<source lang=javascript> |
<source lang=javascript> |
||
function faststep (val, step, mod) { |
function faststep (val, step, mod) { |
||
mod = parseInt(mod); |
|||
#возведение числа val в степень step по step по модулю mod. |
|||
#if результат не требуется приводить по модулю then подать на вход mod=0. |
|||
s = 1; v = step; c = val; |
s = 1; v = step; c = val; |
||
while (v != 0) { |
while (v != 0) { |
||
flag = 0; |
|||
if (v%2 == 1) { |
if (v%2 == 1) { |
||
if (mod |
if (!mod) |
||
s = s*c; |
|||
else |
|||
s = (s*c) % mod; |
|||
v = (v-1)/2; |
v = (v-1)/2; |
||
if (mod |
if (!mod) |
||
c = c*c; |
|||
else |
|||
c = (c*c) % mod; |
|||
flag = 1; |
|||
} |
} |
||
else { |
else { |
||
v = v/2; |
v = v/2; |
||
} |
} |
||
if (!flag) |
|||
if (!mod) |
|||
c = c*c; |
|||
else |
|||
c = (c*c) % mod; |
|||
} |
} |
||
return s; |
return s; |
Версия от 14:14, 27 ноября 2011
Используется представление числа xm:
- .
Язык Си
int power(int t, int k) // возведение t в степень k
{
int res = 1;
while (k)
{
if (k & 1)
res *= t;
t *= t;
k >>= 1;
}
return res;
}
Паскаль
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
res := res * t;
k := k div 2;
t := t * t;
end;
power := res;
end;
Python
def FastPow (t, k): # Быстрое возведение числа t в степень k
res = 1
while k:
if (k & 1):
res *= t
k = k >> 1
if k == 0:
break
t *= t
return res
JavaScript
function faststep (val, step, mod) {
mod = parseInt(mod);
s = 1; v = step; c = val;
while (v != 0) {
flag = 0;
if (v%2 == 1) {
if (!mod)
s = s*c;
else
s = (s*c) % mod;
v = (v-1)/2;
if (!mod)
c = c*c;
else
c = (c*c) % mod;
flag = 1;
}
else {
v = v/2;
}
if (!flag)
if (!mod)
c = c*c;
else
c = (c*c) % mod;
}
return s;
}