HSPTV!掲示板

以下のソースを実行すると、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

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

　おそらく、次の２つの問題点のせいだと思われます。
①，疑似無限ループに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が入っていません。確かに有限個のループなのですが、約１６兆も
繰り返すわけですからwaitを入れないとCPUパワーを食ってしまいます。
　肝心の解決法ですが、さすがに毎ループ毎にwaitを取ると時間を食い過ぎますので

k+ : if k=128 : k=0 : wait 1

のようなスクリプトをループ中に入れてやれば解決すると思われます。 ★② 　②ですが、sさんはある数ｎが素数であるかを調べる為に、√ｎ以下の自然数全ての余りを 求めています。しかし、これは少し無駄が多いです。 　ある数ｎが素数である条件は、

『√ｎ以下の素数全てで割り切れない』

事です。
　例えば、ｎが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]を一定にしたいようですが、これは無理
だと思われます。何故なら、一つの自然数が素数であるか否かを調べる為に要する計算量は
自然数の大きさに応じて変動するからです。以下にｎ近傍の自然数が素数であるか否かを調べる
為に必要な計算回数を書いておきます。
>>ｎ(自然数) １百 １万 １億 １兆
>>ｃ(計算回数) 4 26 1229 78498
単純に言っても、１万～１万１千までの計算量と、１億～１億１千までの計算量では、どちらも
同じオーダー(１千)でありながら６倍近い差が生まれてしまいます。これは直接素数判別時間の
差になります。

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

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

単に素数判定が遅いだけなんで速さを上げればいいわけです。
素数判定が出来る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

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

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

repeat 10,2147483647
	mes cnt
loop

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

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

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

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

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