much faster sequences of primes

Don't hold back

much faster sequences of primes

PostPosted by drab » Mon Oct 20, 2014 12:23 pm

I was using sequences of prime numbers with an idiom of the Rth prime function:

negative2 pi iota n

But I noticed bad performance with large n, and it seemed to be slowing down with the square of n.

So, I wrote a simple defined function that did the same thing, but used only the next prime function (1 pi).

That was thousands of time faster, and did not slow down with the square of n.

So, I suggest a great enhancement to the Rth prime function (negative2 pi), which would recognize if the argument is an arithmetic progression vector, and take the extreme shortcut.
drab
 
Posts: 295
Joined: Thu Oct 09, 2014 6:23 am

Re: much faster sequences of primes

PostPosted by drab » Mon Oct 20, 2014 3:01 pm

And even if the argument is just an integer vector, and not necessarily an arithmetic progression, a LOT could be saved by similarly processing it in grade-up order.
drab
 
Posts: 295
Joined: Thu Oct 09, 2014 6:23 am

Re: much faster sequences of primes

PostPosted by forummaster » Mon Oct 20, 2014 4:35 pm

drab wrote:And even if the argument is just an integer vector, and not necessarily an arithmetic progression, a LOT could be saved by similarly processing it in grade-up order.

That's a great idea.

As to processing the Nth prime value, there is already code to remember the last Nth Prime argument and result and to use it as a starting point for the next argument, so I'm puzzled as to why your code slowed down. Can you provide an example so I can see where my one value cache isn't helping?
forummaster
 
Posts: 555
Joined: Wed Jan 23, 2013 1:00 pm

Re: much faster sequences of primes

PostPosted by drab » Tue Oct 21, 2014 9:22 am

Here is a defined operator which will not only process it's arguments one at a time in increasing order, but will also only run the function only once on each unique value, even if values are repeated.

z←(f inorder) v;o;vs;uvs;uzs;zs
o←⍋v
vs←v[o]
uvs←∪vs
uzs←f¨uvs
zs←(+/uvs∘.=vs)/uzs
z←zs[vs⍳v]

I have another defined operator which can do a similar thing for nested arrays, but that may be overkill.
drab
 
Posts: 295
Joined: Thu Oct 09, 2014 6:23 am

Re: much faster sequences of primes

PostPosted by manandpc » Tue Oct 21, 2014 11:13 am

drab wrote:I was using sequences of prime numbers with an idiom of the Rth prime function:

negative2 pi iota n

But I noticed bad performance with large n, and it seemed to be slowing down with the square of n.

So, I wrote a simple defined function that did the same thing, but used only the next prime function (1 pi).

That was thousands of time faster, and did not slow down with the square of n.

So, I suggest a great enhancement to the Rth prime function (negative2 pi), which would recognize if the argument is an arithmetic progression vector, and take the extreme shortcut.

There is a faster implementation:

Code: Select all
      ⎕ts ⋄ N←10000000 ⋄ z←(2πN)⍴c←0 ⋄ i←1 ⋄ :while N≥i←1πi ⋄ z[c←c+1]←i ⋄ :endwhile ⋄ ⍴z ⋄ ⎕ts
2014 10 21 12 3 12 427
664579
2014 10 21 12 3 42 863
      ⎕ts ⋄ ⍴⍸ 0π ⍳ 10000000 ⋄ ⎕ts
2014 10 21 12 4 6 656
664579
2014 10 21 12 4 15 308
      ⎕ts ⋄ ⍴prime 10000000 ⋄ ⎕ts
2014 10 21 12 4 26 383
664579
2014 10 21 12 4 28 614
     
      ⎕cr'prime'
p ← prime n;d;i                                                                   
d ← ⌊√n                                                                           
p ← 0 1 1 0 1,(0⌈n-5) ⍴ 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0
:if n < 49                                                                         
  p ← ⍸ n↑p                                                                       
:else                                                                             
  i ← 7                                                                           
  :while 1                                                                         
    p[ i× ¯1+i+ ⍸ p[ ¯1+i+ ⍳ 1+(⌊n÷i)-i ] ] ← 0                                   
    i+ ← p[ i+ ⍳ ⌈i÷2 ] ⍳ 1                                                       
  :until i > d                                                                     
  p ← ⍸ p                                                                         
:endif                                                                             
     
      ⍝ see, 'APL highly optimize prime number generator function' topic
     
manandpc
 
Posts: 67
Joined: Tue Jun 19, 2012 9:39 am

Re: much faster sequences of primes

PostPosted by drab » Wed Oct 22, 2014 6:46 am

Answering your question of Mon Oct 20, 2014 5:35 pm ...

