User talk:Retroburrowers

From Rosetta Code

Our 1st response is posted here: U r critiquing alphaversions abandoned infavor of a beta which may find the answer -as well as false positives due to lack of precision. Please test the beta on fuse, and post your versions after our beta, which we can't run not having a Next w/1.5 MB ram. 

 --Frisian wrote:
 A little info why your programs did not give results.

<lang zxbasic> 5 FOR r=34 TO 5 STEP -1 10 FOR m=r TO 249 STEP 30 20 FOR w=4 TO (m-1):FOR x=3 TO (w-1):FOR y=2 TO (x-1):FOR z=1 TO (y-1) 30 LET sum=INT(w^4/m*w + x^4/m*x + y^4/m*y + z^4/m*z + 0.5) 40 LET s1=m^4 45 IF sum>s1 THEN GO TO 65 50 IF s1=sum THEN PRINT w;"^5+";x;"^5+";y;"^5+";z;"^5=";m;"^5": STOP 60 NEXT z: NEXT y: NEXT x: NEXT w 65 NEXT m: NEXT r</lang>

<lang zxbasic> 2 DIM p(249) : DIM q(249) 

4 FOR i=1 TO 249 
5  LET p(i)=i*i : LET q(i)=p(i)*i
6 NEXT i
8 FOR r=34 TO 5 STEP -1

10 FOR m=r TO 249 STEP 30 20 FOR w=4 TO (m-1): FOR x=3 TO (w-1): FOR y=2 TO (x-1): FOR z=1 TO (y-1) 30 LET sum=INT(q(w)/q(m)*p(w) + q(x)/q(m)*p(x) + q(y)/q(m)*p(y) + q(z)/q(m)*p(z) +0.5) 40 LET s1=p(m) 45 IF sum>s1 THEN GO TO 65 50 IF s1=sum THEN PRINT w;"^5+";x;"^5+";y;"^5+";z;"^5=";m;"^5": STOP 60 NEXT z: NEXT y: NEXT x: NEXT w 65 NEXT m: NEXT r<lang>

<lang zxbasic> 2 DIM p(249) : DIM q(249) 

4 FOR i=1 TO 249 
5  LET q(i)=LN i
6 NEXT i
8 FOR r=34 TO 5 STEP -1

10 FOR m=r TO 249 STEP 30 20 FOR w=4 TO (m-1): FOR x=3 TO (w-1): FOR y=2 TO (x-1): FOR z=1 TO (y-1) 30 LET sum=EXP(q(w)-q(m)) + EXP(q(x)-q(m)) + EXP(q(y)-q(m)) + EXP(q(z)-q(m)) 35 IF sum>1 THEN GO TO 65 50 IF sum=1 THEN PRINT w;"^5+";x;"^5+";y;"^5+";z;"^5=";m;"^5": STOP 60 NEXT z: NEXT y: NEXT x: NEXT w 65 NEXT m: NEXT r</lang>

All these versions have 1 fatal flaw. When sum it greater then a certain value they jump to <lang zxbasic>NEXT m</lang> instead they should jump to <lang zxbasic>NEXT y</lang>

Let's say that m = 10 and 

 w     x     y     z
8^5 + 7^5 + 6^5 + 5^5 = 32768 + 16807 + 7776 + 3125 = 60476 
9^5 + 3^5 + 2^5 + 1^5 = 59049 +   243 +   32 +    1 = 59325

To demonstrate this let's take version and alter it a little bit in order to give a fast result.
We set m to 144, w to 133 ,x to 110, and y = 70 to speed things up.
<lang zxbasic> 2 DIM p(249) : DIM q(249)
4 FOR i=1 TO 249 
5 LET p(i)=i*i : LET q(i)=p(i)*i
6 NEXT i

10 FOR m=144 TO 144 STEP 30 : let s1=p(m) 20 FOR w=133 TO (m-1): FOR x=110 TO (w-1): FOR y=70 TO (x-1): FOR z=1 TO (y-1) 30 LET sum=INT(q(w)/q(m)*p(w) + q(x)/q(m)*p(x) + q(y)/q(m)*p(y) + q(z)/q(m)*p(z) +0.5) 45 IF sum>s1 THEN GO TO 65 50 IF s1=sum THEN PRINT w;"^5+";x;"^5+";y;"^5+";z;"^5=";m;"^5": STOP 60 NEXT z 61 NEXT y: NEXT x: NEXT w 65 NEXT m: </lang>

