|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４５８回 あゆしゃVS裏目小僧 登場編 発行 ２００４年６月７日（月曜日） 発行数 約２９００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 先日、いつものようにパシパシと碁石を並べて遊んでいたとき、 ふと、 ★変な匂いに気がつきました。 常人の１．００１倍（普通）のあゆしゃの嗅覚を持って、その 発生源を調べたところ、 ★犯人は、碁石でした。 そういえば、買ってから半年間、洗っていませんねぇ・・・？ {magclick} /*========================================================*/ 今回のお題 ＜＜ あゆしゃVS裏目小僧 登場編 ＞＞ /*========================================================*/ 平方根を求めるアルゴリズムは多々あります。 私が数字を並べることによって自力で考えたアルゴリズム、 ★あゆしゃ法、とでも呼びましょうか？ （やっていることは、ただの２分岐なのですけどね） これがいかに高性能であるかどうかは、囲碁のように、戦って のみ証明されるものであります。 よって小官は、裏目小僧殿に戦いを挑むのであります！ 裏目小僧殿を選んだ理由は、勝てそうだったからであります！ 半分嘘であります！ 他の誰のまねでもない（ような）珍しい形をしていたからで、 ありますぅ！！ /*========================================================*/ 対決方法を決めましょうか？（やんわり） １００万回実行して、その動作速度を計りましょう。 このときに計算させる値は、ループ変数を使った定数にしましょ う。 #define MAX_NUM ( 1000000000 - i ) i を直接指定するものと、このMAX_NUMを使って大きな値を指定 するものとの、２種類を実行させましょう。 （大抵の平方根のアルゴリズムは、桁数が多いと実行速度が遅く、 逆に桁数が少ないと異常に速くなります。あゆしゃ法は、桁数に 関係なく処理速度が固定なので、桁数が小さいと不利なのです。） さらに、その計算結果があっているかどうかは、大事なところ です。 １００万回実行して、ライブラリの sqrt() と答えが一致する ことを確認しましょう。 このときに計算させる値は、乱数にしましょう。 rand() は１６ビットの乱数を発生させるので、これをあわせ ます。 #define RAND32 ( ( ( UINT )rand() << 16 ) + ( UINT )rand() ) 処理としては、こんな感じでしょうか。 t = timeGetTime(); i = 1000000; do { ret = ays_sqrt( i ); } while( --i ); i = 1000000; do { ret = ays_sqrt( MAX_NUM ); } while( --i ); t = timeGetTime() - t; // 処理速度を決定 t = t / 2; // 2000000回実行しているので補正する err = 0; i = 1000000; do { r = RAND32; if( ays_sqrt( r ) != ( UINT )sqrt( ( double )r ) )err++; } while( --i ); printf( "%40s%5d.%03dus / 1time err:%d\n", "UINT ays_sqrt( UINT )", t / 1000, t % 1000, err ); こんな感じでしょうか。 １００万回の処理速度を秒で求めているので、単位を１００万分 の１である us ＝マイクロ秒にすれば、１回あたりの処理速度に なります。 ループ処理の処理速度も含みますが、まぁ、誤差範囲でしょう。 /*========================================================*/ 改めて紹介します。あゆしゃ法のプログラムです。 UINT ays_sqrt( UINT a ) { UINT x; if( a >= ( UINT )65535*( UINT )65535 ) return 65535; if( a >= 32768*32768 ) x = 32768+16384; else x = 16384; if( a >= x * x ) x += 8192; else x -= 8192; if( a >= x * x ) x += 4096; else x -= 4096; if( a >= x * x ) x += 2048; else x -= 2048; if( a >= x * x ) x += 1024; else x -= 1024; if( a >= x * x ) x += 512; else x -= 512; if( a >= x * x ) x += 256; else x -= 256; if( a >= x * x ) x += 128; else x -= 128; if( a >= x * x ) x += 64; else x -= 64; if( a >= x * x ) x += 32; else x -= 32; if( a >= x * x ) x += 16; else x -= 16; if( a >= x * x ) x += 8; else x -= 8; if( a >= x * x ) x += 4; else x -= 4; if( a >= x * x ) x += 2; else x -= 2; if( a >= x * x ) x += 1; else x -= 1; if( a > x * x ) x++; if( a < x * x ) x--; return x; } /*========================================================*/ 対するは裏目小僧さんの、 ・・・ ・・・・・・ ・・・・・・・・・（ホームページ、閉鎖したらしいよ！） ・・・・・・・・・・・・な、なんですとぉ！？ {magclick} /*========================================================*/ さいごに /*========================================================*/ 新C言語使いにおくるチョー基本講座 第４回。 i = 10; do { test(); } while( --i ); と記述したとき、test()は、i が１０〜１の時に実行されます。 while では、i を -1 してから、それが 0 以外の場合にループ が続行されますので。 つまり、１０回実行されるのです。 これは、 for( i = 0; i < 10; i++ ) test(); と書くのと、同じことです。 しかし動作速度が違います。 for は人間の見やすい形にまとめてあるため、機械語がごちゃ ごちゃしており、かなり動作が遅いのです。 ★間ぁ違いない！ では、 i = 10; do { test(); } while( --i ); このように記述すると速いのかというと、速い、と思います。 思いますでは駄目ですね。 ★きっと速いです。 for 文と違って、デクリメントした後すぐにその計算結果が０か どうかが（コンディションステータスによって）判定されるため、 無駄がないはずです。 でも見づらいので、私も普段は使いません。 （でもアセンブラ言語では、０判定のループを使うのが普通です） {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は６月１１日（水曜日）に、第４５９回をお送りします。 お題は「あゆしゃVS裏目小僧 対決編」 どうなるのか・・・？ 不戦勝？ お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 現在の勝率５割。万年５級かな？＜囲碁 なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ ホームページ::あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp まぐまぐ::アイディー 0000020674 まぐまぐ::登録と解除 http://www.mag2.com/m/0000020674.htm まぐまぐ::バックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 めーらっくす::アイディー MM3E1AEE285AB4F めーらっくす::登録と解除 http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F めーらっくす::バックナンバー★最近のものならこちらが便利★ http://www.mailux.com/mm_bno_list.php?mm_id=MM3E1AEE285AB4F |