Algorytmy oparte na systemach liczbowych? [Zamknięte]

Niedawno zauważyłem, że istnieje bardzo wiele algorytmów opartych częściowo lub w całości na sprytnym wykorzystaniu liczb w kreatywnych podstawach. Na przykład:

• Sterty dwumianowe są oparte na liczbach binarnych, a bardziej złożone sterty dwumianowe skośne są oparte na liczbach binarnych skośnych.
• Niektóre algorytmy generowania permutacji uporządkowanych leksykograficznie są oparte na systemie liczb czynnikadowych.
• O próbach można myśleć jako o drzewach, które sprawdzają jedną cyfrę ciągu na raz, aby uzyskać odpowiednią podstawę.
• Drzewa kodowania Huffmana są zaprojektowane tak, aby każda krawędź w drzewie kodowała zero lub jeden w jakiejś binarnej reprezentacji.
• Kodowanie Fibonacciego jest używane w wyszukiwaniu Fibonacciego i do odwracania pewnych typów logarytmów.

Moje pytanie brzmi: jakie inne algorytmy są dostępne, które wykorzystują sprytny system liczbowy jako kluczowy krok w ich intuicji lub dowodzie? . Zastanawiam się nad zebraniem wykładu na ten temat, więc im więcej przykładów będę musiał czerpać, tym lepiej.

Chris Okasaki ma bardzo dobry rozdział w swojej książce „ Purely Functional Data Structures ” („ czysto funkcjonalne struktury danych”), w którym omawia się „numeryczne reprezentacje”: zasadniczo należy wziąć pewną reprezentację liczby i przekształcić ją w strukturę danych. Aby nadać smaku, oto sekcje tego rozdziału:

1. Systemy liczb pozycyjnych
2. Liczby binarne (binarne listy o swobodnym dostępie, reprezentacje bez zera, reprezentacje leniwe, reprezentacje segmentowane)
3. Pochylone liczby binarne (pochylone binarne losowe listy dostępu, pochylone dwumianowe stosy)
4. Liczby trójdzielne i czwartorzędowe

Niektóre z najlepszych trików, destylowane:

• Rozróżnij gęstą i rzadką reprezentację liczb (zwykle widzisz to w macierzach lub wykresach, ale ma to również zastosowanie do liczb!)
• Przydatne są nadmiarowe systemy liczbowe (systemy, które mają więcej niż jedną reprezentację liczby).
• Jeśli ustawisz pierwszą cyfrę na niezerową lub użyjesz reprezentacji bez zera, pobranie nagłówka struktury danych może być wydajne.
• Unikaj kaskadowych pożyczek (od zajmowania końca listy) i przenoszonych (od konsulowania na listę) poprzez segmentację struktury danych

Oto lista referencyjna do tego rozdziału:

• Guibas, McCreight, Plass i Roberts: Nowa reprezentacja list liniowych.
• Myers: stosowny stos o swobodnym dostępie
• Carlsson, Munro, Poblete: niejawna kolejka dwumianowa ze stałym czasem wstawiania.
• Kaplan, Tarjan: Czysto funkcjonalne listy z katenacją poprzez rekurencyjne spowolnienie.

„Liczby trójskładnikowe mogą być używane do wygodnego przekazywania samopodobnych struktur, takich jak trójkąt Sierpińskiego lub zbiór Cantora”. źródło

„Liczby czwartorzędowe są używane do reprezentacji krzywych 2D Hilberta”. źródło

„Quater-urojony system liczbowy został po raz pierwszy zaproponowany przez Donalda Knutha w 1955 r. W ramach badania talentów naukowych w liceum. Jest to niestandardowy system liczb pozycyjnych, który opiera się na liczbie urojonej 2i. Jest w stanie reprezentować każdą liczbę zespoloną za pomocą tylko cyfr 0, 1, 2 i 3. " źródło

„Cyfry rzymskie to system binarny”. źródło

"Senary może być uważany za przydatny w badaniu liczb pierwszych, ponieważ wszystkie liczby pierwsze, wyrażone w szóstce o podstawie, inne niż 2 i 3, mają 1 lub 5 jako ostatnią cyfrę." źródło

„Sześćdziesiątkowy (podstawa 60) to system liczbowy, którego podstawą jest sześćdziesiąt. Pochodzi z starożytnych Sumerów w 3. tysiącleciu pne, został przekazany starożytnym Babilończykom i nadal jest używany - w zmodyfikowanej formie - do pomiaru czas, kąty i współrzędne geograficzne, które są kątami. " źródło

itp...

Ta lista jest dobrym punktem wyjścia.

Przeczytałem twoje pytanie niedawno i dziś stanąłem przed problemem: Jak wygenerować wszystkie partycje zbioru? Rozwiązanie, które przyszło mi do głowy i którego użyłem (może z powodu przeczytania twojego pytania) było następujące:

W przypadku zestawu z (n) elementami, gdzie potrzebuję (p) partycji, policz wszystkie (n) cyfry w bazie (p).

Każda liczba odpowiada partycjonowaniu. Każda cyfra odpowiada elementowi w zestawie, a wartość cyfry określa, w której partycji należy umieścić element.

To nie jest niesamowite, ale jest fajne. Jest kompletny, nie powoduje nadmiarowości i korzysta z dowolnych zasad. Używana podstawa zależy od konkretnego problemu z partycjonowaniem.

Niedawno natknąłem się na fajny algorytm do generowania podzbiorów w porządku leksykograficznym w oparciu o binarne reprezentacje liczb od 0 do 2 ⁿ - 1. Używa on bitów liczb zarówno do określenia, które elementy powinny zostać wybrane do zbioru, jak i do lokalnej zmiany kolejności wygenerowane zbiory, aby ustawić je w porządku leksykograficznym. Jeśli jesteś ciekawy, mam tutaj wpis .

