JuliaでProject Euler(16) - inamori’s diary

Problem 16

本当は速い方法(メルセンヌ数を10進表示する)があるが、ここでは単に2倍ずつしていく。

Pythonでは、

import sys

def twice(v):
    v2 = []
    carry = 0
    for d in v:
        carry, r = divmod(d*2+carry, 10)
        v2.append(r)
    if carry > 0:
        v2.append(carry)
    return v2

def e016(N):
    a = reduce(lambda x, y: twice(x), xrange(N), [1])
    return sum(a)

N = int(sys.argv[1])
print e016(N)

Juliaにそのまま翻訳。

function twice(v)
    v2 = []
    carry = 0
    for d in v
        n = d*2+carry
        r = n%10
        carry = div(n, 10)
        push!(v2, r)
    end
    if carry > 0
        push!(v2, carry)
    end
    return v2
end

function e016(N)
    a = reduce((x, y) -> twice(x), 1:N, init=[1])
    return sum(a)
end

N = parse(Int, ARGS[1])
println(e016(N))

実行してみると、

% time julia e016.jl 100000
135178

real    1m27.103s
user    1m27.047s
sys     0m0.531s

% time pypy e016.py 100000
135178

real    0m9.283s
user    0m8.547s
sys     0m0.719s

2行目はやはり、型を指定してやらないといけない。

    v2::Array{Int} = []

こうすると、PyPyと同様になる。

time julia e016a.jl 100000
135178

real    0m9.041s
user    0m9.203s
sys     0m0.453s

PyPyでは型が推定できているのだろう。