|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第４５６回 掛け算の高速化 発行 ２００４年６月２日（水曜日） 発行数 約２９００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンはまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・このメールマガジンは、横６０文字で作成しています。 また、インデントはすべて半角スペース４つで構成しています。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、まぐまぐさんのホームページでお願いします。 ・まぐまぐさんのバックナンバー（下欄参照）を活用して下さい。 ・ここは私の復習の場です。内容は約１ヶ月内外に私が勉強した 内容になっています。最新の技術があれば、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 先日、平方根のアルゴリズムを検索（調査）していたところ、 このようなページを発見しました。 http://www.tensyo.com/urame/index.html ３２ビットの平方根について、かっこいいアルゴリズムで問題を 解決しているページです。 ★これは、どちらが強いか、対決しなければ！ 私は世界最速といって HP に掲載しているわけですから、負ける わけには参りません。 しかし、このアルゴリズムは計算回数が少ないです。 強敵ですね！ 管理人さんに許可を頂、近日、 ★「あゆしゃVS裏目小僧」 をお送りします。お楽しみに！ {magclick} /*========================================================*/ 今回のお題 ＜＜ 掛け算の高速化 ＞＞ /*========================================================*/ 前回作ったストップウォッチで、平方根の処理時間を計測して みました。 平方根 123456789123456789123456789123456789 答え 351364183040128307 この答えを出すまで、0.671秒でした。 敵対する（？）ガウスさんは、1.412秒でした。 ・・・なんだか、すでに勝っていますね。 高速化、やめようかなぁ。。。 /*========================================================*/ まぁ、物は試しに。 それに、もっと化け物のような桁数を計算することが、この大型 計算機の目的なのですから、この程度で満足してはいけません。 現在の掛け算処理は、 CXInt& CXInt::mul( CXInt& b ) { CXInt a( *this ); clear(); do { if( *b.m_buff & 1 ) add( a ); a.shl(); b.shr(); } while( b.noZero() ); return *this; } こんな感じです。まぁ、かわいいこと。 癪に障るので（何？）、死ぬほど高速化してみました。 CXInt& CXInt::mul( CXInt& b ) { CXInt a( *this ); clear(); USHORT* p0 = ( USHORT* )m_buff; USHORT* p2 = ( USHORT* )b.m_buff; USHORT* p02, *p1; ULONG c; int i = SIZE / 2, i2; do { p02 = p0; p1 = ( USHORT* )a.m_buff; c = 0; i2 = i; do { c = (ULONG)*p1++ * (ULONG)*p2 + c + (ULONG)*p02; *p02++ = ( USHORT )c; c = ( c >> 16 ); } while( --i2 ); p0++; p2++; } while( --i ); return *this; } 平方根 123456789123456789123456789123456789 答え 351364183040128307 速度 0.390 計算結果は同じですね。（ほっ） しかし速度が倍、とまではいきませんでしたか。まぁ、早くは なりました。 中で何をやっているのかというと、関数呼び出しを展開し、さら にシフトではなく掛け算を使うようにしました。 ULONGではオーバーフローするので、USHORTで計算しています。 でも見た目があれですから、やっぱりやめておきましょうか。 シンプルがベストです。 /*========================================================*/ ものはためしに、死ぬほどの桁数を入れてみましょう。 平方根 123456789123456789123456789123456789123456789123456789123456 789123456789123456789123456789123456789123456789123456789123 456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456 789123456789123456789123456789123456789123456789123456789123 456789123456789123456789123456789123456789123456789123456789 123456789123456789123456789123456789123456789123456789123456 789123456789123456789123456789123456789123456789123456789123 456789123456789123456789 答え 351364183040128307730566988443067497857502076939339458730666 383836849678991500248239574528915859993488962220277903409365 064689017208581620470190920176396820853572455741907668904504 163298885534486581451024904953370597548887042117635491414202 411366959969 速度 34.232秒 従来版 2.023秒 高速化版 あー、高速化は必要ですか、やっぱり。 ★従来版、フリーズしたかと思いました＾＾ 従来版では駄目ですか。しかし高速化版でこれだけの速度がでる なら、暴動もおきないでしょう。 しかしあっているのでしょうかね、これ？ {magclick} /*========================================================*/ さいごに /*========================================================*/ 新C言語使いにおくるチョー基本講座 第２回。 コンピュータの処理速度は、とても速いです。 その速さを示すのが、「CPU が１メガヘルツ」という感じで表す ★ヘルツ という単位です。 １ヘルツは１秒に１回、という意味です。 １メガは１００万の単位なので、 CPU が１メガヘルツというと、１秒間に１００万回の処理を 行えることを示します。 その１回の処理にかかる時間は１ナノ秒、とても早いです。 １ナノ秒は１０億分の１秒です。 １秒＝１０００ミリ秒。 １ミリ秒＝１０００マイクロ秒。 １マイクロ秒＝１０００ナノ秒。 １ナノ秒＝１０００ピコ秒。 それ以上は、きかないでください。 さて、１メガの CPU で演算を行うのに１秒かかったということ は、１つの演算で１００万回の小さな処理を行った、という意味に なります。 高速化は、小さな処理の回数を少なくして、同じ結果が得られる ように、えっちらおっちら、努力することをいいます。 {magclick} /*========================================================*/ 次回予告 /*========================================================*/ 次回は６月４日（金曜日）に、第４５７回をお送りします。 お題は「フォーミュラコピー」 ガウスさんで、答え合わせを行うことにしましょう。 そのとき、１つ１つコピーペーストしていては、面倒です。 ガウスさんが理解できる式をコピーするボタンを作りましょう。 お楽しみに！ /*========================================================*/ 最後の決り文句 /*========================================================*/ このメールマガジンは、まぐまぐさんから発行しています。 このメールマガジンを解除したい場合は、まぐまぐさんをご利用 ください。このメルマガのまぐまぐアイディーは最後にあります。 このメールマガジンには広告が挿入されていますか？ このメールマガジンの内容に文面の引用はありませんか？ めーらっくすの場合はめーらっくすの利用方に従ってください。 このメールマガジンの内容の、転用、流用、宣伝、リンク、 遥かな押入れより扇風機降臨 なんて大歓迎です。 {magclick} /*========================================================*/ /*========================================================*/ 発行者 あゆしゃ ホームページ::あゆしゃの世界 http://ayusya.hp.infoseek.co.jp/ ご意見・ご感想・ご質問メール mailto:ayusya@flamenco.plala.or.jp まぐまぐ::アイディー 0000020674 まぐまぐ::バックナンバー http://jazz.tegami.com/backnumber/frame.cgi?id=0000020674 まぐまぐ::登録と解除 http://www.mag2.com/m/0000020674.htm めーらっくす::アイディー MM3E1AEE285AB4F めーらっくす::登録と解除 http://www.mailux.com/mm_dsp.php?mm_id=MM3E1AEE285AB4F めーらっくす::バックナンバー★最近のものならこちらが便利★ http://www.mailux.com/mm_bno_list.php?mm_id=MM3E1AEE285AB4F |