Phil Carmody on Thu, 19 May 2005 10:07:54 +0200

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

Re: fordiv() memory hungry

--- Bill Allombert <> wrote:
> On Wed, May 18, 2005 at 06:01:09PM -0400, Igor Schein wrote:
> > Hi,
> > 
> > (17:51:45) gp> fordiv(32!,x,0)
> >   *** fordiv: the PARI stack overflows !
> >   current stack size: 256000000 (244.141 Mbytes)
> >   [hint] you can increase GP stack with allocatemem()
> > 
> > Looks like fordiv() is no improvement over divisors() by virtue of
> > having to create the whole static array first.  Is it possible to make
> > fordiv() more memory-effcient without sacrificing the speed?
> Depends if you insist about having the divisors in increasing order.
> If you don't, you can use forvec() instead.
> If you do, then it looks like a knapsack problem, so this is going to
> be expensive.

Isn't is simply a subset of the output of the Lenstra algorithm for generating
smooth numbers? Of course, with large numbers of divisors, the problem does
grow in complexity, and also that requires non-negligible amounts of auxiliary
storage; but for what I expect to be common usage, neither should ramp up



()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

Yahoo! Mail Mobile 
Take Yahoo! Mail with you! Check email on your mobile phone.