|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第５７３回 素因数分解の高速化２ 発行 ２００５年６月１３日（月曜日） 発行数 約２６００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 ヘルペスと診断され、バトルレックス（正：バルトレックス）を 服用し続けるあゆしゃ。 １週間の服用の結果、 ★何も変わらない！ まぁ、薬が効くまでに半年かかる場合もある、というらしいので とりあえずは様子を見ましょう、ということになりました。 バトルレックスは、（高いのはともかくとして）大量に投与でき ない薬だということで、処方ストップです。 しかし、痛みが結構きついので、痛み止めをいただくことに なりました。 ★痛み止めとして有名な「ロキソニン」をいただきました。 ロキソニンは、痛みを引き起こす代謝作用を抑制する薬で、 副作用が少なく、効果が高いという、とんでもない薬です。 あゆしゃ、ロキソニン初体験です。 服用した結果、驚くほどの効き目です。 すごいなぁ、近代医学。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 素因数分解の高速化２ ＞＞ /*========================================================*/ さて今回は少し話題を変えて、素因数分解のプログラムについて お話します。 ６００桁の数字の素因数分解に成功すると、２０００万円の 懸賞金がもらえます。 http://www.rsasecurity.com/rsalabs/node.asp?id=2093 素因数分解とは、そんなに難しいのでしょうか？ /*========================================================*/ 今回は素因数分解の高速化を考えます。 高速化ができるポイントとしては、以下の点です。 ・％を使っているところ ・素数を＋２で進めているところ ・そのほか この２つです。 といっても、アルゴリズムの中核はこの２つしかやっていない ので、これ以外に高速化を行うポイントがありません。 /*========================================================*/ 今回は２つ目。 ・素数を＋２で進めているところ 偶数は素数ではないので、処理をする必要がありません。 よって、３を始めとする奇数のみを処理しています。 else a += 2; しかしこれだと、９や１５といった、素数ではない数字も処理 してしまいます。 これを処理しないためには、加算テーブルを使用します。 ２の倍数を飛ばすだけを考える場合、 const int skip[] = { 2,2,2,2,2, ... 0 }; const int* ps = skip; という定義で、実際の加算部分を、 else { a += *ps++; if( *ps == 0 ) ps = skip; } という感じにすればよいでしょう。 そして３の倍数を処理しないようにするには、 3,5,7,9,11,13,15,17,19,21,23,25,27,29,... という数列のうち、９，１５，２１，２７を飛ばしますので、 const int skip[] = { 2,2,4,2,4,2,4,2,4,0 }; このような数列になり、さらに if( *ps == 0 ) ps = skip + 1; // 2,4,2..の先頭に戻る このように初期化位置をずらせば、はしょる処理の完成です。 数列の先頭は、初回の例外処理を意味しています。 さらに５の倍数を処理しない、７の倍数を処理しないという 感じで、数列を巨大なものにすればするほど、処理回数が減り、 高速化します。 /*========================================================*/ Cマガジンでは判りやすいようにif文や関数みたいなもので 紹介されていましたが、この手のものはテーブルを参照するのが 普通です。 /*========================================================*/ ・そのほか アルゴリズム自体を新規に作ることができれば、歴史に名を 残すことができるでしょう。 たとえば、「素数表から逆算する方法」です。 ある数が２つの素数の積であると仮定する場合、１つの素数の ペアとなる素数は１または０なので、検索と同じ要領で処理でき ます。 もっとも、素数表を作るのが大変なのですけどね。 素数って、結構たくさんあるのです。 {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 |