|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４６０回 平方根の残骸 発行 ２００４年６月１１日（金曜日） 発行数 約２９００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 先日、このようなページを見付けました。 http://park3.wakwak.com/~ore/ 中でも、このページがお勧めです。（リンクフリー） http://park3.wakwak.com/~ore/application/telmemo/index.html なかでも、シャア専用がお勧めです。シャア専用ですよ！ 先日、株の売買ゲームに登録しました。 野村のバーチャル株式投資倶楽部 http://www2.nomura.co.jp/vstock/VirtualServlet? 仮想のお金（初期値：１００万円）と、実際の株式の状態を元に 資金を増やすゲームです。 参加費は無料で、扱われる株式の値段は本物ですので、株の お勉強に最適です。 私は木曜日現在、999,865円です。（49,945番／90,783人中） やや、下がってしまいました。 しかし、大分となれたもので、１位の人の金額が９９００万円だ という新事実を把握できるまでになりました。 １０億円と勘違いしたのは、桁を１つ読み間違えていたよう です。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 平方根の残骸 ＞＞ /*========================================================*/ あゆしゃが平方根のアルゴリズムを考えるようになったきっかけ は、ガウスさんでした。 http://www.vector.co.jp/soft/dl/win95/personal/se119757.html ガウスさんのヘルプにて、ニュートン法という言葉を初めて目に して、衝撃を受けたのです。 そこで、ニュートン法とは何ぞやと、調べたところ、このページ を見付けました。 http://www.sm.rim.or.jp/~shishido/newton.html ここにあったプログラムを真似して、このプログラムを作ったの が、あゆしゃの初めての平方根です。 // while( x * x < a ) x++; // 二乗がaを超える最小のxを求める for( cnt = 0; cnt < 10; cnt++ ) { // 精度レベル x2 = x; x = ( x + a / x ) / 2; // 二乗してaになるxに近づける if( x2 == x ) break; // 結果がかわらなくなったら終了 } とりあえずインクリメントは馬鹿なのではずして、後は精度 レベルをどうしようかなぁと、考えました。 しかし割り算がどうしても嫌でした。 ★そこで、インクリメントに注目しました。 インクリメントは、数列を線形検索しているわけなので、すこし はしょれないかと、思ったのです。 そうして考えているとき、平方根が０〜６５５３５の中に必ず 存在するということに気がつきました。 そこで、検索だけで最後まで求められるはずだと思ったのです。 for( x = 30000; x < 65500; x += 30000 ) if( a < x * x ) break; for( x2 = x, x = x - 10000 + 1000; x < x2; x += 1000 ) if( a < x * x ) break; for( x2 = x, x = x - 1000 + 100; x < x2; x += 100 ) if( a < x * x ) break; for( x2 = x, x = x - 100 + 10; x < x2; x += 10 ) if( a < x * x ) break; for( x2 = x, x = x - 10 + 1; x < x2; x += 1 ) if( a < x * x ) break; x++; // これがないと誤差が10万回に1回の確率で出てしまう はじめはこのように、１０進数で考えていました。 そしてこれを、もっと速くしようと思ったのです。 for( x = 30000; x < 65500; x += 30000 ) if( a < x * x ) break; for( x2 = x, x = x - 30000 + 10000; x < x2; x += 10000 ) if( a < x * x ) break; for( x2 = x, x = x - 10000 + 2000; x < x2; x += 2000 ) if( a < x * x ) break; for( x2 = x, x = x - 2000 + 400; x < x2; x += 400 ) if( a < x * x ) break; for( x2 = x, x = x - 400 + 80; x < x2; x += 80 ) if( a < x * x ) break; for( x2 = x, x = x - 80 + 16; x < x2; x += 16 ) if( a < x * x ) break; for( x2 = x, x = x - 16 + 4; x < x2; x += 4 ) if( a < x * x ) break; for( x2 = x, x = x - 4 + 1; x < x2; x += 1 ) if( a < x * x ) break; x++; // これがないと誤差が10万回に1回の確率で出てしまう IF が増えただけですが（笑）。 しかしあまり速くなく、この方法に限界を感じました。 さらに、誤差が出てしまうのが悩みの種でした。 ★そこで、ふとひらめいたのです。２進数にしようと！ for( x = 32768, cnt = 16384; cnt; cnt >>= 1 ) { if( a >= x * x ) x += cnt; else x -= cnt; } x += 2; これはかなり速く、やばいと思いました。 もっとやばくしようと、ループを展開しました。 if( a >= 32768*32768 ) x = 32768+16384; else x = 32768-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; x += 2; 現在のもののほとんどが、このときに完成しました。 しかし、あゆしゃに立ちはだかる壁がありました。 誤差が出るのです。 ＋２でごまかしていますが、完全ではありませんでした。 そこで、エラーになる数字をざーーーーーーーーーっと並べて、 どうやればエラーを防げるかを考えました。 そこで、 // 求める値を超える状態にする 実行されない場合もある if( a > x * x ) x++; // 求める値を初めて下回る状態にする（小数点以下を切捨てる） // 実行されない場合もある if( a < x * x ) x--; この２行の補正を、編み出したのです。 リリアンのように。 コメントには、おっかなびっくり感が残っていますね。 {magclick} /*========================================================*/ さいごに /*========================================================*/ 新C言語使いにおくるチョー基本講座 第６回。 プログラミングの作業を早く片付けようと思う場合、私は長い プログラムを書くようにしています。 長い、つまり丁寧なプログラムです。 本文の、「ざーーーーーーっと」と、同じことです。 １行で書けるやん、というものでも、丁寧に、なでるように、 組み立てます。 最初は、自分自身も処理に精通していないため、あまり トリッキーなことをしてしまうと、やばいのです。 それから、少し余裕が出たら、プログラムを小さく再構成 します。 バグはプログラム量と比例するといいますので、小さい プログラムのほうが、バグが少ないのです。 再構成、っていうか、作り直しです。 ★実はこれが楽しい＾＾； 丁度そのころ、私はコメントを書きます。 初めてプログラムを書くときは、コメントは面倒くさいし、 しかし３日たつとプログラムがわからなくなるので、 必死こいてコメントを書きます。 最善なのは、初回に書くことなのですけれども。 {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 |