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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Ошибки в исх. коде. Неправильно работает при специальных входных параметрах. Делфи-синтаксис более компактный
Строка 52: Строка 52:
Result := Result * Val;
Result := Result * Val;


Pwr := Pwr div 2;
Pwr := Pwr shr 1;
Val := Val * Val;
Val := Val * Val;
end;
end;

Версия от 17:19, 24 апреля 2012

Используется представление числа 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;
}

Язык C++

int power(int t, int k)   //возведение числа t в степень k
{
  int i, res;
  res=t;
  t=1;
  for(i=0; i<k; i++)
    t*=res;
}

Паскаль

//Синтаксис - Delphi
function power(Val, Pwr: integer): integer; {возведение числа t в степень k}
begin
  if Val = 0 then
    Result := 0
  else
    if Pwr = 0 then
      Result := 1
    else
      if Pwr = 1 then
        Result := Val
      else
        begin
          Result := 1;
          while Pwr > 0 do
          begin
            if Pwr mod 2 = 1 then
              Result := Result * Val;

            Pwr := Pwr shr 1;
            Val := Val * Val;
          end;
        end;
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;
}