This is my defined function to quickly build a sequence of N primes:

z←ps n;p
z←0⍴p←1
go:→(n≤⍴z)/0
z←z,p←1πp
→go

It works the same as ¯2π:

ps 9
2 3 5 7 11 13 17 19 23
¯2π⍳9
2 3 5 7 11 13 17 19 23

Defined operators t1 and t2 just run their functions, and return how long it took.

The time for function ps is fairly linear wrt the size of N:

ps t1 99
0.001125065901
ps t1 999
0.01211279636
ps t1 9999
0.2419504361

But the time for ¯2π is not linear at all:

¯2π t2 ⍳99
0.001940112212
¯2π t2 ⍳999
0.3270593882
¯2π t2 ⍳9999
47.22952671
drab
 
Posts: 295
Joined: Thu Oct 09, 2014 6:23 am

Re: much faster sequences of primes

PostPosted by drab » Wed Oct 22, 2014 8:08 am

I was not surprised to discover that the limit on finding prime factors was a 63-bit integer:

π9223372036854775807
7 7 73 127 337 92737 649657
π9223372036854775808
DOMAIN ERROR

(64⍴2)⊤9223372036854775807
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1
(64⍴2)⊤9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

because beyond that, they are stored as floating point numbers.

However, I was surprised (and very pleased) that it continued working for much larger numbers, if they are expressed as rational numbers:

π⎕←¯1+2*128
3.402823669E38
DOMAIN ERROR

π⎕←¯1+2*128x
340282366920938463463374607431768211455
3 5 17 257 641 65537 274177 6700417 67280421310721
drab
 
Posts: 295
Joined: Thu Oct 09, 2014 6:23 am

Re: much faster sequences of primes

PostPosted by drab » Wed Oct 22, 2014 8:14 am

Did you implement rational numbers by actually actually storing the prime factors of the numerator and denominator?
drab
 
Posts: 295
Joined: Thu Oct 09, 2014 6:23 am

Re: much faster sequences of primes

PostPosted by forummaster » Sat Jan 28, 2017 12:01 am

drab wrote:Did you implement rational numbers by actually actually storing the prime factors of the numerator and denominator?

Rational numbers are implemented using the very excellent Free Open Source MPIR (Multiple Precision Integer and Rational) library. The format is simply Numerator and Denominator, however, the numbers are stored in a Canonical form in which the numerator and denominator have no factors in common (i.e., their GCD is 1).
forummaster
 
Posts: 555
Joined: Wed Jan 23, 2013 1:00 pm

Re: much faster sequences of primes

PostPosted by forummaster » Sat Jan 28, 2017 12:34 am

drab wrote:Answering your question of Mon Oct 20, 2014 5:35 pm ...

This is my defined function to quickly build a sequence of N primes:

z←ps n;p
z←0⍴p←1
go:→(n≤⍴z)/0
z←z,p←1πp
→go

It works the same as ¯2π:

ps 9
2 3 5 7 11 13 17 19 23
¯2π⍳9
2 3 5 7 11 13 17 19 23

Defined operators t1 and t2 just run their functions, and return how long it took.

The time for function ps is fairly linear wrt the size of N:

ps t1 99
0.001125065901
ps t1 999
0.01211279636
ps t1 9999
0.2419504361

But the time for ¯2π is not linear at all:

¯2π t2 ⍳99
0.001940112212
¯2π t2 ⍳999
0.3270593882
¯2π t2 ⍳9999
47.22952671
Thanks for the heads up. When I originally implemented this function, I borrowed an idea from Roger Hui of Dyalog which is to rely upon a table of results for every N values where N is 1E5. The top end of the table is such that N is the largest number such that it is a multiple of 1E5 and that ¯2πN returns a number just below 2*32; that N is 203200000. To find an answer, first do a binary search of the table finding the multiples of 1E5 which are the upper and lower limits of a range of 1E5 values, then compare N with the midpoint of the upper and lower values and either search forwards from the lower value or backwards from the upper value using (Next Prime) or ¯1π (Previous Prime), respectively.

Because the increment (1E5) is so large, this means that the table is designed for large arguments, not small ones, so it's no surprise that it performs poorly for numbers < 1E5. On the other hand, it works quite well for numbers as large as 2E8.

In any case, I've introduced two new tables for the range of N in [0, 1E2] by 1s, and [0, 1E5] by 100s. This should allow ¯2πN to produce results on small arguments quite quickly.

This enhancement is available in the latest beta version.

http://www.nars2000.org/download/binaries/beta/
forummaster
 
Posts: 555
Joined: Wed Jan 23, 2013 1:00 pm


Return to Open Discussion

Who is online

Users browsing this forum: No registered users and 1 guest

cron