[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] numbers egg slow?
From: |
Daishi Kato |
Subject: |
Re: [Chicken-users] numbers egg slow? |
Date: |
Wed, 12 Oct 2005 14:35:29 +0900 |
User-agent: |
Wanderlust/2.15.1 (Almost Unreal) Emacs/21.4 Mule/5.0 (SAKAKI) |
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