Message Boards Message Boards

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

What is Mathematica doing?

Posted 10 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
Posted 10 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
Posted 10 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.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract