Jak blisko liniowego mnożenia, dodawania i porównywania (na liczbach całkowitych)?

Nawiązując do artykułu KW Regana „Połącz gwiazdy” , na końcu wspomina, że wciąż otwartym problemem jest znalezienie reprezentacji liczb całkowitych, tak że operacje dodawania, mnożenia i porównywania można obliczać w czasie liniowym:

Czy istnieje reprezentacja liczb całkowitych, aby dodawanie, mnożenie i porównywanie były wykonalne w czasie liniowym? Zasadniczo, czy istnieje liniowy czas dyskretnie uporządkowany pierścień?

(1) Jak blisko możemy zbliżyć się do liniowego mnożenia i dodawania czasu bez porównywania? Zakładam, że rozmiary problemów mogą się różnić, dlatego potrzebujemy struktury danych / algorytmu, który umożliwia zmianę rozmiarów liczb całkowitych.

(2) W przypadku pełnego problemu możemy założyć, że znajdziemy optymalny schemat mnożenia, dodawania i porównywania liczb całkowitych. Jak bardzo zbliżamy się do najwolniejszej z tych trzech operacji (w najgorszym przypadku) względem czasu liniowego? A w tej notatce, jak szybkie byłyby inne operacje?

FORMALNE OŚWIADCZENIE O PROBLEMACH

Jak wspomina Emil Jeřábek, chcielibyśmy wykluczyć trywialne przypadki i skoncentrować się na najgorszym przypadku tego pytania.

Pytamy więc, dla nieujemnych liczb całkowitych i gdzie i , czy możemy znaleźć strukturę danych / algorytm, który może wykonywać dodawanie, mnożenie i porównywać z \ między i w czasie i przestrzeni ? $\forall x$ $\forall y$ $0 \le x < n$ $0 \le y < n$ $x$ $y$ $O(n \log{(n)})$ $O(\log^2{(n)})$

ds.algorithms ds.data-structures worst-case

— Matt Groff
źródło

Wspomnę, że możliwe jest stworzenie schematu, który wykonuje te operacje w czasie

na nieujemnych liczbach całkowitych, gdzie

jest bitem największej liczby całkowitej (zakładając, że znamy

wcześniej). Zastanawiam się, czy możemy to zrobić lepiej i zrobić to w czasie proporcjonalnym do obliczanych bieżących liczb całkowitych.

Θ (n)

$\Theta(n)$

n

$n$

n

$n$

— Matt Groff,

@TysonWilliams: Tak! Dwójkowy!

— Jeffε

O (n \log n)

$O(n\log n)$

n^{2}

$n^2$

n

$n$

f (n)

$f(n)$

f (n) = Θ (\log n)

$f(n)=\Theta(\log n)$

$n$

p_{n} # = \exp ((1 + o (1)) n \log n) .

$p_n\# =\exp((1+\mathcal{o}(1) )n\log n).$

N

$N$

n

$n$

N < \exp ((1 + o (1)) n \log n)

$N<\exp((1+\mathcal{o}(1) )n\log n)$

N < p_{n} #

$N<p_n\#$

n

$n$

n \log n \propto \log (N)

$n \log n \propto \log(N)$

n

$n$

n \log (n)

$n\log(n)$

O (n \log \log (N))

$O(n\log\log(N))$

O (n \log \log (N) \log \log \log \log (N) \log \log \log (N))

$O(n\log\log(N)\log\log\log\log(N)\log\log\log(N))$

n \log n \propto \log N

$n \log n \propto \log N$

n

$n$

O (\log N / \log \log N)

$O(\log N/\log\log N)$

O (\log N)

$O(\log N)$

O (\log N \log \log \log N \log \log \log \log N)

$O(\log N \log\log\log N \log\log\log\log N)$

— Joe Fitzsimons
źródło

patrz także twierdzenie o chińskiej reszcie

— wer

@vzn: Tak, chciałem wspomnieć o tym dla porównań, ale potem przyszło mi do głowy, że może być szybsza operacja porównania dzięki mieszanej reprezentacji radix.

— Joe Fitzsimons