Karim Belabas on Tue, 06 Feb 2024 20:05:31 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: nonprime(n) 

* Bill Allombert [2024-02-06 19:08]:
> On Tue, Feb 06, 2024 at 06:14:47PM +0100, hermann@stamm-wilbrandt.de wrote:
> > On 2024-02-06 08:40, Aurel Page wrote:
> > > 257M is overkill.
> > > 
> > > $ gp -p4M
> > > ? for(n=1,2^18, prime(n));
> > > time = 1,315 ms.
> > > 
> > > We have all the necessary primes:
> > > ? prime(2^18)
> > > % = 3681131
> > > 
> > > Cheers,
> > > Aurel
> > > 
> > And why is forprime() so fast without -p...?
> > 
> > hermann@7950x:~$ gp -q
> > ? c=0;forprime(p=2,oo,c+=1;if(c==2^18,print(p);break()));
> > 3681131
> > ? ##
> >   ***   last result: cpu time 60 ms, real time 60 ms.
> 
> Compared to
> ? prime(2^18)
> %1 = 3681131
>   ***   last result computed in 5 ms.
> this is not so fast.
> 
> the issue is that "for(n=1,2^18, prime(n))" does
> 
> for(n=1,2^18, c=0;forprime(p=2,oo,c+=1;if(c==n,break())))
> 
> which is a very inefficient way to do that computation.

I agree with the conclusion, but the algorithm is a little less silly.

We start from a quick search in a small table of [p_i, \pi(p_i)],
for some quickly increasing sequence of primes p_i. We then start the
forprime loop at the largest p_i less than our target: this gains a
constant factor. A larger table would mean a larger gain (and more
memory used).

Note that the initial part of forprime iterates over a bounded
number of differences of primes. We could switch to storing actual
primes (the table would only be 8 times larger), but lots of functions
would be immensely sped up as long as we remain in the table. For
instance prime(n) would become O(1) time and primepi(x) would use O(log x)
time. Etc.

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/