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)

  • 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 May 17 '12 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. is in limbo May 17 '12 at 12:22
  • 2
    $\begingroup$ Compare your code with FixedPoint[(# + 2/#)/2 &, N[1, 123]] // AbsoluteTiming $\endgroup$ – J. M. is in limbo May 17 '12 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. is in limbo May 17 '12 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 May 17 '12 at 17:12

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

  {#, 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]


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.

  • $\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. is in limbo May 17 '12 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 May 17 '12 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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