From: Clay on
On Feb 2, 2:05 pm, Greg Berchin <gberc...(a)comicast.net.invalid> wrote:
> On Tue, 2 Feb 2010 10:16:31 -0800 (PST), Clay <c...(a)claysturner.com> wrote:
> >This implements a simple y^x where x is an integer. If you want
> >fractional powers, then find the nth root of the radix and move the
> >binary point over in the exponent so it ends up be an integer.
>
> That's beautiful.  Wish I'd thought of it.
>
> My technique does the same thing as yours; yours is just implemented more
> cleverly.
>
> Greg

I suspect these algos go bact to the early 1960s. If I recall
correctly that's when the CORDIC stuff was done and these algos have a
lot in common with them. Maybe I'll do a literature search and see
what I can find on them.

Clay
From: Greg Berchin on
On Tue, 2 Feb 2010 11:09:30 -0800 (PST), Clay <clay(a)claysturner.com> wrote:

>I suspect these algos go bact to the early 1960s. If I recall
>correctly that's when the CORDIC stuff was done and these algos have a
>lot in common with them. Maybe I'll do a literature search and see
>what I can find on them.

There is nothing new under the sun. I can only take solace in knowing that I
(re)invented the algorithm myself, without knowing about the previous work.
From: Clay on
On Feb 2, 2:12 pm, Greg Berchin <gberc...(a)comicast.net.invalid> wrote:
> On Tue, 2 Feb 2010 11:09:30 -0800 (PST), Clay <c...(a)claysturner.com> wrote:
> >I suspect these algos go bact to the early 1960s. If I recall
> >correctly that's when the CORDIC stuff was done and these algos have a
> >lot in common with them. Maybe I'll do a literature search and see
> >what I can find on them.
>
> There is nothing new under the sun.  I can only take solace in knowing that I
> (re)invented the algorithm myself, without knowing about the previous work.

I did a little searching. The CORDIC technique is due to Volder in
1959. He didn't explicitly describe logs and exps.

The fast y2x algo dates back to al Kashi in the 15th century.

Clay
From: Randy Yates on
Clay <clay(a)claysturner.com> writes:
> [...]
> // This algo implements a simple y^x where x is an integer.
> // Here PRECISION needs to be big enough to cover all of the "1" bits
> in the exponent.
> double Y2X(double radix, int x)
> {
> double y=1.0;
> int i,mask;
>
> mask=1<<PRECISION-1;
>
> for (i=0;i<PRECISION;i++) {
> y=y*y;
> if (x&mask)
> y*=radix;
> mask>>=1;
> }
> return y;
> }

Wow, now that is tricky!

I had to write this up and try it out to see what was actually going
on. Now I see it's in how you factor the exponent, and taking advantage
of base 2 representation. I learnt sumtin'!
--
Randy Yates % "The dreamer, the unwoken fool -
Digital Signal Labs % in dreams, no pain will kiss the brow..."
mailto://yates(a)ieee.org %
http://www.digitalsignallabs.com % 'Eldorado Overture', *Eldorado*, ELO
From: Manny on
On Feb 3, 12:40 am, Randy Yates <ya...(a)ieee.org> wrote:
> Clay <c...(a)claysturner.com> writes:
> > [...]
> > // This algo implements a simple y^x where x is an integer.
> > // Here PRECISION needs to be big enough to cover all of the "1" bits
> > in the exponent.
> > double Y2X(double radix, int x)
> > {
> > double y=1.0;
> > int i,mask;
>
> > mask=1<<PRECISION-1;
>
> > for (i=0;i<PRECISION;i++) {
> >    y=y*y;
> >    if (x&mask)
> >            y*=radix;
> >    mask>>=1;
> >    }
> > return y;
> > }
>
> Wow, now that is tricky!
>
> I had to write this up and try it out to see what was actually going
> on. Now I see it's in how you factor the exponent, and taking advantage
> of base 2 representation. I learnt sumtin'!
> --
> Randy Yates                      % "The dreamer, the unwoken fool -
> Digital Signal Labs              %  in dreams, no pain will kiss the brow..."
> mailto://ya...(a)ieee.org          %  http://www.digitalsignallabs.com% 'Eldorado Overture', *Eldorado*, ELO

Pretty cool all in all! And it's so cool that I promise - when I can
find time of course - to benchmark this against Xilinx's AccelDSP
cores which are supposedly as efficient as it gets. We can also cheat
a bit and input an algorithmic description of this and see what the
tools would readily spit out. Will report back on this though no way
before end of Feb.

-Momo