Bill Allombert on Fri, 17 Nov 2006 23:32:44 +0100


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

Re: time-limited integer factorization


On Fri, Nov 17, 2006 at 01:45:46PM -0800, Max A. wrote:
> Dear pari-users,
> 
> Is there a way to perform integer factorizations in GP bounded in time?
> Say, I want to factor a certain number but spend at most one hour. If
> factorization is not finished within this time frame, I want to it to
> return all found factors along with a composite co-factor.

This script should do the trick on UNIX/Linux systems.

default(factor_add_primes,1)
install("getpid","l")
timefact(N,sec)=
{
  trap(siginter,0,
    system(Str("(sleep ", sec ,";kill -INT ",getpid(),")&"));
    factor(N));
  factor(N,0);
}

where N is the number to factor and sec the number of seconds allowed.
Note that primes found by factor are stored in addprimes(). In some
circumstances, you want to use removeprimes() to delete them.

Note: instead of using system(), we could use the function alarm() and
trap SIGALARM.

Cheers,
Bill.