Run it and simple stops with out a result, since m does not increase we can check the value of y and z, y = 74, z = 73. In line 45 change <lang zxbasic>GO TO 65</lang> to <lang zxbasic>GO TO 61</lang>. Rerun it and after a while it will produce the correct answer 133^5+110^5+84^5+27^5=144^5.

Please remember that the ZX Spectrum is 38 years old and it was not designed for this kind of tasks, it was a cheap and simple computer. --Frisian (talk) 15:15, 30 April 2020 (UTC)

<lang zxbasic> 5 DIM p(249): DIM q(249): DIM r(249,249) 10 FOR i=1 TO 249: LET q(i)=5*LN i: LET p(i)=q(i)/2: NEXT i 15 FOR j=1 TO 249: FOR k=1 TO 249: LET r(j,k)=EXP(q(j)-p(k)): NEXT k: NEXT j 20 FOR w=7 TO 245 STEP 7: FOR x=5 TO 245 STEP 5: FOR y=3 TO 246 STEP 3: FOR z=2 TO 248 STEP 2 25 FOR m=8 TO 249 30 LET sum=r(w,m)+ r(x,m) + r(y,m) + r(z,m) 35 LET lnsum=LN sum 50 IF lnsum=p(m) THEN PRINT w;"^5+";x;"^5+";y;"^5+";z;"^5=";m;"^5": STOP 55 IF lnsum>p(m) THEN NEXT m 60 NEXT z: NEXT y: NEXT x: NEXT w </lang>

This code will not run on ZX Spectrum nor on Fuse. In line 5 the last dim statement uses to much memory 249*249*5 = 310005 Bytes, this is even more then the total amount of memory for a ZX Spectrum 128. Therefore it´s not a ZX Spectrum program. Also it has the same flaw as the other version it will not find the solution.

Please check [ZX Spectrum page] --Frisian (talk) 17:44, 30 April 2020 (UTC) 

 Our 2nd reply:

actually 249^2*5 is within the OEM limit of a QL, & can be made smaller by shifting indices down to 0 TO 248 and changing the code accordingly. Yet this beta does not have the same flaw as the alpha, as the m loop runs within the 4 others. The error should be different: in taking logs, subtracting them, exponentiating differences and taking the log of their sums, and comparing that to a log in the p array. That ought to compound rounding errors, so we wouldn't be surprised if it didn't find the correct solution. Even so, we'd settle for it not finding false solutions. So we'll test it on Q-emuLator sometime next week, and also test trying to balance out the rounding errors on each side of the IF =sign: It seems that Sinclair BASICs calculate an extra digit in FP functions so as to know which way to round the least significant digit. Comparing the 2.5 powers is to attempt a "meet inthe middle" hack to a discrete log problem. Thus, taking INTs becomes superfluous - just like when comparing integers by taking INTs, which seems like shooting yourself in the foot: you may find the correct solution, but you also may round some FP Nos the wrong way and thereby find false solutions. 

The point is taken that a Spectrum Next is no ZX Spectrum, in which case one can revert back to no precalculated differences, and run that at full speed on Fuse.

With Respect to Sundaram Sieve...

In your recent contribution to the Sieve of Eratosthenes Task for QLSuperBasic/Sundaram Sieve: http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Sieve_of_Sundaram, with respect, your statement - "Thus, Sundaram's is what Eratosthenes' Sieve becomes upon applying all optimisations incorporated into the other entries for QL SuperBASIC." is incorrect. Sundaram uses **all odd numbers** as the basis for culling composite numbers whereas the SoE optimized to odds-only uses only **odd primes** for this purpose; this changes the computational complexity to O(n^(3/2)) from O(n log log n), a considerable difference. While one can use some recursion to cull by previously sieved primes, that result becomes a full SoE and can no longer be called the Sieve of Sundaram, as "all odd numbers" is it's exact characteristic. One can recompose your Sundaram code to make this more obvious.

Sorry, forgot to sign - GordonBGood (talk) 20:30, 22 May 2021 (UTC)

reply

Recomposing to get back to Sundaram's original sieve would be to reverse the "modest transformation" from it into the optimised SoE Therefore, the quoted statement is meant in the sense that transforming Sundaram's Sieve will produce the same effect as the original when reducing his 2D array down to 1D, as well as skipping odd non-primes via line 50. Thus, we increased the degree of the transformation from "slight" to "modest." Likewise in the last FOR loop where it becomes necessary to include zero as a member of the compressed elements in order to be equivalent to the SoE, since Sundaram's matrix excludes 0 - but only explicitly, since one can include it on the ground that "the empty set is a subset of any set of items" such that 0 is thereby an implicit way of generating 2 as the 1st prime by uncompressing via 0^I+1+I*2. So we're more inclined to change the reference in the statement as well as the title to an optimised sieve of Sundaram, rather than by removing line 50 & not generating 2.

