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@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
