Bill Allombert on Tue, 28 Sep 2004 16:10:25 +0200

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

Re: storing primes found by factor.

On Tue, Sep 28, 2004 at 02:09:01PM +0200, Jeroen Demeyer wrote:
> Bill,
> This is certainly not a bad idea, but isn't there the risk that it will
> fill up the stack after hours of computations, possibly involving a lot
> of factorizations?
> Maybe you should bound the memory taken by such added primes, maybe the
> default factor_add_primes could be the size in bytes of all these
> primes.  Shouldn't be too hard too implement, except that these primes
> are perhaps stored in between the manually added primes?

That would involve storing meta-data that would eat memory faster than
the primes.

The idea is to only store primes that were "hard" to find, so we can
expect them not to be too large (it is almost impossible to find
primes larger than 10^40 with any of the advanced foactoring methods)
and we can expect to not find them too quickly to fill the memory.
In one megabyte, you can store 87381 primes <10^9 and 37449 primes <
10^40. Note that it is possible to remove primes manually with

However this reveal a slight bug in my patch: 

? factor(nextprime(10^100)*2); addprimes()
%4 = []
? factor(nextprime(10^100)^2); addprimes()
%5 = [10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267]

%4 is correct: we found nextprime(10^100) without any effort so it should
not be addprimes'd.

%5 is wrong: we should not store primes found by the power extraction

I don't know exactly how I can fix that.