luaでProject euler25やってみた

エンジニア仲間からluaって言語を教えてもらったので

軽くいじってみた

環境はubuntuなのでtarしてmake linux && sudo make install

で/usr/local/bin/以下に

lua

luac

ってのがインストールされます。

でも標準だと数値演算で14桁までしか計算出来ないので

src/以下のluaconf.hを編集してからmakeします。

編集した箇所は以下。

420-430行目付近。

longをlong longに変更

500-530行目付近。

doubleをlong doubleに変更
LUA_NUMBER_SCANを%Lfに変更
LUA_NUMBER_FMTを%.32LGに変更

で、make linux && sudo make install

エラーが出なければOkです。

でもこれでも32桁までしか扱えないので

それ以上の桁数の計算をする際には別に実装してあげる。

今回はeulerの25問目。

Fn = Fn-1 + Fn-2

フィボナッチ数の1000桁以上目になるnを求める。

これだと処理の途中で確実にスタックオーバーランしてしまうので

1．処理対象の数値を文字列として扱う

2．文字列にした数値を3桁ごとに区切る

3．3桁ごとに加算処理

4．処理結果を結合

とします。

以下コード

-- project euler 25
-- example

digits = 3

function sep(n)
    local l = string.len(n)
    local f = digits
    local limit = math.floor(l / f)
    local a = l % f
    
    if a > 0 then limit = limit + 1 end

    local cnt = 0
    local rtn = {}
    while limit > cnt do
        if limit - cnt == 1 and a > 0 then
            v = string.sub(string.sub(n, -f), 0, a)
        else
            v = string.sub(string.sub(n, -f), 0, digits)
        end

        rtn[cnt] = v
        f = f + digits
        cnt = cnt + 1
    end
    return rtn
end

function merge(n, m)
    n = sep(n)
    m = sep(m)
    b = ""
    c = {}
    local l = table.maxn(m)
    for i=0, l do
        if n[i] == nil then n[i] = 0 end
        if m[i] == nil then m[i] = 0 end
        a = n[i] + m[i]
        if 0 < i and i <= l then
            a = a + b
        end
        if string.len(a) > digits then
            b = string.sub(a, 0, 1)
        else
            b = 0
            if string.len(a) < digits then
                if string.len(a) == 1 then a = "00"..a end
                if string.len(a) == 2 then a = "0"..a end
            end
        end
        c[i] = string.sub(a, -digits)
    end
    
    if b then c[table.maxn(c)+1] = b + 0 end
    
    s = ""
    for i=0, table.maxn(c) do
        s = c[i]..s
    end
    return s
end

function main()
    local a, b, c = "0", "1", "1"
    while 1 do
        a, b, c = b, string.gsub(merge(a,b), "^0*", ""), c+1
        -- print(c..":\t"..b)
        if string.len(b) >= 1000 then print(c) break end
    end
end


main()

pythonの場合main()の多重代入してる箇所でmerge(a,b)なんてする必要なくてa + bだけでOK。

コンマで結果が帰ってくるけどluaの場合はmerge関数作って毎回実行してってなっているから8秒近くかかった。

もっと効率よく出来たらいいのに思いつかない。。。