algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szybkie potęgowanie modularne - Implementacja w C/C++
Ocena użytkownikóww: *****  / 16
SłabyŚwietny
Nadesłany przez Tomasz Lubiński, 13 listopada 2006 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

spm.c:
//
// Szybkie Potegowanie modulo
//
// www.algorytm.org
// (c)2006 Tomasz Lubinski
//

#include "stdio.h"
#include "stdlib.h"

// calculates a^b mod m
int power_modulo_fast(int a, int b, int m)
{
   int i;
   int result = 1;
   long int x = a%m;

   for (i=1; i<=b; i<<=1)
   {
      x %= m;
      if ((b&i) != 0)
      {
         result *= x;
         result %= m;
      }
      x *= x;
   }

   return result;
}



int main(void)
{
   //9688563^45896 mod 71 = 30
   printf("9688563^458926 mod 71 = %d\n", power_modulo_fast(9688563, 458926, 71));

   //12^53 mod 7 = 3
   printf("12^53 mod 7 = %d\n", power_modulo_fast(12, 53, 7));

   return 0;
}
Komentarze
photo
-6 # k 2012-02-23 21:14
Dla takich liczb: power_modulo_fa st(95925179, 427342114, 1000000000)
powinien wyjść wynik: 272569881

ten źle działa
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # RaQe 2012-04-16 22:02
źle działa bo przekraczasz int'a w parametrze - jeśli potrzebujesz większych wartości zawsze możesz zmodyfikować algorytm dodając np long long'i ;)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Mrowqa 2013-10-22 17:10
RaQe - nieprawda. Kolega wyżej nie przekracza inta. Kod źle działa, bo w implementacji jest integer overflow, w miejscu mnożenia zmiennych 'result' oraz 'x'.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz