Re: concurrent computation of a function

[Max Alekseyev <maxale@gmail.com>]

Hi Aurel,

That's a good suggestion, but requires some effort to really understand the trade-off here, since running two algorithms sequentially bears an overhead. It'd be much easier to not care about algorithms' internals but just run the two in parallel and wait for the winner. Unfortunately, it is not easy to achieve in PARI/GP.

Regards,

Max

On Fri, Sep 20, 2024 at 3:50 AM Aurel Page <aurel.page@normalesup.org> wrote:

Hi Max,

Given your described application, why don't you simply try a cheap factorisation and then use the slow-but-polynomial algorithm if it fails? For instance trial factorisation, Pollard rho, ECM using factor(,limit) / factorint with flags, or even a few rounds of ECM by installing Z_ECM. Of course you would have to tune the factorisation attempt to be cheaper than your second method.

Best,
Aurel

On 19/09/2024 23:04, Max Alekseyev wrote:

Hi Charles,

Thank you for the insight about factorization performance in PARI. In my case, however, factorization is not the ultimate goal but just an optional shortcut to finding some special primes, while there also exists a long (but polynomial-time) "beltway". If a particular factorization happens to be easy, we get our primes fast; but if not, we still get them in a slower fashion without factorization (getting those primes is not equivalent to getting a complete factorization).

For the goal of actually factoring an array of numbers, I have a script for time-limited factorization which can be said to "give up" after a specified time limit and report just a partial factorization that was found so far. I can share it if anyone is interested. It's not helpful for my current project though.

Regards,

Max

On Thu, Sep 19, 2024 at 4:37 PM Charles Greathouse <crgreathouse@gmail.com> wrote:

If you're calculating long-running factorizations, PARI is the wrong tool.

For example, on a random semiprime C77, yafu takes 65 seconds (or 20 seconds on 4 cores, 5 seconds on which is on a single core) vs. 180 seconds for PARI.

Generally PARI is fast -- sometimes even world-class -- at ranges up to 50 digits, but beyond 60 digits it gets increasingly slow, to the point that it's hardly usable beyond 85 digits. And I haven't been following the drag races lately but I've seen NFS tuned for use at 90-110 digits and it's much faster than it used to be. (I think there was a project on mersenneforum to tune GGNFS for these ranges, but I could be misremembering.)

I would, however, find a "take this stack of numbers and end as soon as you find a factor to one of them" function very useful, especially if it came with a parxxx version to compute them literally in parallel (rather than running rho on each one, then SQUFOF on each one, then a low ECM on each, etc.). It could even be useful with a single number.

On Thu, Sep 19, 2024 at 3:42 PM Max Alekseyev <maxale@gmail.com> wrote:

Hi Bill,

Would compiling GP with debugging info and checking the crash backtrace help here?

If so, I'd be interested to step in debugging the issue.

Regards,

Max

On Thu, Sep 19, 2024 at 3:34 PM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

On Thu, Sep 19, 2024 at 03:21:19PM -0400, Max Alekseyev wrote:
> I've tried to use the error() approach extensively in my code and
> immediately got a "real" error:
>
> free(): double free detected in tcache 2
> Aborted (core dumped)

This is exactly the kind of problems I warned you about.
To fix this we would need to know exactly what line of C
code was executed when the process was interrupted.
This is very hard to come by.

Cheers,
Bill.