Ilya Zakharevich on Sun, 07 Jan 2024 18:14:31 +0100


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

forprimestep 50000 times slower than needed


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.)

Thanks,
Ilya

P.S.  High primelimit speeds up sieving about 1.5 orders of magnitude
      (up to primelimit²).