Obliczanie liczby bitów dużej potęgi liczby całkowitej

Biorąc pod uwagę dwie liczby całkowite i w reprezentacji binarnej, jaka jest złożoność obliczania wielkości bitowej ? $x$ $n$ $x^n$

Jednym ze sposobów jest obliczenie poprzez obliczenie aproksymacji z wystarczającą dokładnością. Wygląda na to, że obliczenie z bitów dokładności można wykonać w gdzie $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor n\log_2(x)\rfloor$ $\log_2(x)$ $\log_2(x)$ $k$ $O(M(k)\log k)$ oznacza czas potrzebny do obliczenia iloczynu dwóch liczb całkowitych o długości . Daje to (nie specjalnie prosty) algorytm złożoności w przybliżeniu jeśli jest ograniczeniem wielkości bitowej zarówno jaki (jeśli nie popełniłem błędu). $M(k)$ $k$ $O(s\log^2 s)$ $s$ $x$ $n$

Czy możemy pokonać gdzie jest rozmiarem i (w przypadku, gdy mają one porównywalne rozmiary)? Czy istnieje prosty algorytm pozwalający uzyskać tę złożoność lub lepszą? $O(s\log^2(s))$ $s$ $x$ $n$

Uwaga: Interesuje mnie złożoność modelu teoretycznego, takiego jak maszyny Turinga.

complexity-theory time-complexity binary-arithmetic

— Bruno
źródło

Proponuję migracji / "promowanie" to Theoretical Computer Science

— vzn

@vzn: Nie sądzę, żeby to było przydatne ...

— Bruno,

Dlaczego nie? to pytanie przypomina mi algorytmiczne ataki na hipotezę Dysona, np. takie jak objęte przez RJLipton w 1 , 2

— od

Po prostu dlatego, że znalazłem odpowiedź na moje pytanie, więc nie muszę zadawać jej w innym miejscu.

— Bruno

[edytuj] Zgodnie z sugestią, edytuję swoją odpowiedź, aby podać więcej szczegółów.

Odpowiedź na drugie pytanie jest moim nr :

Propozycja. Obliczenie z dokładnością jest co najmniej tak trudne, jak obliczenie rozmiaru bitu . $\log(x)$ $k$ $x^{2^k}$

Dowód. Niech oznacza rozmiar bitu liczby całkowitej . Najpierw zauważ, że dla nieujemnej liczby całkowitej rozmiar bitu wynosi . $|y|$ $y$ $y$ $y$ $1+\lfloor \log y\rfloor$

Zatem . Teraz to przesunięte o pozycje w lewo. Zatem można obliczyć z dokładnością , po prostu odejmując do rozmiaru bitu i przesuwając pozycje w prawo. $\left|x^{2^k}\right| = 1+\lfloor 2^k\log x\rfloor$ $2^k\log(x)$ $\log(x)$ $k$ $\log(x)$ $k$ $1$ $x^{2^k}$ $k$

— Bruno
źródło

Dlaczego liczba bitów w

umożliwia obliczenie

bitów precyzji? Czy Twoja redukcja faktycznie działa? Co jeśli specjalny przypadek, w którym

był znacznie łatwiejszy / trudniejszy niż wszystkie inne możliwe wartości

(nie-potęgi-dwóch)? Czy potrafisz wykluczyć tę możliwość?

x^{2^{k}}

$x^{2^k}$

\log x

$\log x$

k

$k$

n = 2^{k}

$n=2^k$

n

$n$

— DW

@DW: Wracam do tego pytania, po komentarzu vzn. Mój dowód jest następujący: Liczba bitów liczby całkowitej

wynosi

. Zatem liczba bitów w

wynosi

. Ponadto

jest taki sam jak

ale przesunięto pozycje

w lewo. Zatem

daje (przynajmniej)

pierwszych bitów

y

$y$

1 + ⌊ \log y ⌋

$1+\lfloor\log y\rfloor$

x^{2^{k}}

$x^{2^k}$

1 + ⌊ 2^{k} \log x ⌋

$1+\lfloor 2^k\log x\rfloor$

2^{k} \log x

$2^k\log x$

\log x

$\log x$

k

$k$

⌊ 2^{k} \log x ⌋

$\lfloor 2^k\log x\rfloor$

k

$k$

. Zatem jeśli możesz obliczyć liczbę bitów

, odejmując

od wyniku, otrzymujesz pierwsze

bitów

. Czy to ma sens?

\log x

$\log x$

x^{2^{k}}

$x^{2^k}$

1

$1$

k

$k$

\log x

$\log x$

— Bruno,

Tak, to ma dla mnie większy sens! Zwłaszcza, że próbujesz tylko wykazać twardość. Czy mogę zachęcić cię do zaktualizowania odpowiedzi za pomocą tego bardziej szczegółowego wyjaśnienia? Dziękujemy za powrót do tej kwestii i udokumentowanie odpowiedzi na własne pytanie.

— DW