I happened to stumble across some GMP benchmarks for calculating pi(x). May interest you
https://gmplib.org/pi-with-gmp.html -------------------------------------------- On Thu, 3/24/16, Mike Day <[email protected]> wrote: Subject: Re: [Jchat] primes To: [email protected] Date: Thursday, March 24, 2016, 12:36 AM Sorry not to be clear. I'd come across a Python function to calculate primepi and/or sum of primes. I translated it into c, J and Pari GP with the sorts of performance times indicated. The method rests on these properties: N(v,p) = N(v,p-1) - (N(v/p, p-1) - N(p-1,p-1)) S(v,p) = S(v,p-1) - p(S(v/p, p-1) - S(p-1,p-1)) where N(v,m) (S(v,m)) is the number (sum) of integers in [2,v] that remain after sieving by all primes smaller than or equal to m . The implementation is clever in that it doesn't need to explicitly include all integers in the sieve, but instead uses a couple of arrays of size ~ root(n). My Lehmer effort is based on Weisstein's description in Wolfram World, and is MUCH more complicated and less J-like than what I chose to call primepi. FYI, I've just rediscovered my note to self on the apparent error in Weisstein's description: " NB. Line 1 is wrong; the limits on i,j should read 1<=i<j<=a " (ie _not_ 1<=i<=j<=a ) OK? Mike PS - sorry that table of (very approx) timings displayed poorly for you. On 23/03/2016 13:33, 'Jon Hough' via Chat wrote: > Sorry, I'm confused, what's the difference between primepi and lehmer? > > Anyway, it seems your J Lehmer implementation calculates pi(1e9) in ~2 seconds. > That doesn't seem bad. I mean it's usable. > -------------------------------------------- > On Tue, 3/22/16, Mike Day <[email protected]> wrote: > > Subject: Re: [Jchat] primes > To: [email protected] > Date: Tuesday, March 22, 2016, 7:32 PM > > fwiw, I messed around > with primepi(n) and sum-of-primes-to(n) a few months > ago. (Sum of primes can be dealt with in a > similar fashion to > primepi). Lehmer > didn't perform well in my attempts to apply > it. The Wolfram page on > Lehmer > used to have an error in > one of the summations, so take care if using > http://mathworld.wolfram.com/LehmersFormula.html > (I'm sorry but I can't see if it's > still wrong right now. Weisstein didn't > acknowledge an attempt to report the problem, > and I naven't retained a > copy of > my message.) > > Timings for primepi(n), on a previous > laptop: > +------+----------+-------+-------+--------+-----+-----+-----+----+------+ > |Times |n= |1000000|1e7 |1e8 > |1e9 |1e10 |1e11 |1e12|1e13 | > +------+----------+-------+-------+--------+-----+-----+-----+----+------+ > |c++~ |primepi |1ms |5ms > |14ms |150ms|1.1s |9.4s |86s |13m05s| > +------+----------+-------+-------+--------+-----+-----+-----+----+------+ > |J |primepi |1ms > |6ms |20ms |62ms |3.4s |16.6s|92s |8m15s | > +------+----------+-------+-------+--------+-----+-----+-----+----+------+ > |J |Lehmer |4ms > |22ms |190ms |2.2s |8m23s|.... > |....|.... | > +------+----------+-------+-------+--------+-----+-----+-----+----+------+ > |PariGP|my-primepi|100ms |616ms |4.4s > |34.6s|4m27s|.... |....|.... | > +------+----------+-------+-------+--------+-----+-----+-----+----+------+ > |PariGP|built-in > |0.004ms|0.327ms|0.0011ms|104ms|27.8s|.... |....|.... | > +------+----------+-------+-------+--------+-----+-----+-----+----+------+ > > (Apologies if this doesn't > display well - I've tried!) > > On the present laptop, with an amd chip: > _1 p: <.1e8 > > 5761455 > > > timer'{.{:primepi <.1e8' > > +---------+-------+ > > |0.0179977|5761455| > > +---------+-------+ > > _1 p: > <.1e10 > > |limit error > > | _1 p:<.10000000000 > > > timer'{.{:primepi <.1e10' > > +-----+---------+ > > |3.857|455052511| > > +-----+---------+ > > > As the > comparisons above demonstrate, my attempt at coding Lehmer > in J > performed poorly. I code c > and c++ very naively, not knowing them well, > so it's not surprising that J outperforms > my c++ effort for larger n. > The first row of > the Pari GP times are for my attempt at translating my > J function into its script. Pari GP's > built-in primpi function has is > very fast > for lower n, but degrades sharply for larger values. It > might be > relevant that I initialise GP with > parisize = 8000000, primelimit = > 4270000000 > > The > downside, as others have said, is that an efficient > primepi > function does > NOT > scan all primes on its way to counting or summing them! > > Code available if > interested. > > Mike > > On 22/03/2016 00:31, 'Jon > Hough' via Chat wrote: > > Since p: has > a limit (why is that, by the way? I have written a pi(x) > function using Miessel's formula in another language and > it does grind to a slowdown for values much larger than 1e7, > so that might be the reason. I'm assuming internally J > uses Miessel or Lehmer's formula.), > > > it might be better to "cheat" and just use a > hardcoded value for pi(1e9). > > > > https://primes.utm.edu/howmany.html > (scroll down to table 1) > > > > > > Also, possibly the > worst idea ever, why not iterate from 2 to 1e9 and do prime > tests and keep a record of the previously found prime to > compare the final digits with the next prime, and keep a > record of the comparisons. Probably hopelessly slow, and > inefficient. > > > > > -------------------------------------------- > > On Tue, 3/22/16, Raul Miller <[email protected]> > wrote: > > > > Subject: Re: [Jchat] > primes > > To: "Chat > forum" <[email protected]> > > Date: Tuesday, March 22, > 2016, 12:14 AM > > > > Oh, I coded wrong. The > > limit error was from p:, but > I should not have been > > feeding it the value 1e9. > > > > Sometimes I wonder how I get > anything > > done... > > > > Thanks, > > > > -- > > Raul > > > > > > On Mon, Mar > > 21, 2016 at 11:03 AM, Roger > Hui <[email protected]> > > wrote: > > > > > > > > it should be > straightforward to do the extra credit > > problem > > > > > > I should > > have checked. The extra > credit problem is for 100,000,000 > > primes. > > > > > > _1 p: > > _1+2^31 > > > 105097564 > > > p: 1e8 > > > > > 2038074751 > > > > > > So the > > limit error is not in p: . > > > > > > > > > > > > > > > > > > > > > On Sun, Mar 20, 2016 > > at 4:44 PM, Raul Miller > <[email protected]> > > > wrote: > > > > > > > Rosettacode has a > task now, for this > > item. > > > > > > > > http://rosettacode.org/wiki/Prime_conspiracy#J > > > > > > > > And, > > hypothetically speaking, it > should be straightforward to do > > the > > > extra > > > > > > credit problem. But that > doesn't work. Given: > > > > > > > > dgpairs=: 2 > > (,'->',])&":/\ > 10 | p: > > > > > combine=: ~.@[ ,.~ ' ',.~ > > ":@,.@(+//.) > > > > > > > > We can try this: > > > > > > > > > > /:~ > combine&;/|: > > (~.;#/.~)@dgpairs@((+ > i.)/)"1 > > > > > > (1e6*i.1e3),.1e6+999>i.1e3 > > > > > > > > |limit error: > dgpairs > > > > > > > > ... but p: > > doesn't work for values > like 1e9 (1 p: works, but not > > p: > > > > itself). > > > > > > > > > > And, for example, > Roger has > > worked out some > ways of dealing with large > > > > primes -- see > looking at > > > > http://code.jsoftware.com/wiki/Essays/Primality_Tests > > -- but we don't > > > have > > > > anything that's > a drop in > > replacement for > the p: monad. > > > > > > > > So this presents > something of a > > problem - > how would we tackle a problem > > > > > > like this? > > > > > > > > (Please feel free > to change forum to > > programming if you've got > working > > > > > code > > > > rather than just > > ideas...). > > > > > > > > > > Thanks, > > > > > > > > > > -- > > > > Raul > > > > > > > > > > > > > > > > > > > > > > On Tue, Mar > > 15, 2016 at 7:02 AM, Cliff > Reiter <[email protected]> > > > > wrote: > > > > > > > > > A look at the > frequencies of > > pairs of > last digits of successive primes: > > > > > > > /:~({.,#)/.~2]\10|p:4+i.1e7 > > > > > > > > > > > > 1 1 446808 > > > > > > > > > > 1 > > 3 756071 > > > > > > > > > > > > 1 7 769924 > > > > > > > > > > 1 9 526953 > > > > > > > > > > > > 3 1 593196 > > > > > > > > > > 3 > > 3 422302 > > > > > > > > > > > > 3 7 714795 > > > > > > > > > > 3 9 769915 > > > > > > > > > > > > 7 1 639383 > > > > > > > > > > 7 > > 3 681759 > > > > > > > > > > > > 7 7 422289 > > > > > > > > > > 7 9 756852 > > > > > > > > > > > > 9 1 820369 > > > > > > > > > > 9 > > 3 640076 > > > > > > > > > > > > 9 7 593275 > > > > > > > > > > 9 9 446032 > > > > > > > > > > > > The 1 follows > 1 as > > rare as 9 follows 9, > but rarer is 3 follows 3 as > > > rare > > > > > as 7 > > follows 7. 9 1 most popular! > Very curious. Probably should > > move to > > > > > JProg' > Best, > > Cliff > > > > > > > > > > > > > > > > > > > > > > > > > > > > > On 3/14/2016 12:03 PM, R.E. > Boss wrote: > > > > > > > > > > > >> > > > > >> > > > > > > > >https://www.quantamagazine.org/20160313-mathematicians-discover-prime-conspiracy/ > > > > >> R.E. > Boss > > > > >> > > ---------------------------------------------------------------------- > > > > For > > > > > > >> information about J > forums see http://www.jsoftware.com/forums.htm > > > > > > >> > > > > > > > > > > > > ---------------------------------------------------------------------- > > > > > For > information about J forums > > see http://www.jsoftware.com/forums.htm > > > > > > > > > > > ---------------------------------------------------------------------- > > > > For information > about J forums see http://www.jsoftware.com/forums.htm > > > > > > > > > ---------------------------------------------------------------------- > > > For information about J > forums see http://www.jsoftware.com/forums.htm > > > > > ---------------------------------------------------------------------- > > For information about J > forums see http://www.jsoftware.com/forums.htm > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > --- > This email has been checked for viruses by > Avast antivirus software. > https://www.avast.com/antivirus > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
