创建快速指数函数

Question

在OCaml中，我很难找到一个更快的典型指数函数版本。以下是我要遵循的一些指导方针：

1. 与典型的expt b n ==> b * (b * (b ...)递归指数版本不同，该函数接收两个参数b和n，基本上采取分而治之的姿态。
2. 如果n是偶数，则fastexpt b n => (b ^ (n / 2))^2 else，如果n是奇数，则fastexpt b n => b * (b ^ (n - 1))

下面是我到目前为止编写的代码：

let fastexpt : int -> int -> int
= fun b n ->
    if n = 0 then 1
    else if ((n mod 2) = 0) then (expt b (n / 2)) * (expt b (n / 2)) 
    else b * (expt b (n - 1));;

我的问题是:是否有一种不使用expt函数来编写此函数的方法？

Answer 1

您在这里所做的是第一次使用divide方法，然后在计算的其余部分使用普通方法(如果考虑到您已经声明了expt)

另一件事是，如果n是奇数，你可以返回b * b^((n-1)/2) * b^((n-1)/2)，这就是快速幂运算的目的。

您应该做的只是将fastexpt定义为递归，然后一直使用它：

let rec fastexpt : int -> int -> int
= fun b n ->
    if n = 0 then 1
    else 
      let b2 = fastexpt b (n / 2) in
      if n mod 2 = 0 then b2 * b2 
      else b * b2 * b2;;