Re: fordiv question

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Ariel Pacetti [2015-02-05 21:26]:
> 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)
>   ***   at top-level: fordiv(2^240*3^50*5^
>   ***                 ^--------------------
>   *** fordiv: the PARI stack overflows !
>   current stack size: 128000000 (122.070 Mbytes)
[...]
> While
> 
> ? 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?

It is; as documented (cf ??fordiv).

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

Er... The final 1 (nondecreasing exponent vectors) causes the above to miss
*many* divisors.

  ? c=0;forvec(X=[[0,240],[0,50],[0,20],[0,15]],c++,1)
  ? c
  %5 = 3876
  ? numdiv(2^240*3^50*5^20*7^15)
  %6 = 4129776

With the correct expression:
  ? forvec(X=[[0,240],[0,50],[0,20],[0,15]], x=2^X[1]*3^X[2]*5^X[3]*7^X[4])
  time = 2,653 ms.

Better (and faster):
  ? P = [2,3,5,7];
  ? forvec(X=[[0,240],[0,50],[0,20],[0,15]], x=factorback(P,X))
  time = 1,821 ms.

Of course, the divisors() implementation is much faster since it doesn't start
from scratch multiplying all primes together

> ? fordiv(2^240*3^50*5^20,x,1)
> ? ##
>   ***   last result computed in 90 ms.

Indeed: the time necessary to sort the divisors.

For integer arguments, fordiv is specified to output divisors by increasing
 size. If we remove that condition, then indeed an iterator is going to be
(much) faster. OTOH for other types of inputs, divisors are output in
(seemingly) random order, so we might as well always use an iterator in this
case.

All trivial to implement but I'm not sure how useful this would be...

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`