RE "So we're more inclined to change the reference in the statement as well as the title to an optimised sieve of Sundaram, rather than by..." - but the title of the whole Task page is The Sieve of Eratosthenes not Sundaram so why clutter it up and make it confusing by bringing up the subject of other less efficient sieves? I would recommend just removing any and all sieves that are not SoE's. Regards GordonBGood (talk) 06:22, 24 May 2021 (UTC)

reply2

b/c most optimisations employed in other languages go beyond the given task's specification. Many of them are similar to the Sieve of Sundaram in their 2:1 compression. Others are similar to the modestly optimised version. Thus, the task should be reclarified to allow such 'extras'. In this specific case, it's more of an academic exercise to show how one optimised Sieve is a modest transformation away from another. Thusly optimised, they should be identical in terms of speed.

You seem to be under the impression that the Sieve of Sundaram (SoS) is an "optimisation"; It is not. The only optimization that it enjoys is that it is just slightly easier to implement that the SoE and that, like the odds-only SoE, it reduces the sieving memory requirement to half. You are correct that the SoE can be just a modest transformation away from the properly implemented SoS. Perhaps it will take an example to convince you; Following is a properly implemented version of the Python code from the Wikipedia article on SoS; I say improved because it removes the redundancies of over-looping past constraints that never do any culling operations, it properly manages zero based array indices, and the determination of `j` is based on what it actually does and is formulated so that no multiplications are required inside the culling loop:

<lang python>import math

def sieve_of_Sundaram(n): 

   """The sieve of Sundaram is a simple deterministic algorithm for finding all the prime numbers up to a specified integer."""
   if n < 3:
       if n < 2: return 0
       else: return 1    
   k = (n - 3) // 2 + 1; integers_list = [True] * k; ops = 0
   for i in range(0, (int(math.sqrt(n)) - 3) // 2 + 1):
  1. if integers_list[i]: # adding this condition turns it into a SoE!
           p = 2 * i + 3; s = (p * p - 3) // 2 # compute cull start
           for j in range(s, k, p): integers_list[j] = False; ops += 1
   print("Total operations:  ", ops, ";", sep=)
   count = 1
   for i in range(0, k):
       if integers_list[i]: count += 1
   print("Found ", count, " primes to ", n, ".", sep=)

""" 

   if n > 2:
       print(2, end=' ')
   for i in range(0, k):
       if integers_list[i]:
           print(2 * i + 3, end=' ')

"""

sieve_of_Sundaram(1000000)</lang>

Output:
Total operations:  1419797;
Found 78498 primes to 1000000.
Now, uncommenting the prime test condition as noted turns this into a SoE, but changes the output as to the total number of operations:
Output:
Total operations:  811068;
Found 78498 primes to 1000000.
This difference in the amount of operations as in the amount of work done gets even larger as the range goes up; if you want to play with it, the code is posted on an on-line IDE here. The reason for this difference is that the SoE has about O(n log log n) asymptotic complexity which increases quite slowly with range, where as the SoS has about O(n log n) complexity, which increases more quickly with range. This can be seen from the above implementation as i ranges up to (half of) the square root of the range, where the j variable ranges from a little above i to something approaching (half of) the range, so the product is O(n^(3/2)) but the span of the culling increases with increased base number so as to reduce the term to about log n, with the extra constant factor of about a quarter meaningless for showing complexity with increasing range (Big-O).
That is the reason that the SoS should not be on the SoE Task Page: it doesn't have the same asymptotic complexity, it isn't that much simpler, and it is confusing for those that can't tell the difference.
Regards, GordonBGood (talk) 06:16, 25 May 2021 (UTC)
I had another look at your "Sieve of Sundaram" code and it's not wrong other than for the title: as it does have the condition that the base value must have already been determined to be prime, it is not the SoS but rather a full implementation of the Odds-Only Sieve of Eratosthenes. Therefore, my recommendation is just that you change the title and comments. Regards GordonBGood (talk) 02:04, 26 May 2021 (UTC)

reply3

We were dissuaded from keeping line 50 by your subsequent argument, even w/o the example in Python, but still appreciate its inclusion. We accordingly changed the comments to stress that a minimally changed SoS is being emulated, and so allow keeping the title.

Retrieved from "https://rosettacode.org/wiki/User_talk:Retroburrowers?oldid=299764"