如何生成一个代表'e'二进制扩展的系列

Question

我试图在'e'的扩展中找到前100,000个二进制数字.是否有算法将'e'的二进制数字生成为无限列表？

Answer 1

这是eHaskell中一个无限的龙头:

main = print $ stream (1,0,1) [(n, a*d, d) | (n,d,a) <- map f [1..]]
    where
        f k = (1, k, 1)

stream z (x:xs)
    | lbound == approx z 2 = lbound : stream (mul (10, -10*lbound, 1) z) (x:xs)
    | otherwise            =          stream (mul z x) xs
  where
    lbound = approx z 1

approx (a,b,c) n = (a*n + b) `div` c

mul (a,b,c) (d,e,f) = (a*d, a*e + b*f, c*f)

基于编程Praxis 无限制的e和pi插口,后者又来自Gibbon的第一个无限制的pi插口.

$ runhaskell A.hs
[2,7,1,8,2,8,1,8,2,8,4,5,9,0,4,5,2,3,5,3,6, ^C

如果你对这些有趣的算法感兴趣,我会推荐Gibbon的论文.

Answer 2

您可能有兴趣使用CReal.对于100,000个二进制数字,30,200个十进制数字就足够了:

Prelude> 100000 * logBase 10 2
30102.999566398114
Prelude> :m + Data.Number.CReal
Prelude> :set +s
Prelude Data.Number.CReal> last $ showCReal 1000 (exp 1)
'4'
(0.34 secs, 34061824 bytes)
Prelude Data.Number.CReal> last $ showCReal 2000 (exp 1)
'4'
(1.25 secs, 104478784 bytes)
Prelude Data.Number.CReal> last $ showCReal 4000 (exp 1)
'7'
(5.96 secs, 355775928 bytes)
Prelude Data.Number.CReal> last $ showCReal 8000 (exp 1)
'2'
(20.89 secs, 1298942504 bytes)

这个模式对我来说看起来是二次方的,所以exp 1在我的机器上计算前五十或二十分钟的前30,200位数看起来可能合理地完成.可以接受以二进制直接输出的补丁(因此避免转换为十进制和后退).

编辑:投影满意,只需不到六分钟的计算时间!

Prelude Data.Number.CReal> showCReal 30200 (exp 1)
"2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334...middle snipped due to StackOverflow message limit...39106913376148418348845963656215266103322394174671"
(349.44 secs, 17096829912 bytes)