Czy możemy obliczyć

Szukam wydajnego algorytmu dla problemu:

Wejście : dodatnia liczba całkowita $3^n$ (zapisana w bitach) dla jakiejś liczby całkowitej $n \geq 0$ .

Wyjście : liczba $n$ .

Pytanie : Czy możemy obliczyć $n$ na podstawie bitów $3^n$ w czasie $O(n)$ ?

To jest teoretyczne pytanie motywowane moją odpowiedzią na pytanie matematyczne. SE Jak znaleźć wzór na ten bijection? . W tym pytaniu autor chciał znaleźć bijection z

{{2)}^{n} {3)}^{m} : n \geq 0 i m \geq 0}

$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$ oraz liczb naturalnych

N = {1, 2, \dots}

$\mathbb{N}=\{1,2,\ldots\}$ . Zaproponowałem

{2)}^{m} {3)}^{n} \mapsto {2)}^{m} (2) n + 1)

$2^m 3^n \mapsto 2^m(2n+1)$ jako rozwiązanie. Inna odpowiedź brzmiała: „nie ma prostej formuły”, co sprawia, że zastanawiam się, jak (obliczeniowo) proste jest moje proponowane rozwiązanie.

W moim proponowanym rozwiązaniu, jeśli znamy $n$ i $m$ , możemy łatwo obliczyć $2^m(2n+1)$ (napisz binarne cyfry $n$ a następnie $1$ a następnie $m$ zera). Zajmuje to czas $O(n+m)$ .

Znalezienie z bitów równoznaczne ze znalezieniem najmniej znaczącego bitu (który można obliczyć, zliczając przesunięcia odpowiednich bitów, pozostawiając w pamięci). Zajmuje to czas . $m$ $2^m 3^n$ $3^n$ $O(m)$

Musimy jednak również znaleźć , co może być trudniejsze. Można byłoby znaleźć poprzez wielokrotne dzielenie przez , ale wydaje się to marnotrawstwem. Wymaga operacji dzielenia, z których każda zajmie czas , więc w sumie jest to czas . [Właściwie po każdej iteracji liczba cyfr będzie zmniejszać się liniowo, ale nadal powoduje to czas .] $n$ $n$ $3$ $n$ $O(n)$ $O(n^2)$ $O(n^2)$

Wydaje się, że powinniśmy być w stanie wykorzystać wiedząc, że wkład to potęga . $3$

ds.algorithms time-complexity Rebecca J. Stones
źródło

Jaki jest twój dokładny model obliczeń? Jakie operacje są dozwolone w czasie

? (Gdybyśmy mogli wykonywać arytmetykę z liczbami takimi jak

, byłoby to całkiem przydatne ...)

O (1)

$O(1)$

\log_{2} 3

$\log_2 3$

Yuval Filmus,

Czy downvoter może wyjaśnić downvote? To wcale nie wydaje się trywialne pytanie. Jaki jest najlepszy czas działania w rozsądnym modelu obliczeniowym?

Yuval Filmus,

Wyobrażam sobie taśmy z zerami, 1 i pustymi komórkami (z nieskończoną liczbą taśm). Chcę, aby jednobitowe operacje przełączania i lewe / prawe operacje działały w czasie

. (Jeśli mamy znacznik 0-ty bit na nieskończonej taśmie, wówczas przesunięcie w lewo / prawo osiąga się poprzez przesunięcie znacznika). W przeciwieństwie do maszyny Turinga nie chcę, aby przesuwanie wskaźnika trwało dłużej. Zatem „przełączanie 0-tego bitu” zajmuje tyle samo czasu, co „przełączanie 124126-tego bitu”.

O (1)

$O(1)$

Rebecca J. Stones,

Może to być w jakiś sposób związane z tym pytaniem

J.-E.

Czy dolna granica

oczywista?

Ω (n)

$\Omega(n)$

Boris Bukh,

Odpowiedzi:

Oczywistym podejściem jest:

(1) Oblicz przybliżenie do . Możesz go zbliżyć do błędu addytywnego 1, zliczając liczbę bitów w danej reprezentacji binarnej, i do błędu addytywnego , dodatkowo patrząc na górne $\log_2(3^n)$ $\epsilon$ bity wejścia. Powinny wystarczyć, aby wybrać stałą wartość, tak że (po połączeniu z błędem w etapie (2)) końcowe końców wynik w ciągu addytywnej błęduprawidłowych. $O(\log\frac{1}{\epsilon})$ $\epsilon$ $1/2$

