The (^) operator sometimes uses one (*) more than needed.
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"
Trac metadata
Trac field | Value |
---|---|
Version | 6.8.2 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Prelude |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | lennart.augustsson@credit-suisse.com |
Operating system | Unknown |
Architecture | Unknown |