Thanks for pointing out optimizations -- I was only interested in getting
the answer so I wasn't even thinking about speed.
This revision gets the correct result in just under three minutes, while
the original took several hours so it's at least 60x faster. Your
optimization is the largest, by far I suspect.
In addition I: upped the limit for regular addition to 14 digits; read the
input file 10,000 lines at a time; used replace and sum() to get the value
to add (except for the last batch, which requires going line-by-line to
avoid over-adding); and improved the bAdd function to be more efficient.
I'm sure this could be optimized/cleaned up further, but I'm happy to leave
it at 3 minutes.
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 ("00000000000000" & c) before r
delete char -14 to -1 of c
end repeat
put c before r
repeat until char 1 of r is not 0
delete char 1 of r
end repeat
return r
end bAdd
on mouseUp
put fld "path2" into fPath
open file fPath for read
put the long seconds into performanceTime
put 0 into T
put 0 into S
put 0 into tTemp
put fld 1 into upperLimit
repeat with C = 1 to 999999999999
read from file fPath for 10000 line
if it is empty then exit repeat
if line -1 of (char -20 to -1 of it) < upperLimit then
replace cr with comma in it
add sum(it) to tTemp
else
repeat for each line L in it
if L > upperLimit then exit repeat
add L to tTemp
end repeat
end if
if tTemp > 100000000000000 then
put bAdd(T,tTemp) into T
put 0 into tTemp
end if
if the seconds > S then
put the seconds + 5 into S
if L is empty
then put C && item 1 of it into fld 2
else put C && L into fld 2
unlock screen
lock screen
end if
if L > upperLimit then exit repeat
end repeat
put C && L into fld 2
put bAdd(T,tTemp) into T
put T && L && (the long seconds - performanceTime)
close file fPath
end mouseUp
On Sun, Nov 15, 2015 at 4:47 PM, Alex Tweedly <a...@tweedly.net> wrote:
> 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
>
_______________________________________________
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
