e-Gadget - プログラム関数電卓　fx-5800Pで素因数分解再び

fx-5800Pで素因数分解再び

【2014/10/29 再修正】
【2013/12/04 修正】
【2014/12/05 誤字修正】

以前、fx-5800Pで作った素因数分解のプログラムを紹介した。

以前の記事は、fx-5800Pで素因数分解を参照。

素因数を見つけるループの１回の実行時間を推定したところ、45ミリ秒ほどかかっていることが分かった。全ての自然数を検索する方法では実測値が[素因数の数和] × 45ミリ秒の計算値とほぼ一致したことから、このループの実行時間はほぼ45ミリ秒程度とと考えている（その後、奇数のみを調べるようにプログラムを変更している)。

これを読んで下さったKENさん(長野県)からコメント(非公開)を頂き、「条件にもよるが大幅に高速化できる」という具体的なプログラムソースの改善案を頂いた。

=========================
ある数Xの素因数をするときにはsqrtXまで調べれば十分であることを使いました。（例えば51を素因数分解するのに、7まで調べたら9以上は調べる必要がない）
以下Lp Whileの前後に追加したソースです。
---
If C=0 And D>Y
Then 0→Y
If End
Lp While Y≧1
If Y=0 And X≠1
Then X⊿
"TO THE":1⊿
If End
---
いかがでしょうか。
こうすることで特に（素因数分解の最後に残る）大きい素数が、一つだけ出てくるときに効果を発揮します。
12345の素因数分解（823の素数判定）はわずか1秒ほどで終わります。ただし、521×523＝272483のように最大の素数とそれに次ぐ素数の差が小さいときは、ソースが増えた分、元のプログラムよりも数秒余計にかかってしまうようです。

3時間以上かかったという987654321は30秒で終わりました。
この案、是非いかがでしょうか。
=========================

ありがとうございます。改めてKENさんにお礼を申し上げます。

頂いたコンセプトに従って、具体的にプログラムの改良を試みたので紹介する。

元のプログラムソースに、赤で示した３行を追加することで、このコンセプトの追加ができた【修正】。

