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