|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４５３回 平方根デバッグ 発行 ２００４年５月２６日（水曜日） 発行数 約２９００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 /*========================================================*/ 前回までのあらすじ 先日、といっても昔のことではなく本当に最近なのですが、FBを やっていたとき、 「すばやさアルゴリズムは、どうなっているのだろう？」 と、疑問に思いました。さっそくグーグルで、 「フfァaントムブレイブ＋アルゴリズム」で検索しても、それら しいものは良くわかりませんでした。 他のキーワードでも、良くわかりませんでした。 /*========================================================*/ すばやさが９０，８０，３０のとき、行動回数は９：８：３に なって欲しいところが人情という感じでしょう。 /*========================================================*/ 一番簡単そうなのは、最小公倍数を使う方法でしょうか。 つまり、すべての参加キャラの最小公倍数を求め、誰か１人が その値を超えるまで、自分たちのすばやさを加算していき、上回っ たら、そいつが動いて、すばやさの現在値を０にリセット。 という感じでいいような気がしますが、最小公倍数なんて、INT の３２ビットを簡単に超えてしまうので、少し無理でしょうか。 足し算のみとはいえ、ループの回数が多そうですし、。。。、 これはだめかなぁ？ うーん、困った。 /*========================================================*/ というわけで とりあえず、最小公倍数はどのように求めるのでしょうか？ ２つの値の最小公倍数を求めるには、２つの値が同じになるまで 低いほうの値を増してやればよいのです。つまり、 while( a != b ) { if( a < b ) a += a_base; else b += b_base; } という感じ。基本的には、ですけどね。 _base は、元の値です。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 平方根デバッグ ＞＞ /*========================================================*/ 前回までで、大型計算機は足し算と引き算と掛け算と割り算が 行えるようになりました。 ならば平方根、と勇んで実行すると、撃沈。。。 帰ってこなくなります。 /*========================================================*/ UINT のときの計算回数は、１６回ぐらいでした。ビット数の、 半分と同じぐらいだからです。 大型計算機は８１９２ビットですから、計算回数は４０９６回 ぐらいです。 この回数だけ、掛け算と比較と足し算または引き算が動きます。 計測した結果、掛け算が死ぬほど遅いということが分かりまし た。 /*========================================================*/ その前に、計算回数を減らしましょう。少し、多すぎます。 CXInt& CXInt::sqrt( void ) { CXInt a( *this ); // 自分を複製 int pos = SIZE * 8 / 2; // 限界値のビット位置 // 最初の比較（オーバーフローチェック） clear().setBit( pos-- ).dec(); // x = 65535 if( a.cmp( copy().pow() ) >= 0 ) return *this; // ret 65 // 自分を初期化 clear().setBit( pos-- ); // x = 32768 // ２回目以降の比較 for( ; pos; pos-- ) { if( a.cmp( copy().pow() ) > 0 ) add( CXInt().setBit( else sub( CXInt().setBit( pos ) ); } if( a.cmp( copy().pow() ) > 0 ) inc(); if( a.cmp( copy().pow() ) < 0 ) dec(); return *this; } 最初のビット位置を、最大位置にしていますが、これを間引き しましょう。 CXInt a( *this ); // 自分を複製 // 最初の比較（オーバーフローチェック） clear().setBit( SIZE * 8 / 2 ).dec(); // x = 65535 if( a.cmp( copy().pow() ) >= 0 ) return *this; // ret 65 // 最初の計算位置を求める CXInt mask; int pos = 0; mask.setBit( pos ); while( pos < SIZE * 8 - 1 && a.cmp( mask ) > 0 ) { mask.setBit( pos, 0 ); pos++; mask.setBit( pos ); } mask.setBit( pos, 0 ); pos = pos / 2 + 1; // 自分を初期化 clear().setBit( pos-- ); // x = 32768 // ２回目以降の比較 mask.setBit( pos ); CXInt c( *this ); c.pow(); for( ; pos >= 0; pos-- ) { if( a.cmp( c ) > 0 ) add( mask ); else sub( mask ); mask.setBit( pos, 0 ); mask.setBit( pos - 1 ); c.set( *this ); // copy c.pow(); } if( a.cmp( copy().pow() ) > 0 ) inc(); if( a.cmp( copy().pow() ) < 0 ) dec(); return *this; という感じにしてみましょう。 前半のループは、最大のビット位置を検索しています。 後半のループでは、少し早くなるように、マスクを大事に計算 するようにしました。 /*========================================================*/ かなり早くなりましたが、答えが違います。がーん。 {magclick} /*========================================================*/ さいごに /*========================================================*/ {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 |