Karim Belabas on Sat, 29 Oct 2022 14:49:50 +0200


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

Re: unordered but memory-friendly fordiv() (without calling to divisors()) 

* Max Alekseyev [2022-10-28 23:30]:
[...]
> Formally speaking the divisors of any number form a recursively enumerable
> set, and its structure can be exploited to produce the divisor values
> efficiently. (Perhaps, this is already done internally by the divisors()
> function.)

It is. Given PARI's memory model, it's not easy to do this while
bounding memory (it's trivial to do in optimal space if all divisors are
to be stord: the memory used is the memory occupied by the divisors).

> Can we have a variant of fordiv() / fordivfactored() that will not call to
> divisors() but generate the divisors on-fly at the cost of not enforcing
> them be in order?

Easy to do directly in GP, with acceptable inefficiencies. Little
motivation to include it in PARI, compared to the work involved.
Adapting fordivfactored from forvec/parforvec is particularly easy, with
low overhead ! (fordiv is much harder, as seen above).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251), Université de Bordeaux
Vice-président en charge du Numérique
T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/
`