Re: fordiv question

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Feb 05, 2015 at 02:25:45PM -0600, Ariel Pacetti wrote:
> 
> Dear pari users,
> 
> I realized that using fordiv for big numbers (with easy
> factorization) blows down completely the memory. Here is an example:
> 
> ? fordiv(2^240*3^50*5^20*7^15,x,1)
>   *** fordiv: the PARI stack overflows !
>   current stack size: 128000000 (122.070 Mbytes)
> 
> ? forvec(X=[[0,240],[0,50],[0,20],[0,15]],x=2^X[1]*3^X[2]*5^X[3]*7^X[4],1)
> 
> Is fordiv first computing the set of all divisors and then
> performing the operation?

Yes, it does, because it is specified to iterate over the divisors by increasing
order, something your forvec loop does not.

> Also note the timings (factoring takes 0 time)
> 
> ? forvec(X=[[0,240],[0,50],[0,20],[0,15]],x=2^X[1]*3^X[2]*5^X[3]*7^X[4],1)
> ? ##
>   ***   last result computed in 4 ms.
> ? fordiv(2^240*3^50*5^20,x,1)
> ? ##
>   ***   last result computed in 90 ms.

You are using the flag 1 to forvec so you are skipping a lot of divisors.

? my(s);forvec(X=[[0,240],[0,50],[0,20],[0,15]],x=2^X[1]*3^X[2]*5^X[3]*7^X[4];s++);s
%19 = 4129776
? ##
  ***   last result computed in 2,736 ms.
? my(s);fordiv(2^240*3^50*5^20*7^15,x,s++);s
  *** fordiv: Warning: increasing stack size to 16000000.
  *** fordiv: Warning: increasing stack size to 32000000.
  *** fordiv: Warning: increasing stack size to 64000000.
  *** fordiv: Warning: increasing stack size to 128000000.
  *** fordiv: Warning: increasing stack size to 256000000.
  *** fordiv: Warning: increasing stack size to 512000000.
%20 = 4129776
? ##
  ***   last result computed in 3,253 ms.

(the time difference is about the time to sort the list of divisors).

With the flag 1 to forvec:

? my(s);forvec(X=[[0,240],[0,50],[0,20],[0,15]],x=2^X[1]*3^X[2]*5^X[3]*7^X[4];s++,1);s
%22 = 3876
? ##
  ***   last result computed in 4 ms.

Cheers,
Bill.