なお、元のプログラム名「Factorizing」は因数分解と言う意味で不適切だったので、素因数分解：Prime Decompositionから、プログラム名を「PRIME DECOMP」と変更した(青字で変更を示した）。

fx-5800P用
素因数分解改良プログラム
PRIME DECOMP
====================
Lbl 0
Cls
"PRIME DECOMP"
"INPUT INTEGER"?→A
0→C:2→D:A→X
Do
X÷D→Y
If C=0 And Y<D : 2014/10/29 修正
Then X→D:X÷D→Y
IfEnd
If Frac(Y)=0
Then Y→X:Isz C
Else
If C≠0
Then
D▲
"TO THE":C▲
0→C
IfEnd
If D=2
Then Isz D
Else Isz D:Isz D
IfEnd
IfEnd
LpWhile Y≧1
Cls
"COMPLETED"
""
"<->:TRY OTHERS"
":QUIT"
While Getkey≠67
WhileEnd
Goto 0
====================

KENさんのご提案よりも変更部分の少ない修正にしてみた(赤の部分)。

なお、この If C=0 And Y<D [2014/10/29 修正] による判定はループが回るたびに必ず１回実行されるが、中の Then x→D:X÷D→Y は１回しか実行されないので、ループの実行速度は、KENさんのご提案と変わらない。

この If 文の判定だが、If C=0 And Y≦√(X) としても良いが、123456789 の素因数分解では１５秒ほど余計に時間がかかる。

平方根よりも小さくなる時、KENさんの案では Y を 0 にしている。私の案では D を X に変更することで、結果的に Y が 1 になる。いずれもDoループを抜けるための方策である。この点でも実行速度に大きな違いは無い。

私の案は、結果表示を新たに追加しないでプログラムを改造するという点にチョットこだわった。D を X に変更すると、結果的に Y が 1 になり、従って最後にもう一回ループが回ることから、Do ループを抜けた後に結果表示のコードを書く必要が無くなるわけだ。

この変更により、実行時間が以下のように大幅に改善された【修正】。

入力した自然数	結果	改造前の時間	改造後の時間
12345	3 x 5 x 823	２０秒	２．５秒
123456	2⁶ x 3 x 643	２０秒	３秒
1234567	127 x 9721	４分	１秒
12345678	2 x 3² x 47 x 14593	６分	８秒
123456789	3² x 3607 x 3803	約５分	３分
987654321	3² x 17² x 379721	３時間以上	３３秒
98765432	2³ x 37 x 333667	２．５時間	４３秒
9876543	3 x 227 x 14503	６分	12秒
987654	2 x 3 x 97 x 1697	７秒	６．５秒
98765	5 x 19753	８分	８秒
9876	2² x 3 x 823	２０秒	３秒

目を見張るべき時間短縮となった( ^o^)ノ

KENさんのご指摘のように、大きな素因数が１つだけ出てくる場合に速度向上が顕著だ。しかし、3² x 3607 x 3803 のように似たような３桁の素因数が含まれる場合は、それほど大きな高速化はできない。√X の効果が出るまでに、D を２づつ増やすのに時間がかかるためと考えている。その証拠に一旦 3607 が出ると、次の 3803 がほぼ瞬時に得られる。

なお、今回の改善で計算速度は向上したが、カシオの最新の関数電卓 fx-995ES に内蔵されている素因数分解の計算速度には及ばない。

応援クリックをお願いします。励みになるので．．．

にほんブログ村

人気ブログランキング

FC2ブログランキングへ

keywords: fx-5800P、fx-995ES、プログラム、素因数分解、プログラム関数電卓

リンク集　|　ブログ内マップ

関連記事

テーマ : プログラム関数電卓
ジャンル : コンピュータ

このページのトップへ

前の記事 « ホーム » 次の記事

トラックバック

この記事にトラックバックする(FC2ブログユーザー)

このページのトップへ

コメントの投稿

大変遅くなりました

すけっぴさん

ここのところ、電卓プログラムを触る余裕が無くて放置しており、スミマセン。

本文にあるコードの赤文字の部分の1行目にある

Y≦D

を

Y＜D

に変更することで、問題を解消できるようです。

ありがとうございます。

2014-10-28(21:31) :
やす (Krtyski) URL :
編集

返信ありがとうございます。

プログラムの仕組みについて理解し切れてないので報告になりますが、どうやら素数の二乗が素因数分解できないようです。4,9,25,49どれも素数の二乗ですが上手くいきません。さらに素数の二乗(4,9,25,49...)を素数と間違えて結果に表示される場合があります。144,735などを素因数分解させるとそうなります。
速度を優先させるとしたらいっそこのプログラムのままで、表示の直前にIf 0=Frac( √D) : Then √D→D : 2C→C : IfEnd を入れるのが簡単ですかね。(√素因数は整数でないことを利用)
根本的ではない邪道な案ですが良ければ好きにお使いください。

2014-06-24(17:47) :
すけっぴぃ URL :
編集

バグがわかりました

素因数分解した結果が、2の乗数×3×3 になる時に、9が素因数分解されないことが分かりました。

ソースコードの赤文字部分に問題が有ることも分かりました。

D=3 かつ Y=9 になる時、赤文字部分で悪さするわけです。

次は、これをどのように修正するか、です。

今日のところは、ここまで。

2014-06-24(11:22) :
やす (Krtyski) URL :
編集

ふ～む、どういうことでしょうか？

すけっぴぃさん

こんばんは、

> 18や144を素因数分解させると結果が9^* になるのですが、これで良いのですか?

先ず、

18 = 2 x 3 x 3

144 = 2 x 2 x 2 x 2 x 3 x 33

となる筈です。

ここで公開したプログラムを使って計算してみると、

18 = 2 x 9

144 = 2 x 2 x 2 x 2 x 9

となってしまいます。

これは、プログラムに問題がありますね。

今まで気づきませんでした。

ご指摘、ありがとうございます。

プログラムを、どこか修正しないとダメなようです。

> ちなみに知識には飢えてないけど電卓の使い道に飢えてる高校生です。

どこが、違っているのか、時間をみて調べてみようと思います．．．．．が、最近なかなか時間が取れないので、いつになるのか．．．．．

ヘルプ頂けるとうれしいです。

2014-06-23(22:30) :
やす (Krtyski) URL :
編集

18や144を素因数分解させると結果が9^* になるのですが、これで良いのですか?

ちなみに知識には飢えてないけど電卓の使い道に飢えてる高校生です。

2014-06-23(20:53) :
すけっぴぃ URL :
編集

Gotoの効用

Kenさん

新ロジックのプログラム投稿、ありがとうございます。

次の３連休の際に、じっくりと拝見致します。

新しい記事をアップしていますが、休みの日に書いておいた原稿を、ちょっと見直して投稿すると言うスタイルです。

ところで、書きためておいた記事の中から、いくつかのコマンドの処理速度についてのものをアップしました。以前Kenさんのコメントで、For 文が速い、If文は遅いと言う内容があったので、気になって調べたものです。

Goto ループや、For ループが速いと言うKenさんのコメントを検証できました( ^o^)ノ

2013-12-12(20:08) :
やす URL :
編集

No title

高速化したプログラムのソースの一部を以下に記します。

変数はやすさんを踏襲します。
今から記述する部分については初期条件を
[1]C=0, D=3
[2]「素因数2について調べた後であること」
とします。よって[2]は「X={n|nは任意の奇数}かつY=X÷2」と同値です。

---
While Y≧1

For D→D To sqrtX Step 2
X÷D→Y
Frac(Y)=0 ⇒ Goto 2
Next

X→D
Lbl 2

Do
Y→X:IszC
X÷D→Y
LpWhile Frac(Y)=0

Do⊿
"TO THE":C⊿
0→C

WhileEnd
---
以上です。

「For-To-Step」を「Do-LpWhileとIsz」に置き換えて同じ事をさせたものも作りましたが、こちらの方が速かったので採用しています。

ところがさらに速いものを発見してしまいました・・・
時間の関係でまだきちんと組んでいないのですが、アイディアとしては
「階差を常に2ではなく、2,4,･･･とし、3の倍数での除算を避ける」という手法です。
（きりがないのでもう考えるのをやめようかと思っていた矢先で困っちゃいます）
いつかやってみようと思います。

ちなみに33333331を左から一桁ずつ削ってつくった素数ですが、こういう素数を「素な素数」と呼ぶことがあります。（本来はは右から削ったときのことをいいます）

2013-12-09(21:47) :
Ken URL :
編集

Re^2: 想定読者

言葉は難しいですね。

当ブログは、話題が結構限定されている上に、今のところ実際の話題はさらに限定されています。つまり当ブログに２回以上来て貰える人は、それなりに自動的に選別されてしまっているのだと思います。

１０月末に当ブログを立ち上げた際、最初から内容を限定するようにしたのも、読者の想定が楽になるようにしたいとの気持ちも有りました。

以前、アメブロで雑多な記事の中で電卓ネタも記事にしていたのですが、理科系でない読者が圧倒的だったので、手応えが無く、そのため読者に合わせた書き方をするようになっている自分に気がつきました。

そこで、当ブログでは最初から玄関を狭くしてみたわけです。あまりに狭すぎて、のたれ死ぬ心配が当初からありましたが、意外に話題に困らないものです。

一方で、akatukiさんのブログは間口が広いので、様々なルートで様々な属性の方が来られるのは、しかたありません。このような文脈で、４の1.5乗の話はとてもよく分かります。読者の知識レベルや経験の多様性を幅広く考えないと難しでしょう。

知識や人間性の幅を広くするには、棺桶に入るまで勉強ですよね(・ω・)

2013-12-08(05:20) :
やす URL :
編集

Re:想定読者

親分、夜分恐れ入ります。

というのは冗談ですが、「想定読者」については、これは当方の「舌足らず」でありました。
当方の「(4の)1.5乗」検索で来る読者は、確かに中高生に限った事ではない、というか「実際にはどんな読者なのか判らない」のです。しかし、そういう知識欲旺盛な人が来ていた。ネタが、それこそ中高生くらいの知識なので、こうした表現になったのでした。

> 内容が狭くて特定の話題なので、読者の年齢はあまり意識していません。特にプログミング関係の話題ですと、年齢はあまり意味を持ちません。なので、高校生だろうとおじいさんだろうと、私にとっては等しく大切な一人なんですよ。そこに区別を付ける気持ちは全くありません。

ウーン。主張、恐れ入ります。これは申し訳ない。「生涯勉強」を唱えていながら、当方の不徳の致す所であります。

2013-12-08(02:40) :
akatuki URL :
編集

ご心配なく

KENさん

多分そうだろうと、ちゃんと脳内変換して理解していましたので、大丈夫です。

のんびりと、どうぞ( ^o^)ノ

2013-12-07(22:56) :
やす URL :
編集

No title

すみません
先ほど計測時間を誤記してしまいました。
2分○○秒を○○sと書いてしまいました、恥ずかしい。

120足して修正するのでご確認ください。
なお、時計はG-SHOCKの腕時計です。

2013-12-07(22:14) :
Ken URL :
編集

テスト結果

KENさん

日常生活にご負担のないようにしてくださいね。

テスト結果です。

1) 41,028,683 (369,258,147の最大素因数)：300s
2) 82,428,107 (741,852,963の最大素因数)：426s
3) 83,128,807 (748,159,263の最大素因数)：428s

