メルマガ:あゆしゃのC言語プログラミング
タイトル:あゆしゃのC言語プログラミング(Vol.572) 素因数分解の高速化1  2005/06/10


/*========================================================*/
    <<<あゆしゃのC言語プログラミング>>>
/*========================================================*/
 第572回 素因数分解の高速化1
 発行    2005年6月10日(金曜日)
 発行数   約2600

{magclick}
/*========================================================*/
 はじめに ( 決り文句 )
/*========================================================*/
・このメールマガジンは、主にまぐまぐさんから発行しています。
・ジャンルは、マルチメディアのプログラム、C言語です。
・横60文字で作成し、インデントは大抵半角スペース4つです。
・ここで扱うプログラムは、C言語と半光年以内のものです。
・登録解除は、メルマガのホームページでお願いします。
・過去ログはバックナンバー(下欄参照)を活用して下さい。
・内容は私が感じたもので、最新の技術も、へたれもあります。
・わかりやすさを優先させる為、たまに嘘があるかもしれません。
・セキュリティ突破のため、暗号化された単語があります。

/*========================================================*/
 ご挨拶
/*========================================================*/

 こんにちは。あゆしゃです。

 ヘルペスと診断され、バトルレックス(正:バルトレックス)を
服用し続けるあゆしゃ。

 患部の痛みは我慢できるのですが、合わせて起こる頭痛が困り者
で、

 ちょっとあやしいあゆしゃです。

{magclick}
/*========================================================*/
 今回のお題  << 素因数分解の高速化1 >>
/*========================================================*/

 さて今回は少し話題を変えて、素因数分解のプログラムについて
お話します。

 600桁の数字の素因数分解に成功すると、2000万円の
懸賞金がもらえます。

http://www.rsasecurity.com/rsalabs/node.asp?id=2093

 素因数分解とは、そんなに難しいのでしょうか?

/*========================================================*/

 今回は素因数分解の高速化を考えます。

 高速化ができるポイントとしては、以下の点です。

・%を使っているところ

・素数を+2で進めているところ

・そのほか

 この2つです。

 といっても、アルゴリズムの中核はこの2つしかやっていない
ので、これ以外に高速化を行うポイントがありません。

/*========================================================*/

・%を使っているところ

 割り算なので遅いでしょう、というわけです。

 割り切れるかどうかを判定するだけなので、割り算を展開して、
その点のみに処理を絞れば、多少早くなるはずです。

 つまり、割り切れるという前提で処理を進めて行き詰ったら終了
というような処理を組むのです。

 掛け算のアルゴリズムで紹介したように、階段状に並んでいる
同じ数字の和が掛け算の解なので、その逆をたどります。

 具体的には、

__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}
/*========================================================*/
 さいごに
/*========================================================*/

 ただー。

 変数が多く、64ビット変数のオーバーネックも気がかりです。

 おとなしくライブラリの割り算を使ったほうがはやいかも
しれませんね。

{magclick}
/*========================================================*/
 次回予告
/*========================================================*/

 次回は6月13日(月曜日)に、第573回をお送りします。
 お題は「素因数分解の高速化2」

 第2のポイントです。

 お楽しみに!

/*========================================================*/
 最後の決り文句
/*========================================================*/
 このメールマガジンは、まぐまぐさんから発行しています。
 このメールマガジンを解除したい場合は、まぐまぐさんをご利用
ください。このメルマガのまぐまぐアイディーは最後にあります。
 このメールマガジンには広告が挿入されていますか?
 このメールマガジンの内容に文面の引用はありませんか?
 めーらっくすの場合はめーらっくすの利用方に従ってください。
 このメールマガジンの内容の、転用、流用、宣伝、リンク、
この2つです。<3つあるがな! なんて大歓迎です。

{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

ブラウザの閉じるボタンで閉じてください。