« #Calc 1.1.4 その 16 | トップページ | フォクすけ »

2006年9月19日 (火)

自然数の平方根のアルゴリズム

今の #Calc の実装では平方根の計算に二分法を使っているが、あまり速くない。逆双曲線余弦の実装ができたら平方根のほうを改良しようと思って、平方根のアルゴリズムについて調べていたら、Ruby のメーリングリストに興味深い情報を見つけた。

素晴らしい。ニュートン法の二次収束の性質をうまく活かしている。ニュートン法ではどう頑張っても除算の計算時間の log(桁数) 倍の計算時間が必要になると思っていたのだが、この方法だと除算と同じオーダーで計算できる。

逆双曲線余弦が終わったらこの新しいアルゴリズムでどれくらい速くなるか実験だ。

|

« #Calc 1.1.4 その 16 | トップページ | フォクすけ »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/169172/11962312

この記事へのトラックバック一覧です: 自然数の平方根のアルゴリズム:

« #Calc 1.1.4 その 16 | トップページ | フォクすけ »