American Citizen on Thu, 03 Jul 2025 22:04:56 +0200


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

Re: question on execution time for qfbsolve


Bill:

Thanks for the comment. I am doing millions of these qfbsolve(), but the numbers <= 1e6 in general, so I won't see much speed increase.

At least I can avoid an O^2 execution time bottle neck caused by 2 nest loops, in the brute force method I was using in the past.

Randall

On 7/3/25 00:20, Bill Allombert wrote:
On Wed, Jul 02, 2025 at 08:14:09PM -0700, American Citizen wrote:
I ran over the first 100,000 integers

? for(i=1,100000,qfbsolve(Qfb(1,0,1),i,3))
cpu time = 3,394 ms, real time = 3,394 ms.
? for(i=1,100000,qfbsolve(Qfb(1,0,1),[i,factor(i)],3))
cpu time = 3,348 ms, real time = 3,348 ms.

so it is about the same, not much improvement, 46 milliseconds.
Of course since you are including the time to factor i!

The point is to avoid factoring i again when its factorization is already
known.

For example:

? #
? forfactored(i=1,1000000,qfbsolve(Qfb(1,0,1),i,3))
   ***   last result computed in 2,767 ms.
? for(i=1,1000000,qfbsolve(Qfb(1,0,1),i,3))
   ***   last result computed in 2,994 ms.
? for(i=1,1000000,qfbsolve(Qfb(1,0,1),[i,factor(i)],3))
   ***   last result computed in 3,131 ms.

Of course for small numbers, it should not make a lot of difference.

Cheers,
Bill.