186 #5016(2007/12/27 15:44 GMT) Rating1/1=1.00
出題者です. 『The Art of Computer Programming』や, 参考ページに挙げたサーベイに歴史が載っていました.
二進互除法を考えたのは, SteinとSilver and Terzianです. Knuth先生曰く一番古いのは以下だそうです.
前漢の中国の数学書『九章算術』の第1章「方田」の第6問より引用.
> (6) 方田: 又有九十一分之四十九。問約之得幾何？
> 答曰：十三分之七。
> 約分術曰：可半者半之，不可半者，副置分母子之數，以少減多，更相減損，求其等也。以等數約之。
see: R. P. Brent “Twenty years' analysis of the binary Euclidean algorithm”
[ reply ]
186 #5016() Rating1/1=1.00
出題者です. 『The Art of Computer Programming』や, 参考ページに挙げたサーベイに歴史が載っていました.
二進互除法を考えたのは, SteinとSilver and Terzianです. Knuth先生曰く一番古いのは以下だそうです.
前漢の中国の数学書『九章算術』の第1章「方田」の第6問より引用.
> (6) 方田: 又有九十一分之四十九。問約之得幾何？
> 答曰：十三分之七。
> 約分術曰：可半者半之，不可半者，副置分母子之數，以少減多，更相減損，求其等也。以等數約之。
see: R. P. Brent “Twenty years' analysis of the binary Euclidean algorithm”
[ reply ]