performance - 实现 (^)

Question

我正在阅读标准haskell库的(^)的实现代码:

(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0    = errorWithoutStackTrace "Negative exponent"
        | y0 == 0   = 1
        | otherwise = f x0 y0
    where -- f : x0 ^ y0 = x ^ y
          f x y | even y    = f (x * x) (y `quot` 2)
                | y == 1    = x
                | otherwise = g (x * x) ((y - 1) `quot` 2) x
          -- g : x0 ^ y0 = (x ^ y) * z
          g x y z | even y = g (x * x) (y `quot` 2) z
                  | y == 1 = x * z
                  | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)

现在定义 g 的部分对我来说似乎很奇怪，为什么不直接像这样实现它:

expo :: (Num a ,Integral b) => a -> b ->a
expo x0 y0 
    | y0 == 0 = 1
    | y0 <  0 = errorWithoutStackTrace "Negative exponent"
    | otherwise = f x0 y0
    where
      f x y | even y = f (x*x) (y `quot` 2)
              | y==1 = x
              | otherwise = x * f  x (y-1)

但实际上插入 3^1000000 显示 (^) 比 expo 快约 0.04 秒。

Why is (^) faster than expo?

Answer 1

作为编写代码的人，我可以告诉您为什么它很复杂。 :)这个想法是通过尾递归来获得循环，并且执行最少次数的乘法。我不喜欢这种复杂性，所以如果您找到更优雅的方法，请提交错误报告。