Re: [Chicken-users] numbers egg slow?

[Daishi Kato]

At Fri, 07 Oct 2005 01:15:57 -0500,
Alex Shinn wrote:
> 
> At Thu, 06 Oct 2005 21:56:08 +0900, Daishi Kato wrote:
> > 
> > (expt) however is slow for fixnum arithmetic.
> > I reviewed the "Bug in the numbers egg" thread again,
> > understand the background, and am seeking the solution.
> 
> It would be nice to have a faster EXPT, but since there have already
> been a number of bugs related to it we should probably start with a
> very thorough test suite before trying to improve it.

Agreed. That's why I said I'm not confident.
How would we start it?

> > and there was a bug with the case such as (%power 2 2.1).
> 
> Oops, you're right.  But that branch is never actually reached in the
> code, I shouldn't have even included it in the final %POWER
> definition.  (expt 2 2.1) works fine.

Yes, I see that. I explicitly tried (power 2 2.1).
Please remove that part from %power, if possible.

> > +(define (%fix-power base e)
> > +  (define (square x) (%* x x))
> > +  (if (negative? e)
> > +    (/ 1 (%power base (- e)))
> > +    (let lp ((res 1) (e2 e))
> > +      (cond
> > +        ((zero? e2) res)
> > +        ((%fix-expt base e2))
> > +        ((even? e2) ; recursion is faster than iteration here
> > +         (%* res (square (lp 1 (arithmetic-shift e2 -1)))))
> > +        (else
> > +         (lp (%* res base) (- e2 1)))))))
> 
> It's probably better to check the result of %FIX-EXPT once before
> entering the loop rather than on every iteration, since if it fails
> once it will always fail.

I see what you mean, but my original thought was
to even speed up bignum-expt by checking fix-expt every loop.
It really depends on how fast fix-expt is.
There should be other solutions such as writing expt in C,
but for now, I would suggest to check fix-expt out of the loop,
as Alex suggested.
Would it be possible to combine %power and %fix-power in this way?

Daishi