Re: forprimestep 50000 times slower than needed

[Loïc Grenié <loic.grenie@gmail.com>]

On Sun Jan 7, 2024, at 18:14, Ilya Zakharevich wrote:

With primelimit 4 billions (all these commands have the same semantic of isprime()):

  (08:57) gp > for(n=1,1,forprimestep(p=nextprime(10^8),10^8+10^9,10^9,))
  time = 220 ms.
  (08:58) gp > for(n=1,1,forprimestep(p=nextprime(10^8),10^8+10^8,10^8,))
  time = 78 ms.
  (08:59) gp > for(n=1,1,forprimestep(p=nextprime(10^8),10^8+10^7,10^7,))
  time = 15 ms.

Now increasing the count (with each command in the loop havingn the same semantic):

  (08:59) gp > for(n=1,10,forprimestep(p=nextprime(10^8),10^8+10^6,10^6,))
  time = 31 ms.
  (08:59) gp > for(n=1,100,forprimestep(p=nextprime(10^8),10^8+10^5,10^5,))
  time = 78 ms.
  (09:00) gp > for(n=1,1000,forprimestep(p=nextprime(10^8),10^8+10^4,10^4,))
  time = 609 ms.

Of course, with the default primelimit, the speed is yet 500 times more:

  (08:55) gp > for(n=1,100000,forprimestep(p=nextprime(10^8),10^9,10^9,))
  time = 189 ms.

(This is with 2.15.4 on Windows 7.)

     I might be wrong, but I think you spend all your time in nextprime().

     On a related note, I observe that

? my(n=8);forprimestep(p=nextprime(10^8),10^8+10^n,10^n,print(p))
100000007
? my(n=9);forprimestep(p=nextprime(10^8),10^8+10^n,10^n,print(p))
?

    while I would have expected both lines to print 100000007.

         Best,

               Loïc