Calculating the sum of a *lot* of primes

[Alex Tweedly]

Geoff,

thanks for such a fun little problem.

I know you have a complete solution - but I still wanted to investigate 
if it could be done any faster.

The main constraint to take advantage of is that, although the sum of 
the primes needs to be an arbitrarily large number and use 'bigmath', 
the individual primes must fit within a normal LC number.

Therefore, we can use a running sub-total, and only when that approaches 
the upper limit of a normal integer add that to the overall total (with 
bigMath).

So something like  (changed lines marked with "|")

    repeat with C = 1 to 999999999999
       read from file fPath for 1 line
       if it > fld 1 then exit repeat
|      add char 1 to -2 of it to subtotal
|      if subtotal > 999999999999 then   -- that's 12 of them :=-)
|         put bAdd2(T,subtotal) into T
|         put 0 into subtotal
|      end if
       if the seconds > S then
          put the seconds + 1 into S
          put T && it && C into fld 2
          unlock screen
          lock screen
       end if
    end repeat
|   put bAdd2(T,subtotal) into T
    put T && it && C - 1 into fld 2


I didn't have a list of primes on hand, so I used a synthetic little 
benchmark using random large numbers, and got a speed-up of between 50x 
and 100x. I suspect the benfit in the real case would be towards the 
lower end of that range, if my guess about magnitude of the primes is 
correct.


We could also replace 'bAdd' with 'bAddSmall' which takes one 
arbitrarily large number and one normal LC number and adds them; I would 
guess this would give at most 5-10% improvement, so I haven't bothered 
actually trying it :-)

-- Alex.

On 12/11/2015 06:26, Geoff Canyon wrote:
> I re-wrote the algorithm a bit to tweak for speed, then ran it successfully
> for primes up to 3 billion (a couple hours), and got the wrong answer
> because my big addition function was broken :-/
>
> So I broke the problem in two: first generate the list of primes, then do
> the addition.
>
> For the primes I generated the list up to 100,000, stored that, and then
> used a simpler (by one command) routine to generate the primes to 10
> billion in a few hours. Here's that:
>
> on mouseUp
>     put the long seconds into ST
>     repeat for each line i in line 2 to -1 of the primeList of this stack
>        put 2*i & comma after P[i^2]
>     end repeat
>     put 2 into pList
>     put fld "path" into fPath
>     open file fPath for write
>     put 0 into S
>     put fld 1 into endPoint
>     if endPoint mod 2 = 0 then subtract 1 from endPoint
>     repeat with i = 3 to endPoint step 2
>        if P[i] is empty then
>           put cr & i after pList
>        else
>           repeat for each item x in P[i]
>              put x & comma after P[i + x]
>           end repeat
>        end if
>        if the seconds > S then
>           put the seconds + 5 into S
>           put i into fld 2
>           write pList to file fPath
>           put empty into pList
>           unlock screen
>           lock screen
>        end if
>        delete variable P[i]
>     end repeat
>     put i into fld 2
>     write pList to file fPath
>     close file fPath
>     put the long seconds - ST
> end mouseUp
>
> That's ~5gb of primes...
>
> Then I re-wrote the addition function to use a simpler, slower method,
> tested it, and let it go. An hour or so later, and I had my answer
> (validated against the site with the challenge). If anyone sees the problem
> with bAdd, I'm all ears. I didn't look too closely, since I just wanted to
> get the code running to solve the problem. It works for all the test cases
> I tried, but it seems to fail on the boundary between 14 and 15 digit
> numbers.
>
>
> on mouseUp
>     put fld "path" into fPath
>     open file fPath for read
>     put 0 into T
>     put 0 into S
>     repeat with C = 1 to 999999999999
>        read from file fPath for 1 line
>        if it > fld 1 then exit repeat
>        put bAdd2(T,char 1 to -2 of it) into T
>        if the seconds > S then
>           put the seconds + 1 into S
>           put T && it && C into fld 2
>           unlock screen
>           lock screen
>        end if
>     end repeat
>     put T && it && C - 1 into fld 2
>     close file fPath
> end mouseUp
>
> function bAdd x,y
>     put 0 into c
>     repeat with i = 14 to max(length(x),length(y)) step 14
>        add char -i to 13 - i of x + char -i to 13 - i of y to c
>        put char -14 to -1 of c before r
>        delete char -14 to -1 of c
>     end repeat
>     return c & r
> end bAdd
>
> function bAdd2 x,y
>     put 0 into c
>     repeat with i = 1 to max(length(x),length(y))
>        put char -i of x + char -i of y + c into c
>        put char -1 of c before r
>        delete char -1 of c
>     end repeat
>     return c & r
> end bAdd2
> _______________________________________________
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode