Oops. Thats embarrassing. I completely misread everything on that page somehow. I thought it was calculating pi(x) for some reason.
Sent from Outlook Mobile On Sun, Mar 27, 2016 at 1:28 AM -0700, "Mike Day" <[email protected]> wrote: Thanks, though I was more interested in primepi, the prime counting number, than high-precision calculation of 3.1415.... Cheers Mike On 27/03/2016 03:53, 'Jon Hough' via Chat wrote: > 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 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 (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 > 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 > > wrote: > > > > > > Subject: > Re: [Jchat] > > primes > > > To: > "Chat > > forum" > > > > 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 > > > 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 > > > > > > > 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 > > > > > > > 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 --- 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
