'Big' fractions in Julia

Question

I've run across a little problem when trying to solve a Project Euler problem in Julia. I've basically written a recursive function which produces fractions with increasingly large numerators and denominators. I don't want to post the code for obvious reasons, but the last few fractions are as follows:

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

At that point I get an OverflowError(), presumably because the numerator and/or denominator now exceeds 19 digits. Is there a way of handling 'Big' fractions in Julia (i.e. those with BigInt-type numerators and denominators)?

Addendum:

OK, I've simplified the code and disguised it a bit. If anyone wants to wade through 650 Project Euler problems to try to work out which question it is, good luck to them – there will probably be around 200 better solutions!

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)

If I run the above function with, say, 20 as the argument it runs fine. With 50 I get the OverflowError().

Answer 1

Julia defaults to using machine integers. For more information on this see the FAQ: Why does Julia use native machine integer arithmetic?.

In short: the most efficient integer operations on any modern CPU involves computing on a fixed number of bits. On your machine, that's 64 bits.

julia> 9223372036854775805 + 1
9223372036854775806

julia> 9223372036854775805 + 2
9223372036854775807

julia> 9223372036854775805 + 3
-9223372036854775808

Whoa! What just happened!? That's definitely wrong! It's more obvious if you look at how these numbers are represented in binary:

julia> bitstring(9223372036854775805 + 1)
"0111111111111111111111111111111111111111111111111111111111111110"

julia> bitstring(9223372036854775805 + 2)
"0111111111111111111111111111111111111111111111111111111111111111"

julia> bitstring(9223372036854775805 + 3)
"1000000000000000000000000000000000000000000000000000000000000000"

So you can see that those 63 bits "ran out of space" and rolled over — the 64th bit there is called the "sign bit" and signals a negative number.

There are two potential solutions when you see overflow like this: you can use "checked arithmetic" — like the rational code does — that ensures you don't silently have this problem:

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

Or you can use a bigger integer type — like the unbounded BigInt:

julia> big(9223372036854775805) + 3
9223372036854775808

So an easy fix here is to remove your type annotations and dynamically choose your integer types based upon 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