'Big' Julia 中的分数

Question

我运行在尝试用 Julia 解决 Project Euler 问题时遇到了一个小问题。我基本上写了一个递归函数，它生成分子和分母越来越大的分数。出于显而易见的原因，我不想 post 代码，但最后几个分数如下：

1180872205318713601//835002744095575440
2850877693509864481//2015874949414289041
6882627592338442563//4866752642924153522

那时我得到一个 OverflowError()，大概是因为分子 and/or 分母现在超过了 19 位。有没有办法在 Julia 中处理 'Big' 分数（即那些具有 BigInt 类型分子和分母的分数）？

附录：

好的，我简化了代码并稍微伪装了一下。如果有人想通过 650 个欧拉计划问题来尝试找出它是哪个问题，祝他们好运——可能会有大约 200 个更好的解决方案！

function series(limit::Int64, i::Int64=1, n::Rational{Int64}=1//1)
    while i <= limit
        n = 1 + 1//(1 + 2n)
        println(n)
        return series(limit, i + 1, n)
    end
end

series(50)

如果我运行上述函数以 20 作为参数，它运行没问题。 50 我得到 OverflowError().

Answer 1

Julia 默认使用机器整数。有关这方面的更多信息，请参阅常见问题解答：Why does Julia use native machine integer arithmetic?.

简而言之：任何现代 CPU 上最有效的整数运算涉及对固定位数的计算。在您的机器上，这是 64 位。

julia> 9223372036854775805 + 1
9223372036854775806

julia> 9223372036854775805 + 2
9223372036854775807

julia> 9223372036854775805 + 3
-9223372036854775808

哇！刚刚发生了什么！？那绝对是错误的！如果你看看这些数字是如何用二进制表示的，就会更明显：

julia> bitstring(9223372036854775805 + 1)
"0111111111111111111111111111111111111111111111111111111111111110"

julia> bitstring(9223372036854775805 + 2)
"0111111111111111111111111111111111111111111111111111111111111111"

julia> bitstring(9223372036854775805 + 3)
"1000000000000000000000000000000000000000000000000000000000000000"

所以你可以看到那 63 位 "ran out of space" 翻转了 - 第 64 位称为 "sign bit" 并表示一个负数。

当您看到这样的溢出时，有两种可能的解决方案：您可以使用 "checked arithmetic" — 就像理性代码所做的那样 — 确保您不会默默地遇到这个问题：

julia> Base.Checked.checked_add(9223372036854775805, 3)
ERROR: OverflowError: 9223372036854775805 + 3 overflowed for type Int64

或者你可以使用更大的整数类型——比如无界 BigInt:

julia> big(9223372036854775805) + 3
9223372036854775808

所以这里的一个简单解决方法是删除类型注释并根据 limit:

动态选择整数类型

function series(limit, i=one(limit), n=one(limit)//one(limit))
    while i <= limit
        n = 1 + 1//(1 + 2n)
        println(n)
        return series(limit, i + 1, n)
    end
end

julia> series(big(50))
#…
1186364911176312505629042874//926285732032534439103474303
4225301286417693889465034354//3299015554385159450361560051

'Big' Julia 中的分数

'Big' fractions in Julia

biginteger

fractions

julia