2 do potęgi x

[Kera]

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?

[a4karo]

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

[Kera]

"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

[Brombal]

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.

[Kera]

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}}\)

[Brombal]

\(\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}\)

[Kera]

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}\)

[Brombal]

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

[Kera]

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

[Brombal]

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:

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}}\)