HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2010
0330
s重い9解決


s

リンク

2010/3/30(Tue) 11:55:24|NO.31670

以下のソースを実行すると、CPUの使用率が9割を超えてしまいます。
実行速度を0〜52ms/4 orders程度にしたままで、動作を軽くすることはできませんか。

#include "d3m.hsp" #module #defcfunc IsPrimeAB int A,int B f=0 po=4 repeat B-A+1,A if IsPrimeC(cnt)=1:f=1:break if po=cnt:wait 1:po=po+4 loop return f #defcfunc IsPrimeC int A i=2:while i*i <= A if(A\i = 0):return 0 i++ wend return 1 #global mes "n^2と(n+1)^2の間に素数が存在するか調査する" mes "調査開始" C=4097072 D=C+4 dim Nam,3 *Enter Nam(0) = d3timer() C++ A=C*C:B=(C+1)*(C+1) if A > B:A = A xor B:B = A xor B:A = A xor B if IsPrimeAB(A,B)=1{ if C = D{ color 255,255,255 boxf 30,50 color 0,0,0 pos 30,50 mes "n="+C+" is OK" Nam(1) = d3timer() Nam(3)=Nam(1)-Nam(0) mes ""+Nam(3)+"ms/4 orders で実行中" wait 1 D=D+4} goto *Enter }else{ mes "n="+C+" is not OK" mes ""+A+"〜"+B+"の間に素数はない" goto *endn } *endn stop



この記事に返信する


maa

リンク

2010/3/30(Tue) 19:59:40|NO.31672

ざっと見たところ、連続して調べるにはIsPrimeCに無駄が多い気がします。
素数の一覧を作って行く感じにするのはどうですか?
修正したついでにwaitをそこに加えればCPUの使用率も下がると思います。



木村

リンク

2010/3/30(Tue) 20:22:02|NO.31674

 おそらく、次の2つの問題点のせいだと思われます。
 さ浸無限ループにwaitが入っていない
◆ち膿瑤竜瓩疂に無駄がある


 まず、,任垢

#defcfunc IsPrimeAB int A,int B f=0 po=4 repeat B-A+1,A if IsPrimeC(cnt)=1:f=1:break if po=cnt:wait 1:po=po+4 loop return f
 この部分のループにwaitが入っていません。確かに有限個のループなのですが、約16兆も
繰り返すわけですからwaitを入れないとCPUパワーを食ってしまいます。
 肝心の解決法ですが、さすがに毎ループ毎にwaitを取ると時間を食い過ぎますので
k+ : if k=128 : k=0 : wait 1

のようなスクリプトをループ中に入れてやれば解決すると思われます。 ★  △任垢、sさんはある数nが素数であるかを調べる為に、√n以下の自然数全ての余りを 求めています。しかし、これは少し無駄が多いです。  ある数nが素数である条件は、
『√n以下の素数全てで割り切れない』
事です。
 例えば、nが36で割り切れれば、確かに非素数である事が分かります。けれども、36で割り
切れる数なら、その因数である18でも、あるいは12でも割り切れるはずです。更に言えば9や
4でも、最終的には36の素因数である2や3のいずれかで割り切れた時点で、36が非素数であるか
否かが分かります。

 これを利用すれば、計算量が大幅に減ります。一例を挙げれば、100〜10000までの間に存在
する素数を調べる場合、sさんの計算では自然数一つ当たり10〜100回余りを求める必要があり
ます。しかし、予(アラカジ)め100以下の素数を調べておいて、素数の余りのみで素数であるか
否かを求める計算方法ならば、自然数一つ当たり4〜26回余りを求めてやるだけで済みます。
 両者の差は調べる数の桁が大きくなればなるほど拡大します。大数の素数チェックをする
なら、こちらの方が良いと思います。

 で、肝心のソースですが、木村は論理演算子関連の処理能力が皆無なのでsさんのソースに
適合したスクリプトは書けませんでした。が、一応全くの別物としては作れたので以下に貼り
ます。

notesel p : noteload "素数(1〜1000000).txt";ノートパット形式で素数が入っている n=1000000 : s=n : e=int(sqrt(n)+1)*int(sqrt(n)+1) : a="" repeat e-s c=cnt+s+1 : r=1 repeat notemax k+ : if k=256 : k=0 : wait 1 noteget n,cnt : n=int(n) if c\n=0 : r=0 : break if c<n*n : r=1 : break loop if r=1 : noteadd str(c) : notesel a : noteadd str(c) : notesel p loop notesel a : notesave "素数("+s+"〜"+e+").txt" : end

★最後に
 sさんは単位自然数当たりの素数判別時間[s/order]を一定にしたいようですが、これは無理
