Liczba 2^100 to 1267650600228229401496703205376, trzydzieści jeden cyfr, a ekran wypisuje ją jako 1.2676506002282⋅10+30. Poproś o 2^100 mod 7 w tym samym oknie, a odpowiedź to 0. Poproś o 2^4 mod 7, a to 2 — i to jest ta poprawna: 2^3 = 8 ≡ 1 (mod 7), więc 2^99 ≡ 1 i 2^100 ≡ 2, albo równoważnie 2^6 ≡ 1 i 100 mod 6 = 4 redukują całe pytanie do 2^4 mod 7.
Nic w potędze nie jest błędne; błędna jest reszta. Double przechowuje pięćdziesiąt trzy bity, więc najbliższa reprezentowalna wartość 2^100/7 chybia o mniej więcej 10^13, a reszta liczona jako a − 7·floor(a/7) dziedziczy błąd dużo większy niż moduł. Poprawna metoda nigdy nie pozwala liczbie urosnąć: najpierw redukuj, potem podnoś — dokładnie to robi potęgowanie modularne w każdej bibliotece kryptograficznej, i dlatego RSA może pracować z liczbami tysięcznobitowymi na sprzęcie, który przechowuje pięćdziesiąt trzy. To ten sam sufit, który czyni 2^53 ostatnim dokładnym licznikiem całkowitym.
Odpowiedź
0
Jak to czytać
2^100 mod 7 na stole roboczym — odpowiedź maszyny, nie arytmetyki. Drugi link to 2^6 mod 7 = 1, okres; trzeci to zredukowane pytanie 2^4 mod 7 = 2, czyli prawdziwa wartość.
Źródło
2^100 = 1267650600228229401496703205376 is exact in binary floating point, being a power of two, but the quotient by 7 has thirty significant digits and IEEE-754 binary64 carries only about sixteen, so a mod implemented as a − b·floor(a/b) returns a remainder taken from the rounded quotient
Rozwiąż w kalkulatorze
Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.