(2) Oblicz przybliżenie do . Nie znam algorytmów do tego, ale spodziewam się, że wymagają one wielomianu czasu w liczbie potrzebnych bitów precyzji, a potrzebujesz tylko bitów precyzji. $\log_2(3)$ $O(\log n)$

(3) Podziel odpowiedź na (1) przez odpowiedź na (2) i zaokrąglij do najbliższej liczby całkowitej.

Tak więc pierwszy krok zajmuje czas liniowy (w większości modeli obliczeniowych, chociaż może nie dla niektórych słabych mocy, takich jak maszyny Turinga z pojedynczą głowicą ), a pozostałe kroki powinny być polilogarytmiczne.

David Eppstein
źródło

Uważam, że obliczenie

bitów precyzji wymaga czasu

, gdzie

jest czasem pomnożenia

bit liczby. Zobacz Brent - Zimmermann, loria.fr/~zimmerma/mca/pub226.html

\log_{2} (3)

$\log_2(3)$

t

$t$

O (M (t) \log t)

$O(M(t) \log t)$

M (t) \leq O (t \log t 2^{\log^{*} t})

$M(t) \leq O(t \log t 2^{\log^* t})$

t

$t$

Ryan O'Donnell,

Dzięki za referencje i przepraszam, że jestem zbyt leniwy, by sam to sprawdzić.

David Eppstein,

Dla dowolnej liczby całkowitej zapisanie systemie binarnym wymaga dokładnie bitów. Niektóre elementarne algebry sugerują, że $n>0$ $3^n$ $L = \lceil \log_2(3^n)+1\rceil$ Dla dowolnej długości bituw tym zakresie znajduje się co najwyżej jedna liczba całkowita. Zatem, biorąc pod uwagę całkowitą potęgęktóra madługośćbitów, wykładnik musi być liczbą całkowitą

\frac{L - 2}{\log_{2} 3} \leq n \leq \frac{L - 1}{\log_{2} 3} .

$\frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}.$

L \geq 1

$L\ge 1$

3

$3$

L

$L$

n = ⌊ \frac{L - 1}{\log_{2} 3} ⌋ .

$n = \left\lfloor\frac{L-1}{\log_2 3}\right\rfloor.$

Jeffε
źródło

Oto inne podejście. Biorąc pod uwagę niskie cyfry , możesz nauczyć się a zatem . Wygląda na to, że to moduł generatora (tj. ma porządek ). $k$ $3^n$ $3^n \bmod 10^k$ $3^n \bmod 5^k$ $3$ $5^k$ $3$ $\varphi(5^k)=5^{k-1} \times 4$

Dlatego, używając dyskretnego dziennika i podnoszenia Hensela, myślę, że powinieneś być w stanie bardzo skutecznie obliczyć z niskich cyfr . Innymi słowy, zaczynasz od obliczenia od niskiej cyfry , poprzez przeniesienie logu dyskretnego do podstawy , modulo ; to ujawnia i można to zrobić w $n \bmod \varphi(5^k)$ $k$ $3^n$ $n \bmod 4$ $3^n$ $3^n \bmod 5$ $3$ $5$ $n \bmod 4$ $O(1)$ czas. Następnie znajdziesz dyskretny log do podstawy , modulo ; ujawnia to i można to zrobić w czasie (korzystając z wiedzy , jest tylko możliwości, które musisz wypróbować). Powtarzać. Na każdym kroku korzystasz z wiedzy aby pomóc ci wydajnie obliczyć log dyskretny $3^n \bmod 25$ $e$ $25$ $n \bmod 20$ $O(1)$ $n \bmod 4$ $5$ $n \bmod \varphi(5^{k-1})$ , wykorzystując fakt, że istnieje tylko możliwych wartości dla . $3^n \bmod 5^k$ $5$ $n \bmod \varphi(5^k)$

Teraz po prostu niech będzie wystarczająco duże, a to ujawni . $k$ $n$

Musisz dowiedzieć się, czy czas działania wynosi , ale wydaje mi się, że tak może być. Podejrzewam, że wystarczy pozwolić i podejrzewam, że możesz wykonać każdą iterację w czasie , łącznie przez czas . $O(n)$ $k=O(n)$ $O(1)$ $O(n)$

DW
źródło