创建快速指数函数

Question

我无法在 OCaml 中找到典型指数函数的更快版本。以下是我试图遵循的一些准则：

与 expt b n ==> b * (b * (b ...) 的典型递归指数版本不同，此函数接收两个参数 b 和 n，基本上采取分而治之的立场。
如果 n 是偶数，则 fastexpt b n => (b ^ (n / 2))^2 否则如果 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

你在这里做的是第一次使用分而治之的方法，然后在剩下的计算中使用正常的方法（如果我们认为你已经声明 expt）

还有就是如果n是奇数，可以returnb * 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;;

创建快速指数函数

Creating a Fast Exponent Function

algorithm

ocaml

exponent

divide-and-conquer