创建快速指数函数

我在查找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功能？

来源

2017-10-15 Sean

使用'fastexpt'呢？ –

也许我不太了解OCaml语言，但是如果我要包含紧固插件，那么我不必将紧密插件的初始定义定义为“let rec”吗？ – Sean

@Sean，来自https://stackoverflow.com/help/how-to-ask： **发布问题并回复反馈发布后，将问题留在浏览器中打开一段时间，然后查看如果有人评论。如果您错过了一条明显的信息，请准备好通过编辑您的问题进行回复以包含它。如果有人发布答案，请准备好尝试并提供反馈！** 当您提问时，请接受答案并回答评论或答案。你所有的问题都没有被接受的答案，这很奇怪。不要粗鲁，人们在这里帮忙，不要离开和沟通。 – Lhooq

你在做什么在这里使用分而治之法的第一次，然后用正常的一个用于计算的其余部分（如果我们认为您已经声明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;;

来源

2017-10-15 09:27:13 Lhooq

如果你想要快速指数，你可以尝试避免'mod'和division，因为它们是CPU上的慢速指令。相反，您可以使用位移运算进行2的幂整数除法，并使用位操作来测试数字的奇偶性：如果第1位设置为零，则数字为偶数。但是，OCaml编译器可能已经做了这些优化，但值得尝试。 –

是的，谢谢你，我实际上是从算法的角度回答，但你的观点值得注意。 ;-) – Lhooq

@AnthonyScemama编译器执行这些优化。如果你想要最优化，可能会有黑暗的魔法，以确保你的整数在计算过程中保持无箱状态（虽然我不确定它是否可以手动操作）。 – PatJ

创建快速指数函数

回答

相关问题