※ 私の書き方が悪かったのですが、1～9を１つづつ使った数の例では、上記のように最大素因数を対象にしたものです。

KENさんがさらに高速化したコードでテストした３つの素数のうち２つは上記に含まれますが、それ以外についてもテストしてみました。

4) 82,428,127：427s

2と３以上の奇数で平方根を超えるまでの素数検索回数は、上記４例では以下のようになります。

[数Ｎの検索回数] = Int(√N ÷ 2 - 0.5) +1

1) 41,028,683：3203回（300s）→ 93.7ms/回
2) 82,428,107：4539回（426s）→ 93.9ms/回
3) 83,128,807：4559回（428s）→ 93.9ms/回
4) 82,428,127：4539回（427s）→ 94.1ms/回

ここで、併せて検索１回あたりの所要時間の概算も追加しました。

検索１回あたり 94ms 程度かかっているようですね。

なお、計時にはフリーソフトの「SGウォッチ：http://www.vector.co.jp/magazine/softnews/051130/n0511303.html」を使いました。計時は１秒の単位までは正確ですので、msオーダーの概算です。

逆転現象に割り算が関わっている可能性とのことですが、fx-5800Pは割り算の処理速度が相対的にかなり遅いことが関係しているのかも知れません。

2013-12-07(22:07) :
やす URL :
編集

