Zastosowanie liczb adycznych w CS

11

Czy są jakieś konkretne (lub bogate źródło) przykłady zastosowania liczb adycznych w informatyce? $p$

survey T ....
źródło

p -numer seryjny / Wikipedia. stosowane w teorii liczb. nieco pośrednie, np. istnieje pewna analiza hipotezy Collatza zapomocą teorii p- adycznej, a niektórzy uważają, że Collatz jest głęboko powiązany z badaniami nierozstrzygalności TCS.

vzn

13

De, Kurur, Saha i Saptharishi podali modułową wersję algorytmu mnożenia liczb całkowitych Fürera w swoim artykule Szybkie mnożenie liczb całkowitych za pomocą arytmetyki modułowej , w którym liczby p-adyczne zastępują liczby zespolone używane przez Fürera. Oba algorytmy zapewniają najlepszą złożoność bitową dla mnożenia liczb całkowitych.

Yuval Filmus
źródło

To dobry przykład.

T ....

10

Podnoszenie Hensel jest bardzo blisko związane z adami: w zasadzie uzyskuje się coraz lepsze przybliżenie do liczby adycznej, „lepsze” w sensie „bliżej wartości adycznej. Podnoszenie Hensel jest używane w wielu algorytmach takich jak faktoring wielomianów lub wykonywanie algebry liniowej nad (jeśli dobrze pamiętam, Dixon ma artykuł na ten temat). $p$ $p$ $p$ $\mathbb{Z}$

Joshua Grochow
źródło

Z wielomianów w

nie możemy nic powiedzieć o reprezentacji w

. Dobrze?

Z_{p} [x]

$\Bbb Z_p[x]$

R [x]

$\Bbb R[x]$

T ....

1

@JA: Mało prawdopodobne (zakładam, że przez

masz na myśli liczby całkowite

). Być może jakiś związek między

i

(szczególnie jeśli rozważa się pytania nad wszystkimi

) lub między

i

... Zobacz zasadę Hasse'a: en.wikipedia.org/ wiki / Hasse_principle

Z_{p}

$\mathbb{Z}_p$

p

$p$

Q_{p} [x]

$\mathbb{Q}_p[x]$

R [x]

$\mathbb{R}[x]$

p

$p$

Z_{p} [x]

$\mathbb{Z}_p[x]$

Z [x]

$\mathbb{Z}[x]$

Joshua

tak,

-adyczne liczby całkowite.

p

$p$

T ....

Q_{p} [x]

$\Bbb Q_p[x]$

R [x]

$\Bbb R[x]$

@JA: Nie wiem - jeśli znajdziesz zastosowanie lub odniesienie do zastosowania, daj nam znać!

Joshua Grochow

6

Istnieją również niektóre modele obliczeniowe:

Oto pierwszy artykuł: Rusins Freivalds: Ultrametric automaty i maszyny Turinga. Turing-100 2012: 98-112

Abuzer Yakaryilmaz
źródło

4

tutaj jest ładna ankieta ogólna z krótkim przeglądem różnych (ostatnich) aplikacji CS do teorii p- adycznej, p3

Co to są liczby p-adyczne? Do czego są używane? / Rozikov

Oto obszary, w których dynamika p-adyczna okazała się skuteczna: informatyka (programy liniowe), analiza numeryczna i symulacje (liczby pseudolosowe), jednolity rozkład sekwencji, kryptografia (szyfry strumieniowe, funkcje T), kombinatoryka (kwadraty łacińskie) , teoria automatów i języki formalne, genetyka. Monografia [9] zawiera odpowiednią ankietę. Nowsze wyniki można znaleźć w najnowszych dokumentach i odnośnikach: [10, 14, 15, 28, 36, 37, 38, 48, 51]. Ponadto istnieją badania w dziedzinie informatyki i kryptografii, które wraz z fizyką matematyczną pobudziły w 1990 r. Intensywne badania nad dynamiką p-adyczną, ponieważ zaobserwowano, że główne instrukcje komputerowe (a zatem programy złożone z tych instrukcji) można uznać za ciągłe przekształcenia w odniesieniu do metryki 2-adycznej, patrz [11, 12].

vzn
źródło

Ciekawy. gdzie w programach liniowych jest używany?

T ....

1

Te również nie wydają się być głównym nurtem.

T ....

Zastosowanie liczb adycznych w CS

Odpowiedzi: