PyDigits.jl (generate Pi digits)

pydigits.jl

# The Computer Language Benchmarks Game
# http://benchmarksgame.alioth.debian.org/

# created by Sébastien Arnaud <[email protected]>
# inspired from Python version: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=pidigits&lang=python3&id=5
# modification suggested by ScottPJones &

# Performance on Macbook 12" Retina (1.3Ghz)

# Julia v0.4.3
#julia> include("pidigits.jl")
#pidigits (generic function with 1 method)
#
#julia> @time pidigits(1000)
#3141592653	:10
#
#  0.056551 seconds (61.97 k allocations: 25.942 MB, 12.53% gc time)#
#julia> @time pidigits(10000)
#3141592653    :10
#5897932384    :20
#...
#2056001016    :9990
#5525637567    :10000
# 3.733863 seconds (631.91 k allocations: 3.606 GB, 9.16% gc time)

# Compared to Python 3.5.1
# $>time python3 pidigits.py 10000
# 3.56s

function add!(x::BigInt, y::BigInt)
   ccall((:__gmpz_add, :libgmp), Void, (Ptr{BigInt}, Ptr{BigInt}, Ptr{BigInt}), &x, &x, &y)
   return x
end

function mul!(x::BigInt, y::BigInt)
   ccall((:__gmpz_mul, :libgmp), Void, (Ptr{BigInt}, Ptr{BigInt}, Ptr{BigInt}), &x, &x, &y)
   return x
end

function f_divmod(n::BigInt, d::BigInt)
  q, r = BigInt(), BigInt()
  ccall((:__gmpz_fdiv_qr, :libgmp), Void, (Ptr{BigInt}, Ptr{BigInt}, Ptr{BigInt}, Ptr{BigInt}), &q, &r, &n, &d)
  return q, r
end

function fast_mod(n::BigInt, d::BigInt)
  r = BigInt()
  ccall((:__gmpz_mod, :libgmp), Void, (Ptr{BigInt}, Ptr{BigInt}, Ptr{BigInt}), &r, &n, &d)
  return r
end

function pidigits(N)

  B_ONE, B_TWO, B_TEN = map(BigInt, (1, 2, 10))
  n, a, d, t, u, ns, k1, k = map(BigInt, (1, 0, 1, 0, 0, 0, 1, 0))
  i = UInt64(0)
  io = IOBuffer()

  while true
    add!(k, B_ONE) # k += 1
    t = n << 1
    mul!(n, k) # n *= k
    add!(a, t) # a += t
    add!(k1, B_TWO) #k1 += 2
    mul!(a, k1) # a *= k1
    mul!(d, k1) # d *= k1
    if a >= n
      t, u = f_divmod(n * 3 + a, d)
      add!(u, n) # u += n
      if d > u
        mul!(ns, B_TEN) # ns *= 10
        add!(ns, t) # ns += t
        i += 1
        if i % 10 == 0
          @printf(io, "%010d\t:%d\n", ns, i)
          ns = big(0)
          if i >= N
            # Print the content of buffer & exit
            println(takebuf_string(io))
            break
          end
        end
        add!(a, -d * t) # a -= d * t
        mul!(a, B_TEN) # a *= 10
        mul!(n, B_TEN) # n *= 10
      end
    end
  end
end

if size(ARGS, 1) > 0
  N = parse(Int, ARGS[1])
  pidigits(N)
end