Calculating the sum of a *lot* of primes

Geoff Canyon gcanyon at gmail.com
Mon Nov 16 09:15:03 EST 2015


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 <alex at 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 at 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 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