ハノイの塔の円盤の移動回数

円盤の移動回数

n 枚の移動回数をSnとすると、
Sn Sn-1 + 1 + Sn-1
 2 ・ Sn-1 + 1
 2 ・ (2 ・ Sn-2 + 1) + 1
 2 ・ (2 ・ (2 ・ Sn-3 + 1) + 1) + 1
 2 ・ (2 ・ (2 ・ (2 ・ Sn-4 + 1) + 1) + 1) + 1
  ...  
 2n ・ S0 + 2n-1 + 2n-2 + 2n-3 + ... + 2 + 1
Sn 2n-1 + 2n-2 + 2n-3 + ... + 2 + 1

公比2の等比数列の和ですから、 2 ・ Sn - Sn を計算すれば、 + ... + を消去できます。

2 ・ Sn   =   2n + 2n-1 + 2n-2 + 2n-3 + ... + 2
Sn   =        2n-1 + 2n-2 + 2n-3 + ... + 2 + 1
辺々差をとると、
2 ・ Sn - Sn   =   2n - 1
Sn   =   2n - 1

264 はどのぐらいの大きさか?

210 = 1024 ≒ 1000 = 103 という関係に注目しましょう。

264 260 X 24
  (210)6 X 24
  (103)6 X 24
  1018 X 24
  16 X 1018
  0.16 X 1020

となり、20桁であることが解ります。 円盤を1秒に1回動かすと64枚を動かし終わるのに、 0.16 X 1020 秒かかります。

1年を365日とすると、以下のように約3千万秒になります。

  365(日) X 24(時間) X 60(分) X 60(秒)
= 31536000 (秒)
= 0.32 X 108 (秒)

64枚動かし終わるのには、以下のように約5千億年かかります。

  (0.16 X 1020) ÷ (0.32 X 108)
= 0.5 X 1012
1秒間に1000回動かしても、この世の終わりは5億年先になります。 宇宙の始まりのビッグバンから約150億年、 地球の誕生から46億年といわれていますから、64枚という リュカ (注) の設定は妥当なものだといえます。
(注) Édouard Lucas (1842-1891) フランスの数学者。 このハノイの塔というパズルの作者。
『インドのガンジス川のほとりのベナレスという地にある寺院に、 ダイアモンドの針に64枚の黄金の円盤がさしてあり、バラモン僧が円盤を移動させている』 という設定で、『64枚を移し終えると、針も円盤も崩壊しこの世の終わりになる』 としている。

さて、スーパーコンピュータの速さがどれくらいかというと、 ...

達成した年速度(FLOPS)メーカ / 発注者 / 組み込まれたプロセッサ数
出典
2005目標 1015 IBM
2004予測 360 x 1012 IBM / エネルギー省
Blue Gene/L ピーク性能
2002 35.8 x 1012 NEC / Earth Simulator / 5120
TOP500 List for June 2004 1位
2004 19.9 x 1012 California Digital Corp. / Lawrence Livermore National Laboratory / 4096
TOP500 List for June 2004 2位
2002 13.8 x 1012 Hewlett Packard / Los Alamos National Laboratory / 8192
TOP500 List for June 2004 3位

2002年11月の TOP500 SuperComputer で、47位までが、 テラFLOPS を超えています。 (ピーク性能では74位まで)
2004年6月では242位までが超えました。

このぐらい速いとハノイの塔も解けちゃいますね。BigInteger できちんと計算してみましょう。

プログラム BigBang.java

実行結果
BigBang-1.gif

10 FLOPS で1回分としても 60日もあれば解けてしまいます。

あ、FLOPS? 「ふろっぷす」と読みます。Floating Point Operations Per Second のことで、1秒間に浮動小数点演算を何回実行できるかという能力をあらわす数値です。 つまり、横浜市の海洋研究開発機構横浜研究所に設置された「地球シミュレータ」という コンピュータは、浮動小数点演算を1秒間に36兆回実行できるということです。

(注)2004年11月の 25th TOP500 では以下のようになりました。

順位速度(FLOPS)メーカ発注者コンピュータ名 / 組み込まれたプロセッサ数
91.7 x 1012 IBMIBM/DOEBlue Gene/L DD2 beta-system(0.7GHz PowerPC 440) / 32768
51.8 x 1012 SGINASA/Ames Research CenterSGI Altix 1.5GHz, Voltair Infiniband / 10160
35.8 x 1012 NEC Earth Simulator Center Earth Simulator / 5120

「地球シミュレータ」は2002年からまもってきた1位の座をを明け渡しました。

