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)$

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

Odpowiedzi: