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 |