5
$\begingroup$

I wanted to know how computers calculate basic functions like Sqrt so first I checked how humans do it I found that they use something called "Newton's method" that is basically a iterative method to find the root of a number.

that can be efficiently reproduced in Mathematica as:

SqRoot[x_, assump_, precision_] := N[Nest[(# + x/#)/2 &, assump, 21], precision]

Timing it for 2 gives:

In:= Timing[SqRoot[2, 1, 123]]
Out:= {1.75, 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492}

1.75 Seconds

While using same precision with Sqrt gives:

In:=Timing[N[Sqrt[2], 123]]
Out:= {1.6237*10^-15,1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492}

1.6237*10^-15 Seconds

Meaning Mathematica uses an entirely different operation to calculate the root of a number

Like this there are tons of elementary functions like Factorial Abs Solve Sin Cos which result in similar fast results as compared to slower human results using slower loops and iterative methods.

Where can we find a compendium of all the back code that supports these functions and makes them faster than actual procedure.

P.S. This is related only to Mathematica based functions (not theoreticalcs.SE)

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Different Timing does not mean that Mathematica uses an entirely different operation ! Functions like Sqrt are written in a compiled language (C), Mathematica is basically interpreted. You can look how it is evaluated e.g. Trace[N[Nest[(2 + x/2)/2, 1, 21], 123] ] $\endgroup$
    – Artes
    Commented May 17, 2012 at 12:16
  • 1
    $\begingroup$ Maybe because your N[] is outside as opposed to being within the Nest[], and the rational numbers that get generated become more unwieldy. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented May 17, 2012 at 12:22
  • 2
    $\begingroup$ Compare your code with FixedPoint[(# + 2/#)/2 &, N[1, 123]] // AbsoluteTiming $\endgroup$
    – J. M.'s missing motivation ♦
    Commented May 17, 2012 at 12:24
  • 2
    $\begingroup$ With the thing being closed-source, most of the built-in functions won't reveal their secrets. It is possible to tweak a few things to see the code within, but I'm not sure if the guys at Wolfram would allow that... $\endgroup$
    – J. M.'s missing motivation ♦
    Commented May 17, 2012 at 12:29
  • 2
    $\begingroup$ You may also want to look at the notes on internal implementation, specifically the section on basic arithmetic. $\endgroup$
    – Michael Wijaya
    Commented May 17, 2012 at 17:12

1 Answer 1

Reset to default
6
$\begingroup$

As suggested in the comments, having N outside of Nest is the cause of the problems. 

ListLogPlot[{
  {#, Timing[N[Nest[(# + 2/#)/2 &, 1, #], 123];][[1]]} & /@ Range[22],
  {#, Timing[Nest[N[(# + 2/#)/2, 123] &, 1, #];][[1]]} & /@ Range[22]
 },  Frame -> True, Joined -> True, PlotMarkers -> Automatic]

gives

enter image description here

I suspect the difference is that in your code, Mathematica is performing symbolic algebra before getting a numerical answer. But, moving N inside allows Mathematica to perform the same calculation with something more akin to machine numbers, even though they are not exactly machine numbers due to the extreme precision asked for.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "something more akin to machine numbers" - let's just call them "inexact numbers". :) It is instructive to replace Nest[] with NestList[] and remove the N[], just to see the digit growth in the numerators and denominators of the approximations. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented May 17, 2012 at 13:37
  • $\begingroup$ @J.M. yes, "inexact numbers" is correct, yet I wanted to highlight the fact that the speed up is really due to using something that is more like the internal machine representation than what is produced in the OP's code. $\endgroup$
    – rcollyer
    Commented May 17, 2012 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.