Re: A faster Divisors function

*To*: mathgroup at smc.vnet.net*Subject*: [mg22906] Re: [mg22890] A faster Divisors function*From*: Hartmut Wolf <hwolf at debis.com>*Date*: Thu, 6 Apr 2000 02:04:26 -0400 (EDT)*Organization*: debis Systemhaus*References*: <200004050240.WAA00989@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Julian Aguirre Estibalez schrieb: > > I need to find the divisors of a large collection of integers, all > of them having small prime factors. An example is > > In[22]:= n = 5910740121125371424569009155900; > > Mathematica factorizes it without problems: > > In[23]:= FactorInteger[n] // Timing > > Out[23]= > {0. Second, {{2, 2}, {3, 2}, {5, 2}, {7, 2}, {11, 1}, {23, 1}, {37, 1}, > {79, 1}, {179, 1}, {191, 1}, {223, 1}, {239, 1}, {269, 1}, {419, 1}, > {457, 1}, {1931, 1}}} > > But when trying to compute Divisors[n], I stopped the calculation > after one hour. I have written my own divisors function: > > MyDivisors[n_Integer]:=With[{f=FactorInteger[n]}, > Sort at Fold[Flatten@Outer[Times, #1, #2]&, {1}, First/@f^Range[0, Last/@f]]] > > In[32]:=Length at MyDivisors[n] // Timing > > Out[32]={16.7333 Second, 331776} > > As you can see, it is fast, but uses a lot of memory. Of course, > it works well with numbers that can be easily factorized, which is always > the case with the problem I am working in. Now my question. Can any of you > suggest a better way of improving the speed or diminishing the memory > rquirements of MyDivisors? > Dear Julian, when I time and memory count your function on my machine I get: In[3]:= MemoryInUse[] Out[3]= 1136736 In[4]:= Length at MyDivisors[n] // Timing Out[4]= {43.552 Second, 331776} In[5]:= MaxMemoryUsed[] Out[5]= 30158648 In[6]:= MemoryInUse[] Out[6]= 1155344 This alternative gives (with restarted kernel): In[1]:= Divisors3[n_Integer] := With[{f = FactorInteger[n]}, Sort @ Flatten @ Outer[Times, Sequence @@ (First /@ f^Range[0, Last /@ f])]] In[2]:= n = 5910740121125371424569009155900 In[3]:= MemoryInUse[] Out[3]= 1136344 In[4]:= Length at Divisors3[n] // Timing Out[4]= {70.882 Second, 331776} In[5]:= MaxMemoryUsed[] Out[5]= 56734480 So this version lasts 1.6 times and takes 1.9 times of the memory. However this version ... In[1]:= Divisors4[n_Integer] := With[{f = FactorInteger[n]}, Fold[Flatten[{#1, Outer[Times, #1, #2]}] &, {1}, First /@ f^Range[1, Last /@ f]]] In[3]:= MemoryInUse[] Out[3]= 1136864 In[4]:= Length at Divisors4[n] // Timing Out[4]= {17.725 Second, 331776} In[5]:= MaxMemoryUsed[] Out[5]= 26176768 only takes 0.4 of your time, and 0.86 of your memory. As suspected the memory conservation utility In[1]:= << Utilities`MemoryConserve` has no significant influence on neither timing nor memory consumption. Also please regard: In[4]:= Length[With[{w = 2^16 - 1}, Table[, {1331776}]]] // Timing Out[4]= {2.283 Second, 1331776} In[5]:= MaxMemoryUsed[] Out[5]= 6491488 So a significant part of your memory (1/6 or 1/5 resp.) is taken by the resulting expression. Perhaps, if you make the calculation repeatedly, and also while doing something with your result, it might be wise to explicitly clear any symbol no longer in use (perhaps including Out[..] where data might be kept, althought not having been printed). Hartmut

**References**:**A faster Divisors function***From:*Julian Aguirre Estibalez <mtpagesj@lg.ehu.es>