Re: Fast Cube Root Using C33

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

I need a fast cube root routine. I started with the obvious
http://metamerist.com/cbrt/cbrt.htm
What is key is getting the initial estimate using the Kahan bit hack but
that only works with IEEE floating point and not with TI floating point.
I can't believe that I am the first to do this since the C33 is
ancient. The obvious solution is to convert the TI float to the IEEE
float, apply the hack, and then convert back to TI float but there must
be a better way. Actually doing another iteration is probably faster. The problem is that sign of the mantissa is at bit 23.

Does anyboy know of a link? Thanks.

Peter Nachtwey

Does anyone here remember how to take the square root of a decimal number via "long division"? My dad taught me how when I was considerably shorter than I am now, possibly because he was appalled at his brother teaching me how to do it on a calculator using Newton's method.

For those of you under 80, it's basically a method for churning out decimals of the square root of a number in a method very akin to long division, except that at each step instead of subtracting (cumulative result) * (guess) you subtract (2 * cumulative result + guess) * (guess) -- you're basically trying to complete the equation (cumulative result + guess) ^ 2 = (cumulative result)^2 + 2 * (cumulative result)(guess) + (guess)^2.

It turns out that -- like long division -- it's really easy to do on a computer in binary because when you're only multiplying by 0 or 1 you don't have to waste a lot of time guessing.

It also turns out that if you're a _real_ math geek you can work out how to do this with cube roots, and, like square roots and division the guesswork is held to a minimum because you're just dealing with ones and zeros.

If the group shows sufficient interest I'll write it up and post it. I figured it out when I was in high school then for got it. Peter's post got me interested enough to figure it out again (thanks Peter!), but I'm not sure if it's faster than Newton's method unless you're doing the work on an FPGA.

Each step starts with you knowing the starting value - answer^3, and needing to calculate 3*answer^2 and 3*answer. You then have to subtract those two numbers from your residual to know if you emit a '1' or a '0'.

I _suspect_ that it's not as quick as Newton's method, but it's late and I'm not (by gawd) going to check!

There is in general a fundamental difference between paper-and-pencil algorithms and those run on a computer with a good divide, and usually, the computer version needs fewer steps.

With paper and pencil, one wants the next digit that is just not too large. With machinery that can divide, one wants the best approximation without regard to the number of digits produced.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
.

Relevant Pages

  • Re: Fast Cube Root Using C33
    ... that only works with IEEE floating point and not with TI floating point. ... The obvious solution is to convert the TI float to the IEEE ... float, apply the hack, and then convert back to TI float but there must ... Does anyone here remember how to take the square root of a decimal number ...
    (comp.dsp)
  • Re: Fast Cube Root Using C33
    ... that only works with IEEE floating point and not with TI floating point. ... The obvious solution is to convert the TI float to the IEEE ... float, apply the hack, and then convert back to TI float but there must ... Again, the process would be to normalize down to the range [0.125, 1), ...
    (comp.dsp)
  • Re: Fast Cube Root Using C33
    ... What is key is getting the initial estimate using the Kahan bit hack ... but that only works with IEEE floating point and not with TI floating ... Does anyone here remember how to take the square root of a decimal ... With machinery that can divide, ...
    (comp.dsp)
  • Re: Fast Cube Root Using C33
    ... that only works with IEEE floating point and not with TI floating point.. ... float, apply the hack, and then convert back to TI float but there must ... Does anyone here remember how to take the square root of a decimal number ...
    (comp.dsp)
  • Fast Cube Root Using C33
    ... What is key is getting the initial estimate using the Kahan bit hack ... but that only works with IEEE floating point and not with TI floating ... The obvious solution is to convert the TI float to the ...
    (comp.dsp)
Loading