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

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

Jednym ze sposobów jest obliczenie poprzez obliczenie aproksymacji log 2 ( x ) z wystarczającą dokładnością. Wygląda na to, że obliczenie log 2 ( x ) z k bitów dokładności można wykonać w O ( M ( k ) log k ), gdzie M $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 k . Daje to (nie specjalnie prosty) algorytm złożoności w przybliżeniu O ( s log 2 s ), jeśli s jest ograniczeniem wielkości bitowej zarówno x, jaki n (jeśli nie popełniłem błędu).$M(k)$$k$$O(s\log^2 s)$$s$$x$$n$

Czy możemy pokonać gdzie s jest rozmiarem x i n (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.

[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ą k jest co najmniej tak trudne, jak obliczenie rozmiaru bitu x 2 k .$\log(x)$$k$$x^{2^k}$

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

Zatem . Teraz 2 k log ( x ) to log ( x ) przesunięte o k pozycje w lewo. Zatem można obliczyć log ( x ) z dokładnością k , po prostu odejmując 1 do rozmiaru bitu x 2 k i przesuwając wynikowe pozycje k 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$