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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Строка 10: Строка 10:
while (k)
while (k)
{
{
if (k & 1)
if (k & 1)
res *= t;
res *= t;
t *= t;
t *= t;
k >>= 1;
k >>= 1;

Версия от 17:44, 15 августа 2016

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

Язык Си#

static int Pow(int a, int b)
        {
            int re = 1;
            while (b != 0)
            {
                if (b % 2 == 1) re *= a; a *= a; b >>= 1;
            }
            return re;
        }
static int Pow2(int a, int b)//Int32-версия
        {
            if (b > 2 && (a > 1 || a < -1))
            {
                bool sgn = false;
                if (a < 0) {if(a==-2 && b==31) return 0-0x80000000; if (b % 2 != 0) sgn = true; a = -a; }
                if (a < 1291)
                {
                    if (a > 215) { if (b > 3) throw new OverflowException();
                    else return sgn ? -pow[a + 406] : pow[a + 406]; }
                    else
                    {
                        if (ind[a] + b - 3 >= ind[a + 1]) throw new OverflowException();
                        else return sgn ? -pow[ind[a] + b] : pow[ind[a] + b];
                    }
                }
                else throw new OverflowException();
            }
            else
            {
                if (b == 2) return checked(a * a);
                if (b == 1) return a;
                if (b == 0) return 1;//0^0 тоже принято за 1
                if (a == 1) return 1;
                if (a == 0 && b > 0) return 0;
                if (a == -1) return b % 2 == 0 ? 1 : -1;
                throw new InvalidOperationException();//деление на 0 или рациональное число
            }
        }
значения массива Ind
int z = 0; Console.Write("0,0,-3,");
            for (int i = 3; i < 31; i++) z++; Console.Write((z - 3) + ",");
            for (int i = 3; i < 20; i++) z++; Console.Write((z - 3) + ",");
            for (int i = 3; i < 16; i++) z++; Console.Write((z - 3) + ",");
            for (int i = 3; i < 14; i++) z++; Console.Write((z - 3) + ",");
            for (int x = 6; x < 8; x++) { for (int i = 3; i < 12; i++) { z++; } Console.Write((z - 3) + ","); }
            for (int i = 3; i < 11; i++) z++; Console.Write((z - 3) + ",");
            for (int x = 9; x < 11; x++) { for (int i = 3; i < 10; i++) { z++; } Console.Write((z - 3) + ","); }
            for (int x = 11; x < 15; x++) { for (int i = 3; i < 9; i++) { z++; } Console.Write((z - 3) + ","); }
            for (int x = 15; x < 22; x++) { for (int i = 3; i < 8; i++) { z++; } Console.Write((z - 3) + ","); }
            for (int x = 22; x < 36; x++) { for (int i = 3; i < 7; i++) { z++; } Console.Write((z - 3) + ","); }
            for (int x = 36; x < 74; x++) { for (int i = 3; i < 6; i++) { z++; } Console.Write((z - 3) + ","); }
            for (int x = 74; x < 215; x++) { for (int i = 3; i < 5; i++) { z++; } Console.Write((z - 3) + ","); }
значения массива pow
            for (int i = 3; i < 31; i++) Console.Write(Pow(2, i) + ",");
            for (int i = 3; i < 20; i++) Console.Write(Pow(3, i)+",");
            for (int i = 3; i < 16; i++) Console.Write(Pow(4, i) + ",");
            for (int i = 3; i < 14; i++) Console.Write(Pow(5, i) + ",");
            for (int x = 6; x < 8; x++) for (int i = 3; i < 12; i++) Console.Write(Pow(x, i) + ",");
            for (int i = 3; i < 11; i++) Console.Write(Pow(8, i) + ",");
            for (int x = 9; x < 11; x++) for (int i = 3; i < 10; i++) Console.Write(Pow(x, i) + ",");
            for (int x = 11; x < 15; x++) for (int i = 3; i < 9; i++) Console.Write(Pow(x, i) + ",");
            for (int x = 15; x < 22; x++) for (int i = 3; i < 8; i++) Console.Write(Pow(x, i) + ",");
            for (int x = 22; x < 36; x++) for (int i = 3; i < 7; i++) Console.Write(Pow(x, i) + ",");
            for (int x = 36; x < 74; x++) for (int i = 3; i < 6; i++) Console.Write(Pow(x, i) + ",");
            for (int x = 74; x < 216; x++) for (int i = 3; i < 5; i++) Console.Write(Pow(x, i) + ",");
            for (int x = 216; x < 1291; x++) for (int i = 3; i < 4; i++) Console.Write(Pow(x, i) + ",");

Паскаль

//Синтаксис - Delphi
function power(Val, Pwr: integer): integer; {возведение числа Val в степень Pwr}
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 and 1) = 1 then
              Result := Result * Val;

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


   //возведение в любую степень, даже под корень (корень степени N = степень 1/N)
   function power(Val,Pwr:Real):Real; {возведение числа Val в степень Pwr}
   begin
    Power:=Exp(Pwr*Ln(Val));
   end;

Python

def fast_pow(x, y):
    if y == 0:
       return 1
    if y == -1:
        return 1. / x
    p = fast_pow(x, y / 2)
    p *= p
    if y % 2:
        p *= x
    return p

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;
}