Calculating the sum of a *lot* of primes
Alex Tweedly
alex at tweedly.net
Sun Nov 15 16:47:52 EST 2015
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
More information about the Use-livecode
mailing list