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())


Karim, it is easy to do once (and with overhead), but becomes boring when it needs to be implemented over and over again. 
From my experience, in roughly half of the cases when I used fordiv(), the order of divisors was not important and I would have happily used fordivunordered() instead. At the same time the demand for memory storage for divisors sometimes may be quite excessing and this new fordiv*() would be a saver.
Also, I remember at least one other message in this maillist ("Using forvec as fordiv") from Charles Greathouse, so you may consider this feature requested by at least two users.

If it's a firm No, then can we have at least a parallel pardiv() function, which naturally has to be unordered? (this is probably a question to Bill)

Regards,
Max

On Sat, Oct 29, 2022 at 8:48 AM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:
* 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/
`