だと思われます。何故なら、一つの自然数が素数であるか否かを調べる為に要する計算量は
自然数の大きさに応じて変動するからです。以下にn近傍の自然数が素数であるか否かを調べる
為に必要な計算回数を書いておきます。
>>n(自然数) 1百 1万 1億 1兆
>>c(計算回数) 4 26 1229 78498
単純に言っても、1万〜1万1千までの計算量と、1億〜1億1千までの計算量では、どちらも
同じオーダー(1千)でありながら6倍近い差が生まれてしまいます。これは直接素数判別時間の
差になります。

 単位ループ数当たりの消費時間[s/loop]であれば、恒常的に一定に保つ事は可能でしょうが
単位自然数当たりの消費時間[s/order]を一定に保つ事は不可能なはずです。

 以上、長文でしたが、sさんの参考になれば幸いです。



エイジ

リンク

2010/3/30(Tue) 22:56:22|NO.31680

単に素数判定が遅いだけなんで速さを上げればいいわけです。
素数判定が出来るlongintというプラグインがあったのでそれを使うのが簡単でしょうか。
http://www.vector.co.jp/soft/win95/prog/se397330.html
もしくはプラグインなしで標準命令だけでつくってもそれなりに早くなるようです。


#module #deffunc eratosthenes dim list,46340 repeat 216,2 if list.cnt==0{ for i,cnt*2,46340,cnt list.i=1 next } loop pn=0 dim prime,65536 repeat 46338,2 if list.cnt==0:prime.pn=cnt:pn++ loop return #defcfunc isprimeC2 int a if a<2:return 0 f=1 repeat pn p=prime.cnt if p*p>a:break if a\p==0:f=0:break loop return f #global eratosthenes #include "d3m.hsp" #module #defcfunc IsPrimeAB int A,int B f=0 po=4 repeat B-A+1,A if IsPrimeC2(cnt)=1:f=1:break if po=cnt:wait 1:po=po+4 loop return f #defcfunc IsPrimeC int A i=2:while i*i <= A if(A\i = 0):return 0 i++ wend return 1 #global mes "n^2と(n+1)^2の間に素数が存在するか調査する" mes "調査開始" C=4097072 D=C+4 dim Nam,3 *Enter Nam(0) = d3timer() C++ A=C*C:B=(C+1)*(C+1) if A<0:mes "END":goto *endn if B<0:B=(1<<31)-1 if A > B:A = A xor B:B = A xor B:A = A xor B if IsPrimeAB(A,B)=1{ if C = D{ color 255,255,255 boxf 30,50 color 0,0,0 pos 30,50 mes "n="+C+" is OK" Nam(1) = d3timer() Nam(3)=Nam(1)-Nam(0) mes ""+Nam(3)+"ms/4 orders で実行中" wait 1 D=D+4} goto *Enter }else{ mes "n="+C+" is not OK" mes ""+A+"〜"+B+"の間に素数はない" goto *endn } *endn stop



s

リンク

2010/3/31(Wed) 06:46:37|NO.31688

今確認して初めてわかったんですけど、A,Bが負の値になってますね……
これ、正しく計算できないんですか?



hatter

リンク

2010/3/31(Wed) 08:50:21|NO.31689

これっていうのはsさんの書いたスクリプトの事でしょうか?
おそらくHSPの言語仕様の上の制約です。2147483647(32bitの最大)までしか数字は表せません。
以下のスクリプトを実行すれば分かると思います。
当然ながらそれを超えると、符号ビットを反転させるので負の値になります。
正負の表現は2の補数で行ってるようで、負の方向には1大きく数字が表せるようです。


repeat 10,2147483647 mes cnt loop



s

リンク

2010/3/31(Wed) 17:07:21|NO.31708

では、どのようにすれば正しく計算できるのですか?



エイジ

リンク

2010/3/31(Wed) 22:25:22|NO.31720

>今確認して初めてわかったんですけど、A,Bが負の値になってますね……
てっきりintの上限を分かってるのかと思ったのですが違ったか。
よく見たらC=4097072とかなってますね。
Cの限界値はC=46340です。

それでどうしたらいいかですが、前のレスで紹介したlongintをつかってみたらどうですか。
intよりもずっと大きい数値が使えるようです。



s

リンク

2010/4/1(Thu) 03:02:39|NO.31721

うまくできました。
ところで、longintはいくつまでの整数を扱えるのですか?



s

リンク

2010/4/1(Thu) 04:27:12|NO.31722

longintはいくらでも桁数を増やせるそうです。
ありがとうございました。



ONION software Copyright 1997-2021(c) All rights reserved.