Re: Fast Cube Root Using C33

On Fri, 27 Feb 2009 08:18:49 -0600, Vladimir Vassilevsky wrote:

Tim Wescott wrote:

On Thu, 26 Feb 2009 19:04:01 -0800, pnachtwey wrote:


I need a fast cube root routine.

[...]



Does anyone here remember how to take the square root of a decimal
number via "long division"?

[...]

That algorithm computes one bit per iteration. Simple, but very slow.
Newton-Raphson efficiently doubles the number of known bits at each
step.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant http://www.abvolt.com

I just checked a simple N-R algorithm for both square root and cube root.

For square roots, N-R delivered a factor of 2.4 precision (so slightly
more than one bit) per iteration -- not a doubling. For cubes, it's a
factor of 1.8 or so -- so less than one bit per iteration.

That's not to say that my algorithm doesn't take longer, because there's
considerably more math per iteration for a crummy third of a bit more per
iteration or whatever I'm achieving.

--
http://www.wescottdesign.com
.

Relevant Pages

  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Iterative subspace decomposition
    ... Subspace Tracking," IEEE Transactions on Signal Processing, vol. 43, ... the PASTd algorithm does not produce orthogonal ... it is not producing the eigendecomposition I ...
    (sci.math.num-analysis)
  • Re: OO Style with Ada Containers
    ... The most important part of STL is the notion of range-based iteration. ... Every single algorithm that iterates over something gets a pair of ... But there's nothing that precludes that in Ada: ... procedure Generic_Algorithm (First, Back: Cursor); ...
    (comp.lang.ada)
  • Re: smallest disk covering a set of points
    ... If there is a 4th point outside the second circle on ... iteration" when an algorithm is found to fail more often fails ... my intuition tells me that it will converge to ...
    (comp.programming)
  • Re: rapidly converging rational sqrt
    ... Note that after iteration 6 we have ... > more than 100 significant digits. ... I don't wish to denigrate your algorithm unduly, but square root algorithms ...
    (sci.math.research)