Karim BELABAS on Mon, 9 Dec 2002 15:07:38 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: primetables SEGV |
On Mon, 9 Dec 2002, John Cremona wrote: [ directly to me, not to pari-dev ] > While you are working on the prime functions, can I remind you that it > is often useful to have the inverse function which given p returns i > such that p=prime(i), as in the following: [...] > pith(x) = > { > local(l,r,lx); > if (x <= 2, return (x==2)); > lx = log(x); > l = floor(x/lx); > r = floor(l * (1 + 3/(2*lx))); > while (r-l>1, > m = (l+r)>>1; > if (prime(m)<=x, l=m, r=m)); > l; > } It is already there [ install(pith, lL) ] (written by Bill). Actually this is the standard \pi(x) = #{p <= x}. It was not installed by default since we could not find a proper name at the time (then we forgot about it I'm afraid...). 'pith' is not realy suitable, and 'pi' would be too confusing. Hum, what about primepi() ? Karim. P.S: Both prime() and pith() could use a builtin table [ e.g of prime(k*10^4), k < 50, then prime(K * 10^6), K < 50 ] to make larger strides. P.S2: Anybody interested in implementing analytic algorithms for the basic prime-counting functions ? (M, pi, psi) @article {MR96d:11139, AUTHOR = {Del{\'e}glise, M. and Rivat, J.}, TITLE = {Computing {$\pi(x)$}: the {M}eissel, {L}ehmer, {L}agarias, {M}iller, {O}dlyzko method}, FJOURNAL = {Mathematics of Computation}, VOLUME = {65}, YEAR = {1996}, NUMBER = {213}, PAGES = {235--245}, } @article {MR98f:11135, AUTHOR = {Del{\'e}glise, Marc and Rivat, Jo{\"e}l}, TITLE = {Computing the summation of the {M}\"obius function}, FJOURNAL = {Experimental Mathematics}, VOLUME = {5}, YEAR = {1996}, NUMBER = {4}, PAGES = {291--295}, } @article {MR99a:11147, AUTHOR = {Del{\'e}glise, Marc and Rivat, Jo{\"e}l}, TITLE = {Computing {$\psi(x)$}}, FJOURNAL = {Mathematics of Computation}, VOLUME = {67}, YEAR = {1998}, NUMBER = {224}, PAGES = {1691--1696}, } -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud Email: Karim.Belabas@math.u-psud.fr F-91405 Orsay (France) http://www.math.u-psud.fr/~belabas/ -- PARI/GP Home Page: http://www.parigp-home.de/