Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>