Max Alekseyev on Sat, 29 Oct 2022 15:40:12 +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/
`