为什么 λ- 微积分最优计算器能够在没有公式的情况下计算大的模幂？
教堂数字是将自然数作为函数进行编码。
(\ 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
巧妙地，你可以用两个教堂的数字来指数化它们。也就是说，如果你应用4到2，你会得到教堂编号 16，或者 2^4。显然，这是完全不切实际的。教堂的数字需要线性的内存，而且非常非常慢。计算像 10^10这样的东西—— GHCI 很快就能正确地回答这个问题——需要很长时间，而且无论如何也无法在你的计算机上安装内存。
我最近一直在尝试使用最优 λ 计算器，在我的测试中，我不小心在最优 λ- 计算器上输入了以下内容:
10 ^ 10 % 13
应该是乘法，而不是求幂。在我绝望地动动手指终止这个永远运行的程序之前，它回应了我的请求:
3
{ iterations: 11523, applications: 5748, used_memory: 27729 }
real 0m0.104s
user 0m0.086s
sys 0m0.019s
随着我的“错误警报”闪烁，我去谷歌和验证，确实 10^10%13 == 3。为了科学，我开始强调它。它立即回答我 20^20%13 == 3，50^50%13 == 4，60^60%3 == 0。我必须使用 外部工具来验证这些结果，因为使用的是 Haskell 本身无法计算它(由于整数溢出)(当然是使用整数而不是整数!).把它推到极限，这就是对 200^200%31的回答:
5
{ iterations: 10351327, applications: 5175644, used_memory: 23754870 }
real 0m4.025s
user 0m3.686s
sys 0m0.341s
如果我们对于宇宙中的每个原子都有一个宇宙的拷贝，并且对于我们总共拥有的每个原子都有一台计算机，我们就不能存储教会编号 200^200。这促使我质疑我的 Mac 是否真的那么强大。也许最优的求值器能够跳过不必要的分支，并以 Haskell 使用惰性求值的相同方式得到正确的结果。为了测试这一点，我编译了 λ 程序到 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)
这正确输出 1(5 ^ 5 % 4)-但抛出任何高于 10^10和它将被卡住，消除假设。
我用的最佳评估器是一个长达160行的未经优化的 JavaScript 程序，它没有包含任何指数模数学——我使用的 lambda 微积分模函数也同样简单:
(λ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))))))
我没有使用特定的同余关系算法或公式
最佳答案