Julia cannot add 2 big integers correctly

New to Julia
1

I have come across what I consider a big problem.

I’m reading “Think Julia” by Allen Downey and Ben Lauwens, and I am now in the chapter about Dictionaries. I am specifically on the Memos subchapter.

I am calculating the fibonacci series of numbers. I use the following code:

known = Dict(0=>0, 1=>1)

function fibonacci(n)
    if n ∈ keys(known)
        return known[n]
    end
    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    res
end

For small numbers it calculates well. The problem is with the “big numbers”.

fibonacci(1425)
7824277221020082018

fibonacci(1426)
8946276023139000775

fibonacci(1427)
-1676190829550468823

Wait a minute ! The sum of two positive numbers cannot give me a negative number.

   fibonacci(1425) + fibonacci(1426) should equal fibonacci(1427)

To me, it seems a problem of overflow. Somehow, I am calculating very big fibonacci numbers.

The problem is that Julia doesn’t warn me or even give me an error !!!

OK, let me try the calculation with the BigInt type of numbers. My new code is …

known = Dict{Int, BigInt}(0=>0, 1=>1)

function fibonacci(n)
    if n ∈ keys(known)
        return known[n]
    end
    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    res
end

Let’s calculate the same fibonacci numbers.

fibonacci(1425)
2870135193715480114725730918763701706297989719713950663872181225188570407497069958099922697430757395929817284686166601789284155271891376602707398646646393487578030823647270568341447238508684080880943650098811795294138886743280637686860685621776451660752376535348947846577631510497401804806696542050

fibonacci(1426)
4643976295738910422782284314065068453793584638755326395700934561957574291597816213807062336695384839760502199019030434245092888600854131835376621590138445911467175656089921622533698591501454932822440811745532167720317101247893453436522997270972458827078034544593550904048414169482938822744045478343

fibinacci(1427) 
7514111489454390537508015232828770160091574358469277059573115787146144699094886171906985034126142235690319483705197036034377043872745508438084020236784839399045206479737192190875145830010139013703384461844343963014455987991174091123383682892748910487830411079942498750626045679980340627550742020393

This time, the sum of two positive numbers is positive, which is perfect.
But the new results, calculated with BigInt have nothing to do with those calculated previously. They are different by many orders of magnitude.

This is where I begin to mistrust the calculations that Julia does for me.

  1. Do you think that I am missing any important points?
  2. The results that I am getting seem to me incoherent. What’s your opinion?

I appreciate any comments.

2

The results are the same mod 2^64. Julia’s Ints have overflow because Ints on a CPU have overflow and making your basic integer type a BigInt makes your language about 50x slower. For a lot more detail, see Discussion about integer overflow

11 Likes
3

Thank Oscar_Smith,

I understand, from your reply, that BigInt gives me the correct answer although it is 50x slower.

However, I consider that Julia should error in case of overflow, and it doesn’t.

Is there any code snippet to catch overflow problems? no doubt it would help a lot.

4

Base.Checked has operators that will throw errors on overflow. That said, the possibility of error throwing will also make your code noticeably slower.

7 Likes
5

Consider using GitHub - JeffreySarnoff/SaferIntegers.jl: These integer types use checked arithmetic, otherwise they are as system types.

julia> @saferintegers known = Dict(0=>0, 1=>1)
Dict{SafeInt64, SafeInt64} with 2 entries:
  0 => 0
  1 => 1

julia> fibonacci(SafeInt(2334))   
ERROR: OverflowError: 7540113804746346429 + 4660046610375530309 overflowed for type Int64
Stacktrace:
 [1] throw_overflowerr_binaryop(op::Symbol, x::Int64, y::Int64)
   @ Base.Checked ./checked.jl:155
 [2] checked_add
   @ ./checked.jl:167 [inlined]
 [3] +(x::SafeInt64, y::SafeInt64)
   @ SaferIntegers ~/.julia/packages/SaferIntegers/Xn8ie/src/arith_ops.jl:35
 [4] fibonacci(n::SafeInt64) (repeats 2242 times)
4 Likes
6

There was a lot of discussion about this in the thread that Oscar linked. Detecting overflow by default comes at considerable expense. In part, catching overflow by default makes vectorization difficult. There is a cost to do what you ask.

What Julia does is give you choices. By default, it lets the processor go as fast as possible. However, we also provide the means to create your own primitive types and change how arithmetic works with them.

Above, the safer integer types have overriden arithmetic with safer arithmetic. It uses checked arithmetic that Oscar mentioned.

https://docs.julialang.org/en/v1/base/math/#Base.Checked.checked_add

julia> using Base.Checked     
                                      
julia> checked_add(28282828282, typemax(Int64))
ERROR: OverflowError: 28282828282 + 9223372036854775807 overflowed for type Int64
Stacktrace:
 [1] throw_overflowerr_binaryop(op::Symbol, x::Int64, y::Int64)
   @ Base.Checked ./checked.jl:155
 [2] checked_add(x::Int64, y::Int64)
   @ Base.Checked ./checked.jl:167
 [3] top-level scope
   @ REPL[17]:1

What I think is amazing about Julia is that I did not have to modify your function. I could change the overflow checking behavior by just changing the types used.

3 Likes
7

@mkitti ,

I was not aware of the existence of this package, and in my case, it seems really helpful.

I’ll have a deeper look at it !!!

8

Just to clarify, integer overflow is not a Julia issue. Python numpy and many other languages/framework behave the same, beause as you have been said, checking is expensive. That’s said, you have been given tools that resolve this trade-off in favour of checking, just that is not the default in Julia.

4 Likes