A plea for int overflow checking as the default

Internals & Design
, ,
75

@Jean_Michel

I think you are simply misusing BigInt. I get much better timings by using inplace operations (the following works only on 0.7; I don’t know whether the GMP/MPZ wrapper exists in 0.6)

#using Int
@btime collatz_small(5000)
  736.384 ��s (0 allocations: 0 bytes)

#using BigInt, essentially your code
@btime collatz_slow(5000)
  134.810 ms (3111832 allocations: 53.44 MiB)

#using inplace ops
@btime collatz_fast(5000)
  8.832 ms (3 allocations: 48 bytes)

The code:

using Base.GMP.MPZ
using BenchmarkTools

function collatz_small(lim)
  max=1
  i=1    
  while i<lim
     i+=1
     c=0
     n=i
     while n>1
       if n&1==0 
         n>>=1
       else 
         n=3*n+1
       end
       c+=1
     end
     if c>max
       max=c
       #println("at $i new max=$max")
     end
  end
  max
end

function collatz_slow(lim)
  max=1
  i=1    
  while i<lim
     i+=1
     c=0
     n=BigInt(i)
     while n>1
       if n&1==0 
         n>>=1
       else 
         n=3*n+1
       end
       c+=1
     end
     if c>max
       max=c
       #println("at $i new max=$max")
     end
  end
  max
end


function collatz_fast(lim)
  max=1
  i=UInt(1)
  n=BigInt(0)
  while i<lim
     i+= 1
     c=0
     MPZ.set_ui!(n,i)
     while n>1
       if !(MPZ.tstbit(n,0))
        MPZ.fdiv_q_2exp!(n,1)        
       else 
         MPZ.mul_ui!(n,UInt(3))
         MPZ.add_ui!(n,UInt(1))         
       end
       c+=1
     end
     if c>max
       max=c
       #println("at $i new max=$max")
     end
  end
  max
end

@btime collatz_small(5000)
@btime collatz_slow(5000)
@btime collatz_fast(5000)