|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４３１回 平方根のアルゴリズム２ 発行 ２００４年３月５日（金曜日） 発行数 約３１００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 ドラクエがまちどうしくて、気が狂いそうな、あゆしゃです。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 平方根のアルゴリズム２ ＞＞ /*========================================================*/ 今回は、割り算を使わない、UINTの平方根を考えて見ましょう。 /*========================================================*/ まず、平方根について基礎から確認しましょう。 平方根とは、数字の桁数を叩き割った数字のことです。 １００００の平方根は１００です。 ０ｘ１００００の平方根は０ｘ１００です。 桁数を叩き割れば、平方根になります。 だから、３２ビットの平方根は１６ビットです。 UINTの平方根の範囲は０〜６５５３５、たったこれだけです。 UINTの平方根を考える場合、複雑な方程式を考える必要は まったくありません。 たかが６万ぐらい、総当りをかけて問題ありません。 /*========================================================*/ ６万の範囲を２分岐で検索しましょう。 UINT ayu_sqrt( UINT a ); UINT x; // オーバーフロー例外回避 if( a >= ( UINT )65535 * ( UINT )65535 ) return 65535; // 最初のチェック if( a > 32768 * 32768 ) x = 32768 + 16384; else x = 32768 - 16384; // 残りをループ for( chk = 8192; chk; chk >>= 1 ) { // 大きければ大きいほうを、小さければ小さいほうを検索続行 if( a > chk * chk ) x += chk; else x -= chk; } // ( UINT )sqrt( a )と答えを合わせるためのごめんなさい if( a > x * x ) x++; if( a < x * x ) x--; // はい、出来上がり return x; /*========================================================*/ ループは固定長なので、展開するともっと早くなります。 標準関数のsqrt()は、大体４０クロックで動作します。 今回のこの処理はループを展開して７０クロックぐらいです。 でも、割り算を使う普通のアルゴリズムも同じぐらいです。 割り算のくせに、早すぎです。ペンティアムはまったく。 まぁ、柔王丸のようなマイコン製品には重宝するかも。 なお、UINTではなくUSHORTを求める場合、４０クロックぐらい、 標準関数と匹敵する速さで動作します。 残念ながら、上回ることはありませんでした。まったく。 {magclick} /*========================================================*/ さいごに /*========================================================*/ 標準関数のsqrt()は、FSQRTというアセンブラ命令を実行 します。 つまり、電子回路で演算するわけです。 ずるいですよね。 ソフトでそれをシミュレートすると遅くなるのは当然ですが、 まぁ２倍弱程度なら、上出来ではないでしょうか。 同じ感じで、浮動少数にも使えます。 浮動少数には０という値が難しいので、 chk > 0.0000001 という感じで、判定します。０が増えると精度が上がり、 低速化します。 同じ感じで、巨大な桁数にも使えます。 {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は３月９日（月曜日）に、第４３２回を送ります。 お題は「掛け算割り算アルゴリズム」 続いて、掛け算と割り算のアルゴリズムについて、お話でも しましょうか。 これも巨大な桁数計算に応用できます。 また、３２ビットの演算をサポートしない柔王丸のような マイコン製品にも応用できるでしょうか？ お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 暮れなずむ、野越え山越え、馬の糞 なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ まぐまぐアイディー 0000020674 まぐまぐバックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ 登録と解除 http://www.mag2.com/m/0000020674.htm ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp めーらっくす ＜＜過去ログがタイトル別になっています＞＞ http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F |