Re: A faster Divisors function
- To: mathgroup at smc.vnet.net
- Subject: [mg22921] Re: [mg22890] A faster Divisors function
- From: Hartmut Wolf <hwolf at debis.com>
- Date: Thu, 6 Apr 2000 02:04:37 -0400 (EDT)
- Organization: debis Systemhaus
- References: <Pine.OSF.4.21.0004051209490.1715-100000@lgdx04.lg.ehu.es>
- Sender: owner-wri-mathgroup at wolfram.com
Julian Aguirre Estibalez schrieb:
>
> Thank you for your message. Your Divisors3 was my first try. I am anxious
> to try Divisors4.
>
Dear Julian,
you'r right, I left out the final Sort (stupid error on my side), and as
it turns out, that Sort takes the time away:
In[1]:=
Divisors4[n_Integer] :=
With[{f = FactorInteger[n]},
Sort at Fold[Flatten[{#1, Outer[Times, #1, #2]}] &, {1},
First /@ f^Range[1, Last /@ f]]]
In[2]:=
n = 5910740121125371424569009155900;
In[3]:= MemoryInUse[]
Out[3]= 1136784
In[4]:= Length at Divisors4[n] // Timing
Out[4]= {36.532 Second, 331776}
In[5]:= MaxMemoryUsed[]
Out[5]= 26177680
(Corrected) Divisors4 now really takes 0.83 times of your function; so
economy of time and memory are about the same.
On the other side you should check, whether you really need that order
for further processing or whether is could be easier to restore order
only in some (perhaps simpler, shorter) final result.
Divisors4 gives the same result as
MyDivisors[n_Integer]:=
With[{f=FactorInteger[n]},
Sort at Fold[Flatten@Outer[Times, #1, #2]&, {1},
First/@f^Range[0, Last/@f]]]
Proof by induction on step of Fold (or position in FoldList):
n = 0: both partial result is {1}
Let us assume that the result of step-n of MyDivisors is equal to
(except of ordering) as of step-n of Divisors4.
n+1: for step-(n+1) we need the next-in-sequence of First/@f^Range[0,
Last/@f]] and of First/@f^Range[1, Last/@f]] respectively. But now
observe
In[11]:= Outer[Times, {a, b, c}, 3^Range[0, 2]]
Out[11]=
{{a, 3 a, 9 a}, {b, 3 b, 9 b}, {c, 3 c, 9 c}}
In[12]:= Transpose[{First[#], Rest[#]} & /@ %]
Out[12]=
{{a, b, c}, {{3 a, 9 a}, {3 b, 9 b}, {3 c, 9 c}}}
In[13]:= Join[{{a, b, c}}, Outer[Times, {a, b, c}, 3^Range[1, 2]]]
Out[13]=
{{a, b, c}, {3 a, 9 a}, {3 b, 9 b}, {3 c, 9 c}}
In[14]:= {{a, b, c}, Outer[Times, {a, b, c}, 3^Range[1, 2]]}
Out[14]=
{{a, b, c}, {{3 a, 9 a}, {3 b, 9 b}, {3 c, 9 c}}}
Flattening Out[14] is step-(n+1) of Divisors4
Flattening Out[14] give the same as Flattening Out[13]
Out[13] is the same as Out[12]
Flattening Out[12] give the same as Flattening Out[11] exept of order
Flattening Out[11] is step-(n+1) of myDivisors
Of course this is not yet a formal argument, but can be made so if {a,
b, c} -> result of step-n, 3 -> prime p at step-(n+1) and 2 -> to the
multiplicity m of p in n (regard m >= 1).
Interestingly, if you do the sorting inside of Fold
In[1]:= Divisors5[n_Integer] :=
With[{f = FactorInteger[n]},
Fold[Sort at Flatten[{#1, Outer[Times, #1, #2]}] &, {1},
First /@ f^Range[1, Last /@ f]]]
In[2]:= n = 5910740121125371424569009155900;
In[3]:= MemoryInUse[]
Out[3]= 1136784
In[4]:= Length at Divisors5[n] // Timing
Out[4]= {40.668 Second, 331776}
In[5]:= MaxMemoryUsed[]
Out[5]= 26177016
You are still faster than MyDivisors, with same memory used as of
Divisors4. What I really need is a function Merge which merges the
(unflattened) steps. That could be quite fast; but it makes no sense to
program that Merge yourself, it must be done at the kernel level, but
that is not accessible to us.
Kind regards, Hartmut