Реализации алгоритмов/Быстрое возведение в степень: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Строка 61: Строка 61:
if (v%2 == 1) {
if (v%2 == 1) {
if (mod !=0) s = (s*c) % mod;
if (mod !=0) s = (s*c) % mod;
else s = s*c;
v = (v-1)/2;
v = (v-1)/2;
if (mod !=0) c = (c*c) % mod;
if (mod !=0) c = (c*c) % mod;
else c = c*c;
}
}
else {
else {

Версия от 19:02, 24 ноября 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) {
#возведение числа val в степень step по step по модулю mod. 
#if результат не требуется приводить по модулю then подать на вход mod=0.
	s = 1; v = step; c = val;
	while (v != 0) {
		if (v%2 == 1) {
			if (mod !=0) s = (s*c) % mod;
                        else s = s*c;
			v = (v-1)/2;
			if (mod !=0) c = (c*c) % mod;
                        else c = c*c;
		}
		else {
			v = v/2;
		}	
	}
	return s;
}