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 removeprimes(). 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 machinery. I don't know exactly how I can fix that. Cheers, Bill.