|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４５９回 あゆしゃVS裏目小僧 対決編 発行 ２００４年６月９日（水曜日） 発行数 約２９００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 先日、株の売買ゲームに登録しました。 野村のバーチャル株式投資倶楽部 http://www2.nomura.co.jp/vstock/VirtualServlet? 仮想のお金（初期値：１００万円）と、実際の株式の状態を元に 資金を増やすゲームです。 参加費は無料で、扱われる株式の値段は本物ですので、株の お勉強に最適です。 月曜日現在、９９８５７５円、第４４６５７位です。 まだ、買った株式の手数料が引かれているだけで、株価の上がり 下がりは含まれていません。 上位の人は１０億ぐらい。・・・がんばろっと。 {magclick} /*========================================================*/ 今回のお題 ＜＜ あゆしゃVS裏目小僧 対決編 ＞＞ /*========================================================*/ 裏目さんのホームページにアクセスできなくなったので、変だと 思っていたのですが、調査の結果、 ★環境によってアクセス拒否される という、気難しい（？）サーバでした。 なぜ気難しいのか、その原因は、DNSの変更のためという補足を いただきました。 現状 OK URL http://banana235.maido3.com/~bs3179/urame/prog/ALGO.HTM DNS 変更後 OK URL http://www.tensyo.com/urame/prog/ALGO.HTM /*========================================================*/ 改めまして、裏目さんのプログラムを紹介します。 #define U32 unsigned long #define U16 unsigned short #define S32 signed long #define S16 signed short unsigned isqrt(U32 x) { int sft=0; U16 y,y0,y1,sum; U32 x0=x; if(x<2) return x; while( 0<(S32)x){x<<=1L; sft++;}; y1=(U16)(x>>16L); y0=(~y1)&0xffff; y=(y0*0x8000)>>16; sum=y; y=(y*y0)>>16; y=(y*0x4000)>>16;sum+=y; y=(y*y0)>>16; y=(y*0x8000)>>16;sum+=y; y=(y*y0)>>16; y=(y* 40960)>>16;sum+=y; y=(y*y0)>>16; y=(y* 45875)>>16;sum+=y; y=~sum; y+= ( (S16)((x-(U32)y*(U32)y)>>16L))>>1; if(sft&1) { sft>>=1; y= (U16)((0x8000L+(U32)(y>>sft)*46341L)>>16L); }else { sft>>=1; y= y>>sft; }; return y; } （VC環境でコンパイルを通すため、多少修正しました） ループは最初の、桁数を叩き割る処理だけで、後は固定の計算の ようです。 計算回数は、見た目は少なそうです。 計算の内容は、アルゴリズム独特のマジックワードがいっぱいで 良くわかりません。 /*========================================================*/ 早速ですが、前回紹介したプログラムの結果です。 １回目 UINT ays_sqrt( UINT ) 0.185us / 1time err:0 UINT isqrt( UINT ) 0.656us / 1time err:483419 ２回目 UINT ays_sqrt( UINT ) 0.185us / 1time err:0 UINT isqrt( UINT ) 0.681us / 1time err:483419 ★動作速度については、ays_sqrt の圧勝となりました！ ★整合性については、ays_sqrt の圧勝となりました！ ★トータルポイントにおいて、ays_sqrt の圧勝となりました！ ★ばんざーい！ ★ばんざーい！ ★ばんざーい！ ★ばんざー・ /*========================================================*/ よかったよかったーー；（ほんのり） 負けたら CXInt に入れたいけど、マジックワードが良くわから ないのでどうやって謝ろうかと考えていたのですが、杞憂であった ようです。 世界最速なのだから、負けるはずがありませんよね！ 桁数が小さければ、とふと思いましたが、裏目さんのものは、 桁数を割ったあとの計算回数は同じなので、たいした違いはないで しょう。 /*========================================================*/ ちなみに裏目さんアルゴリズムの最大の敗因と思われるものは、 環境の変化です。 /*========================================================*/ 裏目さんのプログラムは、マイコンで動かすことを前提として 作られています。 よって、マイコンが持つ掛け算の処理速度が、重要です。 インテルの掛け算は、１クロックぐらいで処理されます。これは 足し算と変わりがありません。 掛け算のアルゴリズムで紹介したとおり、掛け算は単純なので、 気合と根性と電圧があれば、物理的に実現できるのだそうです。 しかしマイコン、それも昔のマイコンだと、int ( short ) の 掛け算で１０クロックはかかると思います。 ３２ビットの UINT はもっと遅いかもしれません。１５ぐらい？ そのような環境では、掛け算の回数がものを言いますので、 あゆしゃ法 １６回 裏目小僧法 １１回 掛け算の回数だけを見れば、裏目さんのほうが勝りますので、 結果が逆転したかもしれません。 /*========================================================*/ ちなみに、掛け算よりシフトのほうが速いという伝説を聞いた ことがあるかと思いますが、現在においては、 ★真っ赤なうそ という時代になりました。 シフト数を１６とした場合、掛け算の２倍の時間がかかります。 もちろん、１５や１４といった中途半端（８の倍数ではない）な 値を指定した場合、もっと遅くなります。 騙されてはいけません。 /*========================================================*/ ソースコードの掲載とリンクについては、裏目小僧さんに了解を いただいています。 {magclick} /*========================================================*/ さいごに /*========================================================*/ 新C言語使いにおくるチョー基本講座 第５回。 y=(y*y0)>>16; y=(y* 40960)>>16;sum+=y; このように、ソースに直接かかれた数字のことを、 ★リテラル値 といいます。 そして１６はともかく４０９６０といった、出所の分からない マジックワードは、リテラル値で書いては駄目、というのが一般的 なコーディングのルールです。 なぜかというと、もしもこれがオチャッピーにより、 y=(y*y0)>>16; y=(y* 40980)>>16;sum+=y; となっていたとしても、バグに気がつきにくいのです。 そして数字のうち間違えは、結構あるものです。 変数ならば、名前が違うとコンパイラが教えてくれますから安全 なのですが、 数字が１文字違ってもコンパイルエラーになりませんし、そのま ま、普通っぽく動いてしまうので、 怖いものです。 ではどうするかというと、マクロか定数を使います。 #define ISQRT_NUM40960 40960 const int ISQRT_NUM40960 = 40960; という感じでしょうか。 マクロ名称や定数名称に、その定数の数字を表記するのは、 １つの安全策です。 これなら、数字のうち間違いについて、コンパイルエラーが 発生して、安全です。 ソースの見易さとデバッグのしやすさも向上します。 逆に数字の部分がないと、「このマクロの値は何だっけ？」と、 デバッグ中に大騒ぎすることになります。 {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は６月１３日（金曜日）に、第４６０回をお送りします。 お題は「平方根の残骸」 あゆしゃ法を作るに当たり、いくつかの失敗作がありました。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 目指せ億万長者！＜仮想＜夢想 なんて大歓迎です。 {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 |