No title

こんばんは、Kenです。

おそらく単純（比例的）に、いずれも記事のプログラムの3分の1ほど（もう少し細かくいえば20分の7ほど笑）の時間で終わるはずです。やってみます。

1) 369258147 (105s)※9桁の数字は誤記らしいので修正しています
2) 741852963 (150s)
3) 748159263 (149s)
と、なりました。
（時間はやすさんの3分の1でしょうか？）

どれも1から9を一度ずつ用いているので、各桁の和が45であり、9の倍数になることは明らかですね。ところが9で除したものが素数になるというのはやはりその数の平方根まで調べないといけません。

素因数分解のアルゴリズムは（ちょっと検索しましたが）楕円曲線だとか群など、関数電卓で扱えるようなものではなさそうです。（もちろん、僕にだって扱えるものではありません）ここ数十年の暗号に使われているので、簡単に出来てしまったら困りますね。

現在のアルゴリズムの核心部分の「２と、３以上の奇数を平方根を超えるまで調べる」は、これ以上の工夫は、ないように思います。
ですので、あとは関数電卓の各コマンドの使い方で時間短縮を図った訳であります。

プログラムの詳細は追って書き込ませていただきます。
とりあえず、さきほどの結果と考察まで。

－－－
本日改めて計りなおしたので秒数を若干修正しました。
Gotoを多少削ったりしてプログラムを綺麗にしたところ数秒速くなったためです。
興味深いのは、2)と3)で数字の大小と時間が逆転していることです。
そこで2)と3)の因数を含む次の３つの素数で実験
41028683(104.2s)←ついでに追加
82428107(149.7s)←時間を修正
82428127(150.7s)
83128807(149.1s)
と、見事に大小が合わない結果が出ました。
割り算の処理に相性があるのかな、なんて考えています。
（12/7追記・一部修正）

2013-12-06(22:20) :
Ken URL :
編集

ありがとうございます >> KENさん

KENさん

処理速度向について、さらにコメントを頂きました。ありがとうございます。

突っ込みどころが合理的で、良いですね。Goto で処理速度を向上させるのは、確かに有効です。

私はパソコンでのプログラミングの経験が、電卓よりも遙かにあるので、Goto をあまり使いたくない癖が付いてしまっているので、今回のご提案は、最初から試そうとも思いませんでした。「頭が硬くなっている」とも言えそうです(´д｀)　　

こういう時「自分の流儀に合わない」などと言い訳をするんです．．．(-_-)

処理速度に限界のある電卓でのプログラミングですから、電卓に併せたプログラムにするのが良いと思いますが、ついつい．．．

ところで、せっかくのコメントが非公開なのは、とてももったいないので、できれば公開して頂けないでしょうか？

KENさんのリアルの部分の内容の取り扱いが、私には判断できないので私が勝手に引用するのをためらわれます。そして、公開コメントを頂ける場合は、是非プログラムソース全体も掲載頂けませんか？

3の並びの素数を見つけられたのですね。面白いですね。ほぼ１０倍づつ違うので、処理速度も１０倍づつになっているかどうか？　などの検討に使えそうですね。

