## A very slow algorithm from my theorem

Expand Messages
• Would anybody try to speed up the algorith implemented in a simple Ubasic program? 5 n=10^3:clr time 10 for x=18 to n step 2 20 a=x 4:b=x 2:z=0 30 for i=1 to a
Message 1 of 7 , Nov 26, 2004
Would anybody try to speed up the algorith implemented in a simple Ubasic program?

5 n=10^3:clr time
10 for x=18 to n step 2
20 a=x\4:b=x\2:z=0
30 for i=1 to a
40 for j=i to b-i
50 for k=i+1 to (x-i-j)\2
60 if i^2+j^2=k^2+(x-i-j-k)^2 z=z+1
65 if z>0 cancel for,for,for:goto 85
70 next k:next j:next i
80 if z=0 c=c+1:print x\2;"es primo"
85 next x
86 print time;prm(c+4)
90 end

---------------------------------

[Non-text portions of this message have been removed]
• ... you can calculate i^2+j^2 outside the loop on k, which will help a little. But the nested loops are going to make it slow. Using a compiled language will
Message 2 of 7 , Nov 26, 2004
At 01:03 PM 11/26/2004, Robin Garcia wrote:
>Would anybody try to speed up the algorith implemented in a simple Ubasic
>program?
>
>
>5 n=10^3:clr time
>10 for x=18 to n step 2
>20 a=x\4:b=x\2:z=0
>30 for i=1 to a
>40 for j=i to b-i
>50 for k=i+1 to (x-i-j)\2
>60 if i^2+j^2=k^2+(x-i-j-k)^2 z=z+1
>65 if z>0 cancel for,for,for:goto 85
>70 next k:next j:next i
>80 if z=0 c=c+1:print x\2;"es primo"
>85 next x
>86 print time;prm(c+4)
>90 end

you can calculate i^2+j^2 outside the loop on k, which will help a
little. But the nested loops are going to make it slow. Using a compiled
language will make it faster. I rewrite it in Pascal, and it still takes
4.0 seconds on a 2.4 GHz P4.
• Alan Eliasen wrote: What does the backslash operator do in Ubasic? ... -- Alan Eliasen | You cannot reason a person out of a
Message 3 of 7 , Nov 28, 2004
Alan Eliasen <eliasen@...> wrote:

What does the backslash operator do in Ubasic?

Robin Garcia wrote:
> Would anybody try to speed up the algorith implemented in a simple Ubasic program?
>
>
> 5 n=10^3:clr time
> 10 for x=18 to n step 2
> 20 a=x\4:b=x\2:z=0
> 30 for i=1 to a
> 40 for j=i to b-i
> 50 for k=i+1 to (x-i-j)\2
> 60 if i^2+j^2=k^2+(x-i-j-k)^2 z=z+1
> 65 if z>0 cancel for,for,for:goto 85
> 70 next k:next j:next i
> 80 if z=0 c=c+1:print x\2;"es primo"
> 85 next x
> 86 print time;prm(c+4)
> 90 end

--
Alan Eliasen | "You cannot reason a person out of a
eliasen@... | position he did not reason himself
http://futureboy.homeip.net/ | into in the first place."
| --Jonathan Swift

I do not know exactly why,but I bet Mars has 2 tiny satellites.

--------Jonathan Swift

---------------------------------

[Non-text portions of this message have been removed]
• ... It is integer division. x y = floor(x/y), or divide and throw away the remainder.
Message 4 of 7 , Nov 28, 2004
At 12:10 PM 11/28/2004, Robin Garcia wrote:

>Alan Eliasen <eliasen@...> wrote:
>
>What does the backslash operator do in Ubasic?

It is integer division. x\y = floor(x/y), or divide and throw away the
remainder.
• ... Hi Robin, Interesting theorem. I think it is related to the identity:- (a^2 + b^2) + (c^2+d^2) = (ab-cd)^2 + (ac-bd)^2 Nevertheless, Mike Oakes has
Message 5 of 7 , Nov 28, 2004
>Subject: Re: [PrimeNumbers] A very slow algorithm from my theorem
>Date: Sun, 28 Nov 2004 18:10:20 +0100 (CET)

