Re: time-limited integer factorization

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Fri, Nov 17, 2006 at 11:25:18PM +0100, Bill Allombert wrote:
> 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);
> }

Well that will not really work because if the factorisation finish
before the allocated time, you still get the SIGINT later on and that
will terminate the next factorisation 

So I propose a cleaner way. You need the following C file:
----%8---alarm.c----------------------------
#include <pari/pari.h>
#include <unistd.h>
/*
GP; install("startalarm","vL",,"./alarm.so");
GP; install("stopalarm","v",,"./alarm.so");
GP; addhelp(startalarm,"(sec): interrupt GP after sec seconds");
GP; addhelp(stopalarm,"(): stop a pending alarm");
*/

static void pari_sigalarm(int foo) { raise(SIGINT); }
void
startalarm(long sec)
{
  os_signal(SIGALRM,pari_sigalarm);
  alarm(sec);
}
void stopalarm(void) { alarm(0); }
---------------------------------------------
(You can compile and run it with gp2c-run)

Now the script is a bit simpler:

default(factor_add_primes,1)
install("startalarm","vL",,"./alarm.so");
install("stopalarm","v",,"./alarm.so");
timefact(N,sec)= 
{
  trap(siginter,0,startalarm(sec);factor(N));
  stopalarm();
  factor(N,0);
}

Cheers,
Bill