Haskell如何即时计算这个庞大的数字？ [英] How does Haskell compute this enormous number instantly?

问题描述

我开始学习Haskell，当我学习一种新语言时，我喜欢做的事情之一是做项目欧拉问题作为我的主要参考材料的补充。

我找到了以下解决方案来找到第二个问题的总和即使斐波那契数字少于四百万：

  fibs = 0：1：zipWith（+）fibs（tail fibs）
f :: Integer  - >整数
fn = 
让evenFib = filter（\\\
-> n`mod` 2 == 0）fibs 
 in sum（takeWhile（< n）evenFib）
  

f 4000000 会返回正确答案。它瞬间完成。好奇的是，我开始输入越来越大的数字......

  Prelude> f 40000000 
 19544084 
前奏> f 400000000000 
 478361013020 
前奏> f 40000000000000000000000000000000 
 13049874051046942401006156573274 
 Prelude> f 2370498572349582734598273495872349587234958273495872349587234958723948752394857 
 2805750129675962215536​​656398462489370528480907433875715844 
  

这些值都会立即返回。我无法保证最后两个答案的准确性，因为我的其他语言的实现不适用于这么大的数字。

所以，我的问题是， Haskell在这里做什么？它是如何即时返回这些值（不管它们是否正确）？而且，这些答案确实是正确的，还是Haskell只是在做点什么？

解决方案

Haskell可能没有特别的问题，但是您使用其他解决方案的算法。

由于斐波纳契数字增长很快（每一步平均增加1.6倍），所以斐波纳契数字不会少于4000000000000000000000000000，可能少于100美元。

$ b

添加少于100个这种大小的数字（不是特别大）的计算机应该需要几微秒。

我不确定你的其他实现是什么样的，但是一个常见的错误是编写这样的Fibonacci函数：

  fib 0 = 0 
 fib 1 = 1 
 fib n = fib（n-1）+ fib（n-2）
  

这太可怕了，因为 fib n 调用 fib（n-1），然后调用 fib（n-2），并将答案返回给 fib n 。但是你必须再次计算 fib（n-2），因为你还没有保存答案。

<在Haskell（或其他任何语言）中更好地实现 fib 如下所示：

  fib 0 = 0 
 fib n = fib'0 1 n 
 
 fib'_ curr 1 = curr 
 fib'last curr n = fib注意每个 fib' call只会产生一个递归，而不是两个。我上面写的大致是 0：1：zipWith（+）fibs（tail fibs）正在做什么，但上面的代码有点混乱，但也可能更容易翻译成其他语言。
 
I am beginning to learn Haskell, and one of the things I like to do when I'm learning a new language is to do Project Euler problems as a supplement to my main reference material.

I have come up with the following solution to the second problem of finding the sum of the even Fibonacci numbers less than four million:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
f :: Integer -> Integer
f n =
  let evenFib = filter (\n -> n `mod` 2 == 0) fibs
  in sum (takeWhile (<n) evenFib)
This works great; f 4000000 returns the correct answer.  It does so instantly.  Curious, I started typing in larger and larger numbers...
Prelude> f 40000000
19544084
Prelude> f 400000000000
478361013020
Prelude> f 40000000000000000000000000000000
13049874051046942401006156573274
Prelude> f 2370498572349582734598273495872349587234958723948752394857
2805750129675962215536656398462489370528480907433875715844
Each of these values is returned immediately.  I have no way of guaranteeing the veracity of the last two answers, because my implementations in other languages don't work for numbers this large.

So, my question is, what is Haskell doing here?  How is it returning these values instantaneously (whether they're actually correct or not)?  Furthermore, are these answers indeed correct, or is Haskell just making stuff up?  
解决方案
It's likely nothing to do with Haskell in particular but the algorithm you're using for the other solutions.

As fibonacci numbers grow quite quickly (they get 1.6x larger on average each step), there's not that many fibonacci numbers less than 40000000000000000000000000000000, probably less than 100.

A computer adding less than 100 numbers of this size (which isn't particularly big) should take microseconds. 

I'm not sure what your other implementations look like, but a common mistake is to write the Fibonacci function like this:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
This is terrible, as fib n calls fib (n-1), which then calls fib (n-2), and returns the answer to fib n. But then you have to go an calculate fib (n-2) again because you haven't saved the answer.

A better implementation of fib in Haskell (or indeed any other language) is like the following:
fib 0 = 0
fib n = fib' 0 1 n

fib' _ curr 1 = curr
fib' last curr n = fib' curr (last+curr) (n-1)
Notice that each fib' call only makes one recursive all, not two. What I've written above is roughly what 0 : 1 : zipWith (+) fibs (tail fibs) is doing, but the above code is a bit messier but probably also easier to translate into other languages.

                        
这篇关于Haskell如何即时计算这个庞大的数字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！