>Robin Garcia wrote:
> > Would anybody try to speed up the algorith implemented in a simple
>Ubasic program?

> > 5 n=10^3:clr time
> > 10 for x=18 to n step 2
> > 20 a=x\4:b=x\2:z=0
> > 30 for i=1 to a
> > 40 for j=i to b-i
> > 50 for k=i+1 to (x-i-j)\2
> > 60 if i^2+j^2=k^2+(x-i-j-k)^2 z=z+1
> > 65 if z>0 cancel for,for,for:goto 85
> > 70 next k:next j:next i
> > 80 if z=0 c=c+1:print x\2;"es primo"
> > 85 next x
> > 86 print time;prm(c+4)
> > 90 end

Hi Robin,
Interesting theorem. I think it is related to the identity:-
(a^2 + b^2) + (c^2+d^2) = (ab-cd)^2 + (ac-bd)^2
Nevertheless, Mike Oakes has formalized it with a proof and I wonder if the
theorem can be
generalized for say kp = a+b+c+d for k=2,4,..and do some proving in that
area. Ny routine below
sugggests some generalizations can be made due to the great time
substutitions shown. if you try x start 256, a=x/128 143 = 11*13 pops up.
All others are correct. I
can't get rid of it by juggling x and a in the neighborhood of 256/128.
Question is why that number
fails at 256/128?

Below is a BCX rendition with some suggestions to speed things up a bit. I
have the c code if
someone wants but you should be able to port this to any language or modify

[program start]
'This is a bcx basic version of the Garcia primes routine. By making
'changes we go from x=18,a=x/4 to x=64,a=x/32 and we get for n=300
'32.2 sec to 0.156 sec. The ^ operator is expensive especially
'when it is in the 3rd nest of the loop. My guess is we can play with
'the x=? and a=x/? to get faster and'faster results for large n.
'I modified the output slightly to 'show the prime index to help in the
'trials selected.
'Cino L. Hilliard 11/28/2004

\$nowin
dim t1!,t2!,c
dim n,x,a,b,i,j,k,z,xij,ij2;
input "number ",n
t1!=timer
' c=4 'org
c=17 'change the prime count depending the
start
for x=128 to n+n step 2 'of x and a there may be on limit what you
a=x/64 'can do here by increasing the start of
b=x/2 'x and changing a = x/? by trial and
error.
z=0 'This suggests the theorem canbe
generalized
for i=1 to a 'with larger starting bounds.
for j=i to b-i
ij2 = i*i+j*j 'basic stuff here to get calculations
out
xij=x-i-j; 'of the 3rd nest and avoid ^
operator
for k=i+1 to xij/2 'and take out of the 3rd nest
' for k=i+1 to (x-i-j)/2
if ij2=k*k+(xij-k)*(xij-k) then 'avoid ^ operator
' if i^2+j^2=k*k+(x-i-j-k)^2 then
z=z+1
end if
if z>0 then
goto L85
end if
next k
next j
next i
if z=0 then
c=c+1
print c;x/2
end if
L85:
next x
t2!=timer
print t2!-t1!
getchar()
[program end]

2.53 ghz p4 output for n=1000, x starts at 256, a starts at x/128

number 1000
31 131 'notice we start at 31'st prime
32 137
33 139
34 143
35 149
36 151
37 157
38 163
39 167
40 173
...
...

155 907
156 911
157 919
158 929
159 937
160 941
161 947
162 953
163 967
164 971
165 977
166 983
167 991
168 997
4.59375

Cheers and K-Mart,
CLH
• Hi, Sorry for the garbled previous send I hope this is more readable. I did it in yahoo which does gives you the ability to preview. Mr Gates are you tuned in?
Message 6 of 7 , Nov 28, 2004
Hi,
Sorry for the garbled previous send
I hope this is more readable. I did it in yahoo which does
gives you the ability to preview. Mr Gates are you tuned in?
I also removed the output which was done with the for x=256 a=x/128

