[algorithm] Perché i valutatori ottimali di λ-calcolo sono in grado di calcolare grandi esponenziamenti modulari senza formule?



0 Answers

Questo non è un ansiere ma è un suggerimento su dove si potrebbe iniziare a guardare.

C'è un modo banale per calcolare gli esponenziati modulari in poco spazio, in particolare riscrivendo

(a * x ^ y) % z

come

(((a * x) % z) * x ^ (y - 1)) % z

Se un valutatore valuta come questo e mantiene il parametro di accumulo a in una forma normale, eviterete di usare troppo spazio. Se in effetti il ​​tuo valutatore è ottimale, presumibilmente non deve fare più lavoro di questo, quindi in particolare non può usare più spazio del tempo che questo richiede per valutare.

Non sono proprio sicuro di cosa sia veramente un valutatore ottimale quindi temo di non renderlo più rigoroso.

Question

I numeri di chiesa sono una codifica di numeri naturali come funzioni.

(\ f x → (f x))             -- church number 1
(\ f x → (f (f (f x))))     -- church number 3
(\ f x → (f (f (f (f x))))) -- church number 4

Ordinariamente puoi esponenziare 2 numeri di chiesa semplicemente applicandoli. Cioè, se si applica 4 a 2, si ottiene il numero di Chiesa 16 , o 2^4 . Ovviamente, questo è assolutamente non pratico. I numeri di chiesa hanno bisogno di una quantità lineare di memoria e sono veramente, molto lenti. Calcolare qualcosa come 10^10 - che GHCI risponde velocemente in modo corretto - richiederebbe anni e non potrebbe comunque adattarsi alla memoria del tuo computer.

Ultimamente sto sperimentando con i valutatori λ ottimali. Durante i miei test, ho accidentalmente digitato quanto segue sul mio calcolatore λ ottimale:

10 ^ 10 % 13

Doveva essere moltiplicazione, non esponenziale. Prima che potessi muovere le dita per interrompere il programma perennemente disperato, rispose alla mia richiesta:

3
{ iterations: 11523, applications: 5748, used_memory: 27729 }

real    0m0.104s
user    0m0.086s
sys     0m0.019s

Con il mio "bug alert" lampeggiante, sono andato su Google e ho verificato, 10^10%13 == 3 effetti. Ma il calcolatore λ non avrebbe dovuto trovare quel risultato, può a malapena memorizzare 10 ^ 10. Ho iniziato a sottolinearlo, per la scienza. Mi ha risposto immediatamente 20^20%13 == 3 , 50^50%13 == 4 , 60^60%3 == 0 . Ho dovuto usare strumenti esterni per verificare quei risultati, dal momento che Haskell non era in grado di calcolarlo (a causa dell'overflow dei numeri interi) (lo è se usi Integers not Ints, ovviamente!). Spingendola al limite, questa è stata la risposta al 200^200%31 :

5
{ iterations: 10351327, applications: 5175644, used_memory: 23754870 }

real    0m4.025s
user    0m3.686s
sys 0m0.341s

Se avessimo una copia dell'universo per ogni atomo dell'universo e avessimo un computer per ogni atomo che avevamo in totale, non potemmo memorizzare il numero della chiesa 200^200 . Questo mi ha spinto a chiedermi se il mio Mac fosse davvero così potente. Forse il valutatore ottimale è stato in grado di saltare i rami inutili e arrivare proprio alla risposta nello stesso modo che Haskell fa con la valutazione pigra. Per verificarlo, ho compilato il programma λ per Haskell:

data Term = F !(Term -> Term) | N !Double
instance Show Term where {
    show (N x) = "(N "++(if fromIntegral (floor x) == x then show (floor x) else show x)++")";
    show (F _) = "(λ...)"}
infixl 0 #
(F f) # x = f x
churchNum = F(\(N n)->F(\f->F(\x->if n<=0 then x else (f#(churchNum#(N(n-1))#f#x)))))
expMod    = (F(\v0->(F(\v1->(F(\v2->((((((churchNum # v2) # (F(\v3->(F(\v4->(v3 # (F(\v5->((v4 # (F(\v6->(F(\v7->(v6 # ((v5 # v6) # v7))))))) # v5))))))))) # (F(\v3->(v3 # (F(\v4->(F(\v5->v5)))))))) # (F(\v3->((((churchNum # v1) # (churchNum # v0)) # ((((churchNum # v2) # (F(\v4->(F(\v5->(F(\v6->(v4 # (F(\v7->((v5 # v7) # v6))))))))))) # (F(\v4->v4))) # (F(\v4->(F(\v5->(v5 # v4))))))) # ((((churchNum # v2) # (F(\v4->(F(\v5->v4))))) # (F(\v4->v4))) # (F(\v4->v4))))))) # (F(\v3->(((F(\(N x)->F(\(N y)->N(x+y)))) # v3) # (N 1))))) # (N 0))))))))
main = print $ (expMod # N 5 # N 5 # N 4)

Questo produce correttamente 1 ( 5 ^ 5 % 4 ) - ma getta qualcosa sopra 10^10 e sarà bloccato, eliminando l'ipotesi.

Il valutatore ottimale che ho usato è un programma JavaScript di 160 righe non ottimizzato che non includeva alcun tipo di matematica esponenziale del modulo e la funzione del modulo lambda-calcolo che ho usato era altrettanto semplice:

(λab.(b(λcd.(c(λe.(d(λfg.(f(efg)))e))))(λc.(c(λde.e)))(λc.(a(b(λdef.(d(λg.(egf))))(λd.d)(λde.(ed)))(b(λde.d)(λd.d)(λd.d))))))

Non ho usato alcun algoritmo o formula aritmetica modulare specifica. Quindi, qual è il valutatore ottimale in grado di arrivare alle risposte giuste?




Related