(その後) 2005年11月のTOP10 26th TOP500では 7位になりました。 順位1の処理速度は3年で1桁上がっています。 プロセッサ数を25倍にして処理速度を8倍弱にしています。

(その後のその後) 2007年6月のTOP500 では以下のようになっています。 順位1は2005年11月から変わっていません。

順位速度(FLOPS)メーカサイトコンピュータ名プロセッサ数
280 x 1012 IBMDOE/NNSA/LLNLBlueGene/L - eServer Blue Gene Solution 131072
101.7 x 1012 Cray Inc.Oak Ridge National LaboratoryJaguar - Cray XT4/XT3 23016
101.4 x 1012 Cray Inc. NNSA/Sandia National Laboratories Red Storm - Sandia/ Cray Red Storm, Opteron 2.4 GHz dual core 26544
14 48.8 x 1012 NEC/Sun GSIC Center, Tokyo Institute of Technology TSUBAME Grid Cluster - Sun Fire x4600 Cluster, Opteron 2.4/2.6 GHz and ClearSpeed Accelerator, Infiniband 11088
20 35.8 x 1012 NEC Earth Simulator Center Earth Simulator 5120

(その後 32007年11月のTOP500 では 順位1はプロセッサ数を倍にしトップをまもりましたが、順位2以下が大きく入れ替わっています。

順位速度
(tera FLOPS)
メーカサイトコンピュータ名プロセッサ数
478.2 IBMDepartment of Energy's/National Nuclear Security Administration/Lawrence Livermore National Laboratory
U.S.A.
BlueGene/L - eServer Blue Gene Solution 212992
167.3 IBMForschungszentrum Juelich(FZJ)
Germany
JUGENE - Blue Gene/P Solution 65536
126.9 SGI SGI/New Mexico Computing Applications Center
U.S.A.
SGI Altix ICE 8200, Xeon quad core 3.0 GHz 14336
117.9 Hewlett-Packard Computational Research Laboratories, TATA SONS
India
Cluster Platform 3000 BL460c, Xeon 53xx 3GHz, Infiniband 14240
102.8 Hewlett-Packard Goverment Agency
Sweden
Cluster Platform 3000 BL460c, Xeon 53xx 2.66GHz, infiniband 13728
102.2 Cray Inc. NNSA/Sandia National Laboratories
U.S.A.
Red Storm - Sandia/ Cray Red Storm, Opteron 2.4 GHz dual core 26569
101.7 Cray Inc. Oak Ridge National Laboratory
U.S.A.
Jaguar - Cray XT4/XT3 23016
16 56.4 NEC/Sun GSIC Center, Tokyo Institute of Technology
Japan
TSUBAME Grid Cluster - Sun Fire x4600 Cluster, Opteron 2.4/2.6 GHz and ClearSpeed Accelerator, Infiniband 11664
30 35.8 NEC Earth Simulator Center
Japan
Earth Simulator 5120

建設費約600億円、年間維持費50億円強の「地球シミュレータ」は2008年度で破棄される見通しです。
5年間で、スーパコンピュータの速度は1桁上がり、同等の速度であればコストが1桁下がっています。(2007/11/13)

(その後 42011年6月のTOP500 では 理化学研究所の京(けい)が1位になりました。同年11月の TOP500 では処理能力は向上しましたが上位の順位は変わっていません。

順位 サイト
ベンダ / 開発年
コンピュータ コア数 Rmax Rpeak Power
理化学研究所
富士通/2011
京 SPARC64
VIIIfx 2.0GHz
Tofu interconnect
705024 10510.00 11280.38 12659.9
国立スーパコンピューティングセンタ天津
NUDT/2011
天河一号A
Xeon X5670 6C 2.93GHz
NVIDIA 2050
186368 2566.00 4701.00 4040.0
Oak Ridge National Laboratory
Cray Inc./2009
Cray XT5-HE
Opteron 6-core 2.6GHz
224162 1759.00 2331.00 6950.0
国立スーパコンピューティングセンタ深圳
Dawning/2010
Dawing TC3600 Blade System
Intel X5650
NVidia Tesla C2050 GPU
120640 1271.00 2984.30 2580.0
東京工業大学
NEC HP/2010
TSUBAME 2.0
HP Cluster
Xeon 6C X5670
Nvidia GPU
73278 1192.00 2287.63 1398.6

Rmax (実測速度)、Rpeak(理論値)の単位は テラFlops、 Power の単位は KW


Top Page
更新日: