Szybkie potęgowanie w GNU MP interfejs C++

Witam,

Korzystam z tej biblioteki//www.informatik.hs-mannheim.de/gmp/gmp_13.html#SEC70

mpz_class fast_exp(mpz_class a, mpz_class exp, const mpz_class m)
{
  mpz_class result = 1;
  mpz_class x = a % m;
  
  for(int i = 1; i <= exp; i <<= 1) {
    x %= m;
    if( (exp & i) != 0 ) {
      result *= x;
      result %= m;
    }
    x *= x;
  }
  
  return result;
}

Zastanawia mnie czemu ten kod nie zawsze działa (tylko dla małych wykładników exp). Podejrzewam, że problem tkwi w wykonywaniu operacji bitowych dla typu abstrakcyjnego, który tylko w szczególnym przypadku można zanalizować bit po bicie (dla bardzo małych liczb).

1. Czy moje podejrzenia są słuszne?
2. W jaki najwydajniejszy sposób (by nie używać naiwnego potęgowania) można zrealizować ten algorytm (zależy mi na samodzielnej implementacji).

Mój pomysł jest następujący:

• liczbę exp metodą kartkową przekonwertować na tablicę bitów, a dla tak przygotowanej już tablicy wykonywać ten algorytm.

Nie wiem tylko czy to najlepsze wyjście i będę wdzieczny za rady / sugestie.

Pozdrawiam,

zamiast for(...
for( ; exp != 0; exp /= 2 )

zamiast if(exp
if( exp%2 != 0 )

Dzięki..

Algorytm się wykonuje, ale chyba nie wszystko w porządku. Czy możecie polecić na 100% pewną implementację tego algorytmu napisaną w dowolnym języku bym mógł porównać dane wyjściowe?

• Ruby:

x ** y

• bc:x^y
• Python:

pow(x, y)

• Haskell:

x ** y
-- lub
x ^^ y
-- lub
x ^ y

Dzięki za sugestię, ale to chyba nie ten algorytm (tylko potęgowanie naiwne).

Próbowałem w Ruby w następujący sposób:
irb> (493843843898873827382).modulo(7)
warning: in ab, b may be too big

Ta metoda nie działa. Za to operacja szybkiego potęgowania modulo powinna być jakoś wykonywalna.

Margor napisał(a)

Dzięki za sugestię, ale to chyba nie ten algorytm (tylko potęgowanie naiwne).

Próbowałem w Ruby w następujący sposób:
irb> (493843843898873827382).modulo(7)
warning: in ab, b may be too big

Ta metoda nie działa. Za to operacja szybkiego potęgowania modulo powinna być jakoś wykonywalna.

Sorry nie zauważyłem, że chodzi o potęgowanie modulo. Jak tak to po co wymyślać koło na nowo? Masz przecież mpz_powm

a^b % m
while(1)
	w=1
	if b %2==1
		w = w * a % m
	b /=2
	if b==0 return w
	a = a*a % m

PARI/GP> Mod(12345678901,2345678)^345678901
time = 0 ms.
Mod(1377675, 2345678)

Dziękuje za sugestię z mpz_powm. Nie zauważyłem, że taka funkcja istnieje. Moja funkcja jak i ta w bibliotece zwracają te same rezultaty, są więc w porządku i nie trzeba angażować w to innych języków.

Dziękuje za sugestię z mpz_powm. Nie zauważyłem, że taka funkcja istnieje. Moja funkcja jak i ta w bibliotece zwracają te same rezultaty, są więc w porządku i nie trzeba angażować w to innych języków.