|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第５８２回 加算表の計測 発行 ２００５年７月４日（月曜日） 発行数 約２６００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 ７月ですか、来月は８月ですね。 夏ですねぇ、梅雨もまだだというのに。。 まぁ、夏になれば、ダンスパウダー（すもっぐ）による雨が降る ので、大丈夫でしょう。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 加算表の計測 ＞＞ /*========================================================*/ 前回作った素因数分解処理は、こんな感じでした。 CString prime( __int64 d, UINT& t ) { char buff[ 1024 ]; memset( buff, 0, sizeof( buff ) ); char* pch = buff; char* pe = buff + 1024 - 64; if( d <= 0 ) return ""; t = timeGetTime(); while( d && ( d & 1 ) == 0 ) { if( pch < pe ) pch += sprintf( pch, " 2 *" ); d >>= 1; } __int64 a = 3; while( a < d ) { if( ( d % a ) == 0 ) { if( pch < pe ) pch += sprintf( pch, " %d *", a ); d = d / a; } else a += 2; } t = timeGetTime() - t; if( d > 2 ) pch += sprintf( pch, " %d", a ); else if( pch > &buff[ 2 ] ) pch -= 2, *pch = 0; if( pch >= pe ) sprintf( pch, " too many" ); return CString( buff ); } これを、c35を参照するように改造します。 ... __int64 a = 3; const int* pc = c35; while( a < d ) ... else { int add = *pc++; if( ! add ) pc = c35_head, add = *pc++; a += add; } /*========================================================*/ 第５７１回にて、素因数分解ツール（VC++7.0専用）の処理速度 を出しました。それと比べてみましょう。 321654987321 3 * 19 * 227 * 24859339 加算表なしの状態で、８７２ｍｓでした。 加算表３５だと、４９０ｍｓでした。答えもあっていました。 加算表３５７だと、４９０ｍｓでした。 加算表３５７１１だと、４４０ｍｓでした。 加算表３５７１１１３だと、４００ｍｓでした。 加算表３５７１１１３１７だと、３８０ｍｓでした。 /*========================================================*/ 2222222222222 2 * 53 * 79 * 265371653 加算表なしの状態で、８．８秒でした。 加算表３５だと、５．２秒でした。答えもあっていました。 加算表３５７だと、５．２秒でした。 加算表３５７１１だと、４．６秒でした。 加算表３５７１１１３だと、４．３秒でした。 加算表３５７１１１３１７だと、４．１秒でした。 /*========================================================*/ 確かに、使わないよりは早くなります。 が、劇的に早くなるようなものではないということが 判りました。 {magclick} /*========================================================*/ さいごに /*========================================================*/ ・・・駄目ですね、この程度の桁数でこんなに時間がかかるよう ならば、駄目ですね。 ６００桁なんて、不可能です。 さらっと試算すると、 １０桁に１０分、 １３桁に（１０００倍の）１６時間、 １６桁に（１０００倍の）２年、 １９桁に（１０００倍の）２０００年、 うーん、。。。 {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 |