<hillcino368@h...> wrote:
> >Subject: Re: [PrimeNumbers] A very slow algorithm from my theorem
> >Date: Sun, 28 Nov 2004 18:10:20 +0100 (CET)
>
> Robin Garcia wrote:
> Would anybody try to speed up the algorith implemented in a
> simple Ubasic program?
>
> 5 n=10^3:clr time
> 10 for x=18 to n step 2
> 20 a=x\4:b=x\2:z=0
> 30 for i=1 to a
> 40 for j=i to b-i
> 50 for k=i+1 to (x-i-j)\2
> 60 if i^2+j^2=k^2+(x-i-j-k)^2 z=z+1
> 65 if z>0 cancel for,for,for:goto 85
> 70 next k:next j:next i
> 80 if z=0 c=c+1:print x\2;"es primo"
> 85 next x
> 86 print time;prm(c+4)
> 90 end
>
Hi Robin,
Interesting theorem. I think it is related to the identity:-
(a^2 + b^2) + (c^2+d^2) = (ab-cd)^2 + (ac+bd)^2
Nevertheless, Mike Oakes has formalized it with a proof and I
wonder if the theorem can be generalized for say kp = a+b+c+d for
k=2,4,..and do some proving in that area. Ny routine below sugggests
some generalizations can be made due to the great time improvements
made by substutitions shown. if you try x start 256, a=x/128 143 =
11*13 pops up. > All others are correct. I can't get rid of it by
juggling x and a in the neighborhood of 256/128. Question is why
that number fails at 256/128?

Below is a BCX rendition.You should be able to port this to any
language or modify your ubasic code. significant speed up is attained
by avoiding the exponentiation ^ operator and computing some variables
outside of the inner loop.

\$nowin
dim t1!,t2!,c
dim n,x,a,b,i,j,k,z,xij,ij2;
input "number ",n
t1!=timer
c=18
for x=128 to n+n step 2
a=x/64
b=x/2
z=0
for i=1 to a
for j=i to b-i
ij2 = i*i+j*j
xij=x-i-j
for k=i+1 to xij/2
if ij2=k*k+(xij-k)*(xij-k) then
z=z+1
end if
if z>0 then
goto L85
end if
next k
next j
next i
if z=0 then
c=c+1
print c;x/2
end if
L85:
next x
t2!=timer
print t2!-t1!
getchar()

CLH
• Robin Garcia wrote: Robin Garcia wrote: Would anybody try to speed up the algorith implemented in a simple
Message 7 of 7 , Dec 2, 2004

Robin Garcia <sopadeajo2001@...> wrote: Would anybody try to speed up the algorith implemented in a simple Ubasic program?

5 n=10^3:clr time
10 for x=18 to n step 2
20 a=x\4:b=x\2:z=0
30 for i=1 to a
40 for j=i to b-i
50 for k=i+1 to (x-i-j)\2
60 if i^2+j^2=k^2+(x-i-j-k)^2 z=z+1
65 if z>0 cancel for,for,for:goto 85
70 next k:next j:next i
80 if z=0 c=c+1:print x\2;"es primo"
85 next x
86 print time;prm(c+4)
90 end

---------------------------------

Sometimes we can speed-up things.

1 word 2:n=168:b=ceil(3*n*log(n)):dim A(b):for j=1 to b:A(j)=j^2:next j
2 y=0:clr time
5 for l=1 to b
10 h=2*l+1:z=0:if h@3=0 and h<>3 or h@5=0 and h<>5 goto 90
20 s=3*h-1:t=s+2:e=isqrt(3*h):f=(h+3-2*e)\2
30 for i=h to h+f step 2:c=A(i)+A(s-i)
50 for k=i+6 to i+e step 2
60 if c=A(k)+A(t-k) :z=z+1
65 if z>0 cancel for,for:goto 90 'los compuestos quedan excluidos
70 next k:next i
80 if z=0 y=y+1:print h;"es primo";prm(y+1)
85 if y+1>=n cancel for:goto 95
90 next l
95 print y+1;"enesimo primo=";prm(y+1);time
100 end

I will invite to a bottle of Rioja wine to the first person who will improve that.

And 2 bottles to Mike if he finds out what theorems I used.

---------------------------------

---------------------------------

[Non-text portions of this message have been removed]
Your message has been successfully submitted and would be delivered to recipients shortly.