Ponadto wiele algorytmów opiera się na skalowaniu (np. Słabo wielomianowa wersja algorytmu maksymalnego przepływu Forda-Fulkersona), która wykorzystuje binarną reprezentację liczb w zadaniu wejściowym, aby stopniowo zawęzić przybliżone przybliżenie do pełnego rozwiązania.

Niezupełnie sprytny system bazowy, ale sprytne wykorzystanie systemu podstawowego: sekwencje Van der Corputa to sekwencje o niskiej rozbieżności utworzone przez odwrócenie reprezentacji liczb w podstawie n. Są one wykorzystywane do budowy 2-d sekwencje Halton , które wyglądają trochę jak ten .

Niewyraźnie pamiętam coś o systemach z podwójną podstawą do przyspieszenia mnożenia macierzy.

System z podwójną podstawą to system redundantny, który wykorzystuje dwie bazy dla jednego numeru.

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

Nadmiarowość oznacza, że ​​jedną liczbę można określić na wiele sposobów.

Możesz poszukać artykułu „Hybrid Algorithm for the Computation of the Matrix Polynomial” autorstwa Vassila Dimitrova, Todora Cookleva.

Staram się jak najlepiej przedstawić krótki przegląd.

Próbowali obliczyć wielomian macierzy G(N,A) = I + A + ... + A^{N-1}.

Zakładając, że N jest złożone G(N,A) = G(J,A) * G(K, A^J), jeśli zastosujemy J = 2, otrzymamy:

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

również,

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

Ponieważ jest "oczywiste" (żartobliwie), że niektóre z tych równań są szybkie w pierwszym układzie, a inne lepsze w drugim - więc dobrze jest wybrać najlepsze z tych w zależności od N. Ale wymagałoby to szybkiej operacji modulo zarówno dla 2, jak i 3. Oto dlaczego pojawia się podwójna podstawa - w zasadzie możesz szybko wykonać operację modulo dla obu z nich, dając połączony system:

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

Zapoznaj się z artykułem, aby uzyskać lepsze wyjaśnienie, ponieważ nie jestem ekspertem w tej dziedzinie.

RadixSort może korzystać z różnych baz liczbowych. http://en.wikipedia.org/wiki/Radix_sort Całkiem ciekawa implementacja bucketSort.

tutaj jest dobry post na temat wykorzystania liczb trójskładnikowych do rozwiązania problemu „fałszywej monety” (gdzie trzeba wykryć jedną fałszywą monetę w woreczku zwykłych monet, używając salda jak najwięcej razy)

Ciągi haszujące (np. W algorytmie Rabina-Karpa ) często oceniają łańcuch jako liczbę o podstawie b składającej się z n cyfr (gdzie n to długość łańcucha, a b to jakaś wybrana podstawa, która jest wystarczająco duża). Na przykład ciąg „ABCD” można zaszyfrować jako:

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

Podstawiając wartości ASCII dla znaków i przyjmując b równe 256 otrzymujemy,

65*256^3+66*256^2+67*256^1+68*256^0

Chociaż w większości praktycznych zastosowań wynikowa wartość jest przyjmowana jako modulo pewnej rozsądnej liczby, aby wynik był wystarczająco mały.

Potęgowanie przez podniesienie do kwadratu opiera się na binarnej reprezentacji wykładnika.

W Hackers Delight(książce, którą każdy programista powinien znać w moich oczach) jest pełny rozdział o nietypowych zasadach, takich jak -2 jako podstawa (tak, prawe ujemne podstawy) lub -1 + i (i jako wyimaginowana jednostka sqrt (-1)) jako baza. Również ładnie obliczyłem, jaka jest najlepsza podstawa (pod względem projektu sprzętu, dla wszystkich, którzy nie chcą tego czytać: Rozwiązanie równania to e, więc możesz iść z 2 lub 3, 3 byłoby trochę lepsze (współczynnik 1,056 razy lepsze niż 2) - ale jest bardziej praktyczne pod względem technicznym).

Inne rzeczy, które przychodzą mi do głowy to szary licznik (licząc w tym systemie tylko 1 bitowe zmiany, często używasz tej właściwości w projektowaniu sprzętu, aby zmniejszyć problemy z metastabilnością) lub uogólnienie wspomnianego już kodowania Huffmanna - kodowanie arytmetyczne.

Kryptografia szeroko wykorzystuje pierścienie liczb całkowitych (arytmatyka modularna), a także pola skończone, których operacje są intuicyjnie oparte na sposobie zachowania wielomianów o współczynnikach całkowitych.

Bardzo podoba mi się ten do konwersji liczb binarnych na kody Graya: http://www.matrixlab-examples.com/gray-code.html

Świetne pytanie. Lista jest rzeczywiście długa. Czas wskazania to prosty przykład mieszanych zasad (dni | godziny | minuty | sekundy | am / pm)

Stworzyłem strukturę n-tuple wyliczania meta-base, jeśli chcesz o tym usłyszeć. To bardzo słodki cukier syntaktyczny do systemów numeracji zasad. Nie jest jeszcze wydany. Wyślij moją nazwę użytkownika (na gmail).

Jednym z moich ulubionych przy użyciu podstawy 2 jest kodowanie arytmetyczne . Jest to niezwykłe, ponieważ serce algorytmu używa reprezentacji liczb od 0 do 1 w systemie binarnym.

Może tak jest w przypadku AKS .