Liczba 128 bitowa modulo...

Witam,

Zdefiniowane są 3 liczby typu unsigned long long:
unsigned long long high;
unsigned long long low;
unsigned long long M;

W jaki sposób można najszybciej policzyć (high * 2^64) + (low) (mod M) ?
Interesuje mnie teoria, nie gotowe rozwiązanie. A spędziłem już nad tym z pół godziny nad kartką...

To znaczy można to zrobić dość łatwo na siłę. Robić modulo na każdym składniku (również 2 ^ 64), wymnażać i dodawać tak długo dopóki nie otrzymamy wartości mniejszej od M. Zrobiłem symulację w excelu i niestety taki algorytm często potrzebował by kilkudziesięciu obiegów pętli zanim zwrócił by wynik. Ja natomiast chciałbym obliczyć wynik bez używania pętli (w czasie stałym). Jak można to zrobić?

Ja najpierw bym policzył 2^64 mod M, podnosząc po kolei do kwadratu. (5 mnożeń modulo)
potem jest bułka z masłem: jedno mnożenie i jedno dodawanie modulo.

coobba napisał(a)

Ja najpierw bym policzył 2^64 mod M, podnosząc po kolei do kwadratu. (5 mnożeń modulo)
potem jest bułka z masłem: jedno mnożenie i jedno dodawanie modulo.

No właśnie nie jest bułka z masłem :) Też mi się tak wydawało na początku...

Samo 2^{64 (mod M) jest trywialne do policzenia, można to zrobić używając jednego dzielenia modulo (następna wartość po 2}64-1 (mod N) - czyli maksymalna możliwa liczba do podzielenia na IA-32).

Aczkolwiek obliczenie 2^64 (mod N) nie rozwiązuje sprawy, gdyż po "pomnożeniu i wykonaniu jednego dodawania" nadal mogę mieć liczbę 128 bitową. Bedę musiał powtórzyć takie modula, mnożenia kilka razy zanim otrzymam wynik... A chciałbym to mieć możliwie jak najszybciej.

Nie mam problemu z wymnożeniem tego wszystkiego i utworzeniem w ten sposób liczby 128 bitowej.

Kłopoty zaczynają się z dzieleniem liczby 128 bitowej (składającej się z dwóch unsigned long long) przez liczbę 64 bitową (zmienna unsigned long long). Może ktoś mi podpowie jak z tym dzieleniem można sobie poradzić?

Witam.
Nie jestem pewien, czy dobrze zrozumiałem i czy ci to pomoże ale jest taki jeden prosty algorytm do dzielenia modulo dużych liczb polegający na dzieleniu takiej liczby na kawałki i dzieleniu każdego kawałka po kolei. Mogę się pomylić ale chyba wygląda to mniej więcej tak: jest duża liczba X. Bierzemy kawałek "z przodu" tej liczby i dzielimy go modulo a wynik "doklejamy" an początek tego co zostało. I tak do końca. Jeśli trafiłem z odpowiedzią to daj znać, to ci to opiszę dokładniej ale sam najpierw muszę zajrzeć do programu, w którym to sam ostatnio stosowałem.

no ale high2^64 (mod m) jest równoważne
(high (mod m))(2^64 (mod m)) (mod m)
2^64 (mod m) nie problem policzyć.