Loading ...
Sorry, an error occurred while loading the content.
 

A very slow algorithm from my theorem

Expand Messages
  • Robin Garcia
    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]
    • Jud McCranie
      ... 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.
      • Robin Garcia
        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]
        • Jud McCranie
          ... 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.
          • cino hilliard
            ... 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
              >From: Robin Garcia <sopadeajo2001@...>
              >To: primoss <primenumbers@yahoogroups.com>
              >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 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
              your ubasic code.

              [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
            • hillcino368
              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?
                Plus I made a couple of corrections and removed the comments.
                I also removed the output which was done with the for x=256 a=x/128
                giving the bad prime 143.

                --- In primenumbers@yahoogroups.com, "cino hilliard"
                <hillcino368@h...> wrote:
                > >From: Robin Garcia <sopadeajo2001@y...>
                > >To: primoss <primenumbers@yahoogroups.com>
                > >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
                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:

                  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.