ちなみに

火曜日の空は僕を押しつぶした。

逆フィボナッチ関数をぱくってみた

昨日からずっとフィボナッチ数列のことを恋かと思うほど考えてしまっていた。数学苦手なのに・・・。
頭の中で式を展開したりできないので、紙に書きまくったり他人の書いたコード読んでアルゴリズム勉強してたのだけど、なんとあのうじひささんも過去に逆フィボナッチ関数(nowa サービス終了のお知らせ)なるものを書いておられるではないか。触発されて、僕も書いてみようということになった次第です。

まずは自分で考えてみた

はじめに書いたのが下のコード。
ハッシュにあらかじめ、書き込んでおいたのを検索したら良いんじゃないかと考えて、ハッシュとサブルーチンについて勉強しなおしながら2〜3時間かかって書いたもの。ある程度の数ということで1000桁目まであらかじめ計算しておく仕様。

#!/usr/bin/perl

use strict;
use warnings;

my ($a, $b) = (0, 1);
my %fibonacci_numbers;

keys ( %fibonacci_numbers ) = 1000;

$fibonacci_numbers{ $a = ($b += $a) - $a } = $_  for (1..1000);

sub serch_fibo {
    my $number = shift @_; 
    $number--
        until (
            defined ( $fibonacci_numbers{ $number } )
            or $number <= 1
        );

    print (
        ( $number != 1 ) ? "$number : $fibonacci_numbers{ $number }\n"
        : "1 : 1 or 2\n"
    );
}

・・・これはひどい。こんなもの本来なら他人に見せられるもんじゃない。
フィボナッチ数列にない数字に対応する為にインクリメントしながら近い値を探すようにしたのだけど、毎回ハッシュを検索してるので、くそ重い。1億を超えると固まってしまう。本当にありがとうございました、

エントリー読んだ

速度も、計算してる桁数も桁違い・・・。予想はしていたけどいったん絶望。
Rubyの知識がゼロだったので、暫くRuby勉強してコードを読んでみた。

まず、フィボナッチ数列の取得から格が違う。というか近似式を使ってほんとに原始的に足していっている僕のレベルが低すぎたのですが。再帰的に書いたらこうなるのかぁなんて感心しながら肝心の逆フィボナッチ関数へ。
実質2行。あうち!勉強の足りなさを痛感。

ぱくる

という訳で、同じアルゴリズムを使ってPerlで書いてみた。

アルゴリズムはうじひささんのものをほぼそのまま使っていて、

  • 逆フィボナッチ関数(&get_number)
    • 1桁目から順番にフィボナッチ数列を計算
    • 入力された数値がn桁目とn+1桁目の間に存在すればn桁とする
  • フィボナッチ数列取得関数(&get_fibonacci_number)
    • 引数が2以下ならば1を返す
    • 配列@fibonacci_numbersのn番目が存在しなければ、n-2番目+n-1番目の値を代入

ってな感じです。

#!/usr/bin/perl

use strict;
use warnings;

my @fibonacci_numbers;

print &get_number($ARGV[0]), $/;

sub get_fibonacci_number {
    my $n = shift @_;
    return 1 if $n <= 2;
    $fibonacci_numbers[$n]
        ||= &get_fibonacci_number($n-2)
            + &get_fibonacci_number($n-1)
    ;
}   

sub get_number {
    my $n = shift @_;
    my $i = 1;
    return undef if $n <= 0;
    $i++
        until (
            &get_fibonacci_number($i)   <= $n
            and
            &get_fibonacci_number($i+1)  > $n
        );
   $i;
}

コードは汚いけど、アルゴリズムは、スマート(笑)


結果

% ./unfibo.pl 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1475

I got it!

しかし、実はこれ以上の桁数は無理です。うじひささんのオリジナルはもっと上の桁までいけます。このへんが今後の課題ですね。

もっともっともっと!!

結論

Rubyおもしろい。浮気しそう。

桁数といっているのは、フィボナッチ数列内の何番目かです。