title: Implementing Root-Calculation Function
body: <p>Implementing math functions for various things is simple enough. <code>int mul(int,int);</code>, <code>int  pow(int,int);</code>, even <code>double div(float,float);</code> are easy to do and can be implemented with loops or recursion. (These are the same methods used to perform these functions by hand or in the head.) To multiply, just repeatedly add the number. To divide, repeatedly subtract it. To get the power, repeatedly multiply. And so on.</p>
  
  <p>One mathematical function that I’ve always wondered about however is roots. For example, how would you write a function to calculate the square (or cube, etc.) root of a number (ie, <code>double root(float num, float root);</code>)? I tried looking around and could not find an algorithm or method of doing this.</p>
  
  <p>When I try to calculate a root by hand, I usually use the guess method (start with an approximate number, add a fraction, multiply, see how far off it is, add a smaller fraction, multiply, check again, and repeat until satisfied). I suppose that could work, but surely there is a better—and faster—method (regardless of how much faster a computer can do it than by hand).</p>
  
  <p>Obviously LUTs are not relevant since it would have to be generic enough to take any operands (unless you are writing a game with a finite set of data). The <a href="http://en.wikipedia.org/wiki/Methods_of_computing_square_roots" rel="nofollow">Wikipedia article</a> mentions the guess method and lists some ancient ones (from long before computers were invented) as well as some pure math and even calculus methods (including some that have “infinity” as a component). The only ones that seem to have anything to do with electronics use tricks or logirithms. (And that’s just for <em>square-roots</em>, let alone cube-roots, and such.)</p>
  
  <p>Is there no easy root calculation method? How do calculators do it? How do computers do it? (No, simply doing <code>double pow(a,0.5);</code> won’t work because then how would <code>double pow(float,float)</code> be implemented?)</p>
  
  <p>Am I just incorrectly grouping root functions with simpler functions? Are they more complex than they seem?</p>