|
|
/*========================================================*/ ＜＜＜あゆしゃのＣ言語プログラミング＞＞＞ /*========================================================*/ 第５７２回 素因数分解の高速化１ 発行 ２００５年６月１０日（金曜日） 発行数 約２６００ {magclick} /*========================================================*/ はじめに （ 決り文句 ） /*========================================================*/ ・このメールマガジンは、主にまぐまぐさんから発行しています。 ・ジャンルは、マルチメディアのプログラム、Ｃ言語です。 ・横６０文字で作成し、インデントは大抵半角スペース４つです。 ・ここで扱うプログラムは、C言語と半光年以内のものです。 ・登録解除は、メルマガのホームページでお願いします。 ・過去ログはバックナンバー（下欄参照）を活用して下さい。 ・内容は私が感じたもので、最新の技術も、へたれもあります。 ・わかりやすさを優先させる為、たまに嘘があるかもしれません。 ・セキュリティ突破のため、暗号化された単語があります。 /*========================================================*/ ご挨拶 /*========================================================*/ こんにちは。あゆしゃです。 ヘルペスと診断され、バトルレックス（正：バルトレックス）を 服用し続けるあゆしゃ。 患部の痛みは我慢できるのですが、合わせて起こる頭痛が困り者 で、 ちょっとあやしいあゆしゃです。 {magclick} /*========================================================*/ 今回のお題 ＜＜ 素因数分解の高速化１ ＞＞ /*========================================================*/ さて今回は少し話題を変えて、素因数分解のプログラムについて お話します。 ６００桁の数字の素因数分解に成功すると、２０００万円の 懸賞金がもらえます。 http://www.rsasecurity.com/rsalabs/node.asp?id=2093 素因数分解とは、そんなに難しいのでしょうか？ /*========================================================*/ 今回は素因数分解の高速化を考えます。 高速化ができるポイントとしては、以下の点です。 ・％を使っているところ ・素数を＋２で進めているところ ・そのほか この２つです。 といっても、アルゴリズムの中核はこの２つしかやっていない ので、これ以外に高速化を行うポイントがありません。 /*========================================================*/ ・％を使っているところ 割り算なので遅いでしょう、というわけです。 割り切れるかどうかを判定するだけなので、割り算を展開して、 その点のみに処理を絞れば、多少早くなるはずです。 つまり、割り切れるという前提で処理を進めて行き詰ったら終了 というような処理を組むのです。 掛け算のアルゴリズムで紹介したように、階段状に並んでいる 同じ数字の和が掛け算の解なので、その逆をたどります。 具体的には、 __int64 d2 = 0; // 名前適当 __int64 b = 0; __int64 i = 1; __int64 a2 = a; switch( ) // 処理回数 { case 30 : if( ( a2 ^ d2 ) & i ) b|=i, d2+=a2; i<<=1; a2<<=1; ... case 3 : if( ( a2 ^ d2 ) & i ) b|=i, d2+=a2; i<<=1; a2<<=1; case 2 : if( ( a2 ^ d2 ) & i ) b|=i, d2+=a2; i<<=1; a2<<=1; case 1 : if( ( a2 ^ d2 ) & i ) b|=i, d2+=a2; } という感じにできるはずです。 breakは、書き忘れではありません。 可変長の演算で、ループの終了判定を省略したい場合に、このよう にします。 処理回数があらかじめわかっている場合に使うことができます。 割り算なので、処理回数は 「dの桁数」−「aの桁数」 となります。 ついでに、割り切れたときに割り算の解も求められるはずです。 {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 |