Prev: Kaiser window vs Kaiser-Bessel window
Next: G726 codec support with .wav files
From: Clay on 2 Feb 2010 12:47
On Feb 2, 12:44 pm, Greg Berchin <gberc...(a)comicast.net.invalid>
wrote:
> On Mon, 1 Feb 2010 14:11:04 -0800 (PST), Clay <c...(a)claysturner.com> wrote:
> >This will let you compute the radix 2 logarithm to an precise number
> >of bits.
>
> I have been using a similar, exact iterative algorithm for decades, except mine
> uses two lookup tables, each with as many entries as the required number bits of
> precision.  Lookup tables aren't nearly as elegant as squaring-and-comparing,
> but the same tables can also be used to compute the inverse logarithm.  I'm not
> sure, but I suspect that your square-and-compare method might turn into a
> square-root-and-compare for the inverse log.
>
> Greg

Actually the inverse log is square and mult! That was the one I
learned back during the 1970s and from there I developed the log algo.

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

>Actually the inverse log is square and mult! That was the one I
>learned back during the 1970s and from there I developed the log algo.

Very interesting.

Would you be so kind as to post that, too?

Thanks,
Greg
From: Clay on 2 Feb 2010 13:16
On Feb 2, 12:50 pm, Greg Berchin <gberc...(a)comicast.net.invalid>
wrote:
> On Tue, 2 Feb 2010 09:47:41 -0800 (PST), Clay <c...(a)claysturner.com> wrote:
> >Actually the inverse log is square and mult! That was the one I
> >learned back during the 1970s and from there I developed the log algo.
>
> Very interesting.
>
> Would you be so kind as to post that, too?
>
> Thanks,
> Greg

Greg,

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. The
original routine I saw of course used incredibly large exponents
(thousands of digits). And they we doing modular exponentiation, so
after each squaring and multiplying a modular reduction was performed.
Also for finding the nth roots, you can embed the log routine into the
exponential one.

I recall when I did an introductory computer programming class in
college we were to write a program to calculate amortizations of home
loans. So I used this routine to find the I^360 power which is needed
in the monthly payment formula. The prof had never seen such a short
cut. He expected us to do repeated multiplication - 360 times. We
weren't allowed to use transcendental functions in the program. I
ended up with around 14 multiplies vs 360.

Clay


// 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;
}
From: Manny on 2 Feb 2010 13:45
On Feb 2, 6:16 pm, Clay <c...(a)claysturner.com> wrote:
> On Feb 2, 12:50 pm, Greg Berchin <gberc...(a)comicast.net.invalid>
> wrote:
>
> > On Tue, 2 Feb 2010 09:47:41 -0800 (PST), Clay <c...(a)claysturner.com> wrote:
> > >Actually the inverse log is square and mult! That was the one I
> > >learned back during the 1970s and from there I developed the log algo.
>
> > Very interesting.
>
> > Would you be so kind as to post that, too?
>
> > Thanks,
> > Greg
>
> Greg,
>
> 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. The
> original routine I saw of course used incredibly large exponents
> (thousands of digits). And they we doing modular exponentiation, so
> after each squaring and multiplying a modular reduction was performed.
> Also for finding the nth roots, you can embed the log routine into the
> exponential one.
>
> I recall when I did an introductory computer programming class in
> college we were to write a program to calculate amortizations of home
> loans. So I used this routine to find the I^360 power which is needed
> in the monthly payment formula. The prof had never seen such a short
> cut. He expected us to do repeated multiplication - 360 times. We
> weren't allowed to use transcendental functions in the program. I
> ended up with around 14 multiplies vs 360.
>
> Clay
>
> // 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;
>
> }

Equally neat! Thanks.

-Momo
From: Greg Berchin on 2 Feb 2010 14:05
On Tue, 2 Feb 2010 10:16:31 -0800 (PST), Clay <clay(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
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Kaiser window vs Kaiser-Bessel window
Next: G726 codec support with .wav files