Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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)

share|improve this question
2  
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] ] –  Artes May 17 '12 at 12:16
1  
Maybe because your N[] is outside as opposed to being within the Nest[], and the rational numbers that get generated become more unwieldy. –  J. M. May 17 '12 at 12:22
2  
Compare your code with FixedPoint[(# + 2/#)/2 &, N[1, 123]] // AbsoluteTiming –  J. M. May 17 '12 at 12:24
2  
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... –  J. M. May 17 '12 at 12:29
2  
You may also want to look at the notes on internal implementation, specifically the section on basic arithmetic. –  Michael Wijaya May 17 '12 at 17:12
show 4 more comments

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
"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. –  J. M. May 17 '12 at 13:37
    
@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. –  rcollyer May 17 '12 at 13:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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