日経BP橋爪様より献本御礼。

まさに夏休みの読み物にうってつけ。数学の入口として、これほど適した話題もないのではないか。円周率を5兆けたでは夏休みが終わってしまうが、本書なら一夏分の課題にちょうどよさそうだ。

本書「不思議な数列フィボナッチの秘密」は、「不思議な数πの伝記」の著者たちによる一冊まるごとフィボナッチ数の本。類書としては「黄金比の謎」があるが、同書がより一般的な数学書であるのに対し、本書はフィボナッチ数一筋である。

目次 - 日経BP書店|商品詳細 - 不思議な数列フィボナッチの秘密より
はじめに 途方もないフィボナッチ数
謝辞
第1章 フィボナッチ数の歴史と姿
第2章 自然界のフィボナッチ数
第3章 フィボナッチ数とパスカルの三角形
第4章 フィボナッチ数と黄金比
第5章 フィボナッチ数と連分数
第6章 フィボナッチ数があてはまる例あれこれ
第7章 美術と建築に見られるフィボナッチ数
第8章 フィボナッチ数と音楽
第9章 個別のフィボナッチ数を求めるためのビネーの公式
第10章 フィボナッチ数とフラクタル
エピローグ
後記
付録A 500番までのフィボナッチ数と、200番までの素因数分解
付録B フィボナッチ関係式の証明
参考資料
訳者あとがき

フィボナッチ数(Fibonacci Numbers)の何がよいかといえば、「かなり先」まで小学生でもわかるということである。なにせ、定義はこんなに簡単だ。

「0のときは0、1のときは1、それ以外のときは、2つ前と1つ前の数字を足したもの」

九九すら必要ない。素数ですら、割り算が絡んでくるというのに。

これが人気度トップの円周率(π;pi)ともなると、実際に計算できるようになるのは高校の数学を全てやってから。円周率はすごいけど難しいし、難しいがゆえに「なんだかわからないけどすごい」で終わってしまう人がほとんどだ。

それでいて、大人でも、というより二次性徴を過ぎたエロい人も魅了されずにはいられない。なにしろ、フィボナッチ数の極限が黄金比なのだ。数学や科学の専門家は、語彙の拡大解釈--たとえば○×社のDNA--を嫌う傾向が強いけど、この比喩に関しては心配ない。比喩ではなく本当なのだから。nが無限に大きな時、Fn:Fn-1が黄金比である。

このくらいまでは、数学が好きな人であればご存知であろう。しかしkmとマイルの変換がこれで出来ることまでご存知だろうか?ちょっと強引な気がするが、たしかにkmとマイルの比も黄金比に近い。

数学にとってのフィボナッチ数は、Playboyにとってのバニーと言い切ってもよい。なにしろフィボナッチ数の起源自体、ウサギの増え方が元となっているのだ。これがセクシーでなくてなんといおう。

本書の唯一の不満は、コンピューターがあまり登場しないこと。目次を見てもわかるとおり、フラクタルとの絡みでちらっと登場はするが、プログラムまでは出てこない。しかしフィボナッチ数の計算というのは、プログラミングを学ぶのにうってつけなのである。

しかしこれは不満であっても不備ではない。なければ自分でやればいい。そしてπの計算とは違って、フィボナッチ数の計算はアンチョコがなくても書ける。FizzBuzzより簡単なのだ。それでいて、ちょっと大きなフィボナッチ数の計算ともなると工夫が必要となってくる。というわけで本entryふろくに500番までのフィボナッチ数を求めるプログラムを各言語で書いたものをつけてみた。単にソースコードがあるのではなく、実際にこの場で実行可能である。

数学好きも、フィボナッチ数のように増えてくれればいいのに。

Dan the Blogger Combinator

ふろく

JavaScript

これのみLLEvalではなくブラウザーで直接実行するようにしている。メモ化は素手で。なおここではF(80)までしか計算していない。しかもF(80)の結果は間違っている。JavaScriptのNumberオブジェクトは253までしか整数を保持できないためである。多倍長整数を実装すれば、当然この制限は乗り越えられるのだが、今のところJavaScriptのものとして標準的なものはないようだ。

var fibonaccis = {};
var fibonacci  = function(n){
  if (fibonaccis[n]) return fibonaccis[n];
  return fibonaccis[n] = n === 0 ? 0
                       : n === 1 ? 1
                       : arguments.callee(n-2) + arguments.callee(n-1);
};

for (var i = 1; i < 80; i++)
  p('F(' + i + ') = ' + fibonacci(i));

Perl

多倍長整数のためにbignumを、メモ化のためにbignumを使っている。

#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use Memoize;
use bignum lib => 'GMP';

memoize('fibonacci');

sub fibonacci {
    my $n = shift;
        $n == 0 ? 0
      : $n == 1 ? 1
      :           fibonacci( $n - 2 ) + fibonacci( $n - 1 );
}

say "F($_) = ", fibonacci($_) for 1..500;

Python

メモ化には西尾さんのコードをお借りした。多倍長整数は言語組み込み。

#!/usr/bin/python

# http://www.nishiohirokazu.org/archived_coreblog/829
class Memoize:
    def __init__(self, func):
        self.func = func
        self.cache = {}
    def __call__(self, *args):
        if self.cache.has_key(args):
            return self.cache[args]
        result = self.func(*args)
        self.cache[args] = result
        return result

def fibonacci(n):
  if   n == 0 : return 0
  elif n == 1 : return 1
  else        : return fibonacci(n-2) + fibonacci(n-1)

fibonacci = Memoize(fibonacci)

for i in xrange(1,501):
  print "F(%d) = %d" % (i, fibonacci(i))

Ruby

メモ化は手で実装。多倍長整数は言語組み込み。

#!/usr/bin/ruby

@fibonaccis = {}

def fibonacci(n)
  if @fibonaccis[n] then @fibonaccis[n]
  elsif n == 0 then 0
  elsif n == 1 then 1
  else  @fibonaccis[n] = fibonacci(n-2) + fibonacci(n-1)
  end
end

(1..500).each do |i|
  puts "F(#{i}) = #{fibonacci(i)}"
end

Haskell

最も美しい。がリソースを使いすぎるので100で打ち止め

#!/usr/bin/runhugs
main = mapM_ (putStrLn . show) (take 100 fibonaccis)

fibonaccis = 0:1:zipWith (+) fibonaccis (tail fibonaccis)