Message Boards Message Boards

0
|
9837 Views
|
3 Replies
|
1 Total Likes
View groups...
Share
Share this post:

What is Mathematica doing?

Lenny Johnson
Posted 11 years ago

I am still in the process of learning the Wolfram language. I have written the following two implementations of a function that finds all perfect numbers between the given range. The first implementation is how you may typically write such a function in a language such as c. The second version is my attempt at a more Mathematica version of the function. 

PerfectSearch[from_Integer, to_Integer] := Module[
  {id = to},
  Flatten[Rest[Reap[While[id >= from,
      sum = 0;
      n = id - 1;
      While[n > 0,
       sum = sum + If[Mod[id, n] == 0, n, 0];
       n = n - 1];
      If[sum == id, Sow[id]];
      id = id - 1;
      ]
     ]
    ]
   ]
  ]

And

PerfectSearch2[from_Integer, to_Integer] := 
 Module[{testNumbers = Range[from, to]},
  MapThread[(If[#1 == #2, #1, (##) &[]]) &,
   {
    Map[
     Function[testNum,
      Total[
       Select[
        Map[
         Function[divisor, If[Mod[testNum, divisor] == 0, divisor, 0]],
         Range[testNum - 1]
         ],
        (# > 0) &
        ]
       ]
      ], 
     testNumbers
     ]
    ,
    testNumbers
    }
   ]
  ]

I generated timing information for these two implementations as follows

p1Timing = DeleteCases[
   Flatten[
    Table[
     Timing[
      PerfectSearch[1, n];
      ],
     {n, 2, 200}
     ]
    ]
   ,
   Null];

And

p2Timing = 
  DeleteCases[
   Flatten[Table[Timing[PerfectSearch2[1, n];], {n, 2, 200}]], Null];

This timing information is shown below

enter image description here

Can anyone explain to me what Mathematica is doing in the second version of the function. It appears that the two functions perform the same up until testing numbers of 100 and above. At this point the second version of the function takes significantly less time to calculate.

Feel free to point out any improvements in the code; As I say, I am still getting to grips with Mathematica.

Thanks in advance
POSTED BY: Lenny Johnson
3 Replies
Sort By:
Lenny Johnson
Lenny Johnson
Posted 11 years ago

The "speed-up" does indeed seem to be due to the internal compilation that is occurring from the use of Map. For anyone wanting a nice review of the compilation features and limits see the link How to compile effectively
POSTED BY: Lenny Johnson
Douglas Kubler
Douglas Kubler
Posted 11 years ago

One of the things to learn about Mathematica (Wolfram) is to search the documentation for functions that may simplify your work. Try guide/NumberTheoreticFunctions in the documentaion. There you'll find Divisors[] and DivisorSum[]. A number is perfect if Total[Divisors[n]]/2==n or DivisorSum[n, Identity]/2 == n.
POSTED BY: Douglas Kubler

It is likely that at that value the internal automatic compilation of some of the code is kicking in:

In[16]:= SystemOptions[CompileOptions]

Out[16]= {"CompileOptions" -> {"ApplyCompileLength" -> \[Infinity], 
   "ArrayCompileLength" -> 250, "AutoCompileAllowCoercion" -> False, 
   "AutoCompileProtectValues" -> False, "AutomaticCompile" -> False, 
   "BinaryTensorArithmetic" -> False, "CompileAllowCoercion" -> True, 
   "CompileConfirmInitializedVariables" -> True, 
   "CompiledFunctionArgumentCoercionTolerance" -> 2.10721, 
   "CompiledFunctionMaxFailures" -> 3, 
   "CompileDynamicScoping" -> False, 
   "CompileEvaluateConstants" -> True, 
   "CompileOptimizeRegisters" -> False, 
   "CompileParallelizationThreshold" -> 10, 
   "CompileReportCoercion" -> False, "CompileReportExternal" -> False,
    "CompileReportFailure" -> False, "CompileValuesLast" -> True, 
   "FoldCompileLength" -> 100, "InternalCompileMessages" -> False, 
   "ListableFunctionCompileLength" -> 250, "MapCompileLength" -> 100, 
   "NestCompileLength" -> 100, "NumericalAllowExternal" -> False, 
   "ProductCompileLength" -> 250, "ReuseTensorRegisters" -> True, 
   "SumCompileLength" -> 250, "SystemCompileOptimizations" -> All, 
   "TableCompileLength" -> 250}}

If you play with some of these using 

SetSystemOptions[
 "CompileOptions" -> {"ApplyCompileLength" -> \[Infinity], 
   "ArrayCompileLength" -> 250, "AutoCompileAllowCoercion" -> False, 
   "AutoCompileProtectValues" -> False, "AutomaticCompile" -> False, 
   "BinaryTensorArithmetic" -> False, "CompileAllowCoercion" -> True, 
   "CompileConfirmInitializedVariables" -> True, 
   "CompiledFunctionArgumentCoercionTolerance" -> 2.1072099696478683`,
    "CompiledFunctionMaxFailures" -> 3, 
   "CompileDynamicScoping" -> False, 
   "CompileEvaluateConstants" -> True, 
   "CompileOptimizeRegisters" -> False, 
   "CompileParallelizationThreshold" -> 10, 
   "CompileReportCoercion" -> False, "CompileReportExternal" -> False,
    "CompileReportFailure" -> False, "CompileValuesLast" -> True, 
   "FoldCompileLength" -> 100, "InternalCompileMessages" -> False, 
   "ListableFunctionCompileLength" -> 250, "MapCompileLength" -> 100, 
   "NestCompileLength" -> 100, "NumericalAllowExternal" -> False, 
   "ProductCompileLength" -> 250, "ReuseTensorRegisters" -> True, 
   "SumCompileLength" -> 250, "SystemCompileOptimizations" -> All, 
   "TableCompileLength" -> 250}]

You will be able to see if the threshold where the timing makes a jump moves according to the change in the threshold for the system options setting.
POSTED BY: David Reiss
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract