algorytm.org

Operacja modulo na dużych liczbach

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?

Operacja modulo na dużych liczbach
Ocena użytkowników:***** / 21
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 13 listopada 2006 23:59

W niektórych przypadkach mamy potrzebę obliczenia wartości a mod n dla bardzo dużej liczby a. Tak dużej, że nie można jej przechowywać w zmiennej całkowitoliczbowej, a jedynie jako tekst. Nawet dla tak dużych liczb jesteśmy w stanie obliczyć wartość modulo. Tak wielką liczbę możemy podzielić na kilka mniejszych łańcuchów a następnie obliczać wartość modulo dla częsci od lewej do prawej strony, za każdym razem doklejając (łącząc łańcuchy) do kolejnej częsci wynik z poprzedniej. W ten sposób jesteśmy w stanie obliczyć wartość modulo dla praktycznie dowolnie dużej liczby wejściowej a. Algorytm zapisany w pseudokodzie wygląda następująco (założymy, że długość łańcuchów, na które dzielimy liczbę wejściową to 1), znak "+" oznacza tutaj łączenie łancuchów np: "1" + "2" = "12":

wynik = "";
for i=1 to length(a)
  begin
    wynik = wynik + a[i];
    wynik = wynik mod n;
  end;

Przykład:

Obliczymy następującą wartość 1295302 mod 7
Bierzemy zatem pierwszą cyfrę z lewej i wykonujemy operacje modulo: 1 mod 7 = 1
Do wyniku z poprzedniego kroku dodajemy kolejną cyfrę (2) i dzielimy modulo: 12 mod 7 = 5
Dodajemy kolejną cyfrę (9) i znów dzielimy modulo: 59 mod 7 = 3
Do wyniku z poprzedniego kroku dodajemy kolejną cyfrę (5), wykonujemy kolejną operację modulo: 35 mod 7 = 0
Dodajemy kolejną cyfrę (3) i znów dzielimy modulo: 3 mod 7 = 3
Dodajemy kolejną cyfrę (0) i znów dzielimy modulo: 30 mod 7 = 2
Dodajemy kolejną cyfrę (2) i znów dzielimy modulo: 22 mod 7 = 1
Zatem ostateczny wynik to: 1295302 mod 7 = 1



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 2
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 4
MarianC/C++C++
.cpp
.cpp
***** / 8
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 3
Tomasz LubińskiJava
.java
.java
***** / 3
tmarcinMatlab
.mat
.mat
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 maja 2010 22:30
Komentarze
photo
+3 # sajmondo 2010-02-23 15:28
Tytuł brzmi 'Operacja modulo na dużych liczbach', natomiast treść dotyczy tylko jednej wielkiej liczby

Co z przypadkiem np.: 12953043543643453453453454352 mod 7435346346455543534?
Jaki algorytm nadaje się do takiego działanie?

Pozdrawiam
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-8 # kotlet 2010-03-28 04:18
odejmowanie i sprawdzanie znaku
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # TomaszK 2013-02-20 21:53
Być może sama zamiana z typu 'int' na większy zakres liczbowy pomoże :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # GrzegorzS 2014-01-04 19:07
Panie sajmondo - to co Pan uważa za dużą liczbę da się obliczyć klasycznie bez tego algorytmu . Ten algorytm da się stosować do liczb , których reprezentację dziesiętną nie da się zapisać na stronie tekstu na ekranie i to małymi literami .
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # kolo 2016-04-23 16:29
chcę policzyć X mod Y
gdzie:
X = 100'000 cyfr
Y = 20'000 cyfr
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # MarioC64 2016-03-08 13:19
Takich operacji nie wykonuje się na stringach - to marnotrastwo, bo w jednym bajcie pamiętane jest co najwyżej 10 kombinacji. Trzeba używać typów złożonych z wielu typów całkowitoliczbo wych, jak np. to w Javie: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/math/BigInteger.java
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Rob 2017-02-17 14:44
Dokładnie. To nie są duże liczby. Duże liczby to te powyżej 2^63... takie że nie obejmuje ich już typ bigint.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz