Matematyka.pl

Jak szybko obliczyć \(\displaystyle{ 2 ^{x}}\) z dowolnej liczby N.
np:
\(\displaystyle{ 1024 = 2^{10} }\)
proste, dla:
\(\displaystyle{ 90854840536950861318665475986000566794205170085914757535186274897579911014174740415773881339220445695095315200783272241691825203576832 = 2 ^{445} }\)
a co z coraz większymi liczbami.
Załóżmy że mamy liczę N mającą w zapisie dziesiętnym miliardy cyfr, dzielenie jej przez 2 trwałoby zbyt długo. Czy jest jakiś szybki sposób?

Co to znaczy "obliczyć"? Wypisać wszystkie cyfry po kolei? Podejrzewam, że nie ma na świecie tyle przestrzeni dyskowej, żeby to zrobić.

"obliczyć" czyli obliczyć \(\displaystyle{ 2 ^{x} }\) jakąś szybką metodą o ile taka istnieje. Pytanie dotyczy, czy jest jakiś sposób?

Dodano po 2 minutach 50 sekundach:
podać wartość x

Chodzi ci o algorytm szybkiego potęgowania?
Bo jeżeli chodzi o zapis w systemie dwójkowym to podana liczba to
\(\displaystyle{ 1000.....0_{2} }\) z \(\displaystyle{ 445}\)-cioma zerami. dzielenie przez \(\displaystyle{ 2}\) to zwykłe ucięcie jednego zera.

Dodano po 2 minutach 15 sekundach:
Operacja na liczbach z miliardem cyfr dziesiętnych robiłem. Zwykłe dzielenie trwało godziny.

podam przykład:
\(\displaystyle{ 2 ^{777176}}\) mod 398563072 = \(\displaystyle{ 2 ^{8} }\) , więc \(\displaystyle{ x=8}\).
Jak obliczyć x gdy potęga i dzielnik modulo, ma miliard cyfr w zapisie \(\displaystyle{ _{10}}\)

\(\displaystyle{ 398563072_{10}=1100000111110011010010000000_{2}}\)
Jak widać ostatnia jedynka na ósmej pozycji.

Dodano po 3 godzinach 38 minutach 18 sekundach:
\(\displaystyle{ \frac{777176}{8} =97 147}\)

Dodano po 3 minutach 16 sekundach:
\(\displaystyle{ \frac{398563072}{2^8} =1 556 887}\)

A co powiesz Brombal na taki przykład:
\(\displaystyle{ 2 ^{795343}}\) mod \(\displaystyle{ 1631448064 = 2 ^{31} }\) czyli \(\displaystyle{ x=31}\)
wtedy:
\(\displaystyle{ 1631448064 _{10} }\) \(\displaystyle{ = }\) \(\displaystyle{ 0110 0001 0011 1101 1110 1100 0000 0000 _{2}}\)
tutaj x= \(\displaystyle{ 10 \neq 31}\)

Dodano po 8 godzinach 4 minutach 23 sekundach:
błąd, zamiast mod \(\displaystyle{ 1631448064}\) powinno być mod \(\displaystyle{ 3262896128}\) ,wtedy \(\displaystyle{ x=11 \neq 31}\)

Z moich obliczeń wynika
\(\displaystyle{ 795343}\) taka reszta

podniosłeś faktycznie \(\displaystyle{ 2 ^{795343} }\) mod \(\displaystyle{ 3262896128}\) i obliczyłeś resztę? Jeżeli tak to moje założenie jest fałszywe

Sprawdzę jeszcze raz

Dodano po 4 godzinach 39 minutach 4 sekundach:
Sprawdziłem Twoje wyniki są prawidłowe.
Przeliczyłem bezpośrednio.
Pierwsza liczba ma \(\displaystyle{ 233954}\) cyfr i mod \(\displaystyle{ 256}\)
Druga liczba ma \(\displaystyle{ 239423}\) cyfr i mod \(\displaystyle{ 2147483648}\)
Pomyliłem się na szczęście.

Dodano po 12 godzinach 36 minutach 59 sekundach:

Kera pisze: 5 gru 2024, o 16:39 podniosłeś faktycznie \(\displaystyle{ 2 ^{795343} }\) mod \(\displaystyle{ 3262896128}\) i obliczyłeś resztę? Jeżeli tak to moje założenie jest fałszywe

Sprawdziłem bezpośrednio powyższe dane dla omyłkowego \(\displaystyle{ 326289612}\)
wynik to
\(\displaystyle{ 255023744}\) czyli \(\displaystyle{ 2^{7} \cdot 1992373 }\)
Poprawny wynik to \(\displaystyle{ 2147483648}\) czyli \(\displaystyle{ 2^{31}}\)