#2306: The (^) operator sometimes uses one (*) more than needed.
------------------------+---------------------------------------------------
Reporter: guest | Owner:
Type: bug | Status: new
Priority: normal | Component: Prelude
Version: 6.8.2 | Severity: minor
Keywords: | Testcase:
Architecture: Unknown | Os: Unknown
------------------------+---------------------------------------------------
The implementation of integer exponentiation is suboptimal.
By inserting a trace in (*) you can easily observe that, e.g., exponent 4
uses 3 multiplications instead of 2.
Here's a different version:
{{{
(^) :: (Num a, Integral b) => a -> b -> a
_ ^ 0 = 1
x ^ n | n > 0 = g x n
where g b i | even i = g (b*b) (i `quot` 2)
| otherwise = f b (i-1) b
f _ 0 y = y
f a d y | even d = f (a*a) (d `quot` 2) y
| otherwise = f a (d-1) (a * y)
_ ^ _ = error "Prelude.^: negative exponent"
}}}
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2306>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
