Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2000
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2000

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

Search the Archive

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


  • Prev by Date: Re: ReleaseInfo[command_String]? -A useless dream?
  • Next by Date: Re: molecular interactions
  • Previous by thread: Re: A faster Divisors function
  • Next by thread: Timing[] holes?