私が、電卓で遊んでいて、以下のような８桁の素数を見つけました。これらを素因数分解した時の処理速度については、如何でしょうか？

1) 368258147 = 3 x 3 x 41028683

2) 741852963 = 3 x 3 x 82428107

3) 748159263 = 3 x 3 x 83128807

33333331 よりも大きい素数達です。平方根で打ち止めにするアルゴリズムのおかげで、非常に高速化しましたが、それでも結構時間がかかります。

今回、さらにご提案頂いたプログラムの改良での硬化は、如何でしょうか？

頂いた内容は、どこへ出しても恥ずかしくない内容だと思いますので、ぜひ公開をご検討ください。

2013-12-06(22:13) :
やす URL :
編集

管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

2013-12-06(21:10) :
:
編集

想定読者

akatuki様

コメントを頂き、ありがとうございます。

ブログの記事を書く際に、最も悩むのが読者の想定なのです。

ブログ全体に一定のラインを設けることができていません。このブログは自分が書きたいことを書くので、記事ごとに想定読者が異なってしまうのは、ある意味仕方ないとも思っております。

内容が狭くて特定の話題なので、読者の年齢はあまり意識していません。特にプログミング関係の話題ですと、年齢はあまり意味を持ちません。なので、高校生だろうとおじいさんだろうと、私にとっては等しく大切な一人なんですよ。そこに区別を付ける気持ちは全くありません。

素因数分解で、平方根を使って余計な処理を省くと言うアイディアを教えて貰った瞬間、私の中ではそれはとても自明なこととして理解しました。素因数を見つける際、小さい方から順に探すのも、大きい方から順に探すのも同じことです。そして、いずれにせよ最も先にある、つまり最も手数がかかるのが、平方根付近の数であるわけですし、それ以上は探しても無駄と言うことは、ネタを教えて貰った瞬間に分かりました。

平方根以上或いは以下を探しても無駄、と言う部分を分かりやすく解説頂きました。ありがとうございます。

これなどは、読者の想定をどこに置くか？　に密接に関係します。自分が分かってしまうと説明を省いてしまう傾向が私にはあるようですが、まぁそこは私の知識の幅がもっとあれば、改善は出来るかも知れません。

逆に、どうして分かったしまうのかを、うまく説明できなのが、問題と言えば問題です。

要所要所で、お気が向けば、また突っ込み、サポートをよろしくお願い致します。

> 当方のblogも、「(4の)1.5乗」という検索で来ている人がいるのですが、こういう読者を大切に、という事です、ハイ。

う～ん、おっしゃることは、とてもよく分かりますが、なかなか難しいかも知れません。

例えば、文字列処理を使えない言語で、数の桁数を知るにはどうするか？　なんて問題があるとします。私が真っ先に思いつくのは高校数学レベルの知識が必要になります。と言うか、他に方法を思いつかないんですね。

四捨五入をプログラミングするとどうなるか？　これも面白い問題だと思います。小学校レベルの算数でＯＫです。

このように、話題ごとに想定読者は変わってくると思うんですね。

2013-12-06(09:03) :
～やす～ URL :
編集

No title

呼ばれもしないのに、お邪魔します。

> ある数Xの素因数をするときにはsqrtXまで調べれば十分であることを使いました。（例えば51を素因数分解するのに、7まで調べたら9以上は調べる必要がない）

以前、この話を聞いた時に「なーんでかな ?」と思ったのですが、こういう理屈の様です。

ある数Xが整数の掛け算で表現できるならば、それは素数ではないわけですネ。

X = a*b

そこで、これを調べるために、aを1, 2, 3, ... と増やして行きます。一方、bの方は X/1, X/2, X/3, ... となるわけですが、ある時点まではa<bだとしても、2数の掛け算ですから、a=sqrt(X)以降ではa>bとなります。ここから先では、aとbを入れ替えただけの計算ですから、既に調べていた、ちう具合ですね。

こう書けば、高校生はもとより、小中学生でもわかる、のかな ? 何で、そんな事をいうのか、と言いますと、「高校生が見てコメントを書いてきた」という辺りなのです。
結構、知識欲に飢えた(?)中高生が(プロ電片手に ; それは難しいのか ?)見ていたりするんかな、などと思いましてネ。
当方のblogも、「(4の)1.5乗」という検索で来ている人がいるのですが、こういう読者を大切に、という事です、ハイ。

2013-12-05(00:12) :
akatuki URL :
編集

このページのトップへ

« 前の記事ホーム次の記事 »

このページのトップへ