TSpython 発言

Fe2+ です。

At Thu, 10 Jan 2008 16:12:56 +0900 (JST),
機械伯爵 wrote:
> 
> 　う〜ん、ブログにも書かれてたのだけど……
> 
> > 最大 greatest 公 common 約数 divisor なので、gcm ではなく gcd です。
> 
> 　G.C.D.が一般的みたいですが、一応、
> 　G.C.M.(greatest common measure)
> 　という用語もあるんですよ（measure = 測る単位という意味で「約数」）
> 　……よっぽどマイナーなのかしらん、この言葉。
> ※あるいは、プログラムのライブラリとかは全てgcdなのかな？

数学に関係している人間の感覚から言わせてもらうと、measure という語は
「測度」という積分の術語を強く想起するので、ここでは使いたくないです。
おそらくユークリッドは長さの共通単位を探す方法として互除法を提示してい
た、というような歴史を踏まえれば妥当性のあった語法かもしれませんが…。


> 　私は別に再帰の信奉者じゃないですけど、このタイプの場合は、かなり大きな
> 数値になっても再帰の限界はきませんので、よほど大丈夫かと。

ユークリッドの互除法の計算量(ループ回数)を評価する良く知られた方法をこ
こで再帰回数の話に単純に置き換えられます。すなわち、フィボナッチ数
F(n) を F(n+2) = F(n+1) + F(n), F(1) = F(2) = 1 で定義すると、F(n+1) と
F(n) の最大公約数は F(n) と F(n-1) の最大公約数に等しくなることがわかり、
したがって再帰回数 n - 1 回で F(3) と F(2) の最大公約数を求めるところま
で至ります。F(3) = 2, F(2) = 1 ですから、ここで余りが無くなって再帰が終
わります。ということで、大雑把に F(n) ぐらいの引数があると n 回の再帰が
必要になることがあることが判りました。
さて、Python の再帰回数の上限はどのくらいかというと、私の手元では 1000
回になっています(sys.getrecursionlimit())。F(1000) がいくらぐらいにな
るかというと、200 桁を少し越えるぐらいです。これを使う機会がないぐらい
大きな数と思うならば大丈夫ということです。

ちなみに前回の gcd のコードは私が関わっている NZMATH というプロジェクト
のコードから引っ張ってきました。そこでは 200 桁は十分大きいとは考えてい
ません。
-- 
MATSUI "Fe2+" Tetsushi