math - 如何在Erlang中计算5 ^ 262144

Question

基于THIS问题，我意识到似乎无法以常规方式计算此类数字。
有什么建议？

Answer 1

可能，但是您需要的算法比朴素的解决方案聪明一点。如果您编写了幼稚的幂函数，则可以执行以下操作:

pow(_, 0) -> 1;
pow(A, 1) -> A;
pow(A, N) -> A * pow(A, N-1).

只是展开了幂函数。但是问题是，在您的情况下，这将是262144乘法，并且数字越来越大。诀窍是一个非常简单的见解:如果将N除以2，再乘以A平方，则几乎可以得到正确的答案，除非N为奇数。因此，如果我们为奇数情况添加一个固定项，我们将获得:

-module(z).

-compile(export_all).

pow(_, 0) -> 1;
pow(A, 1) -> A;
pow(A, N) ->
    B = pow(A, N div 2),
    B * B * (case N rem 2 of 0 -> 1; 1 -> A end).

这几乎可以立即在我的机器上完成:

2> element(1, timer:tc(fun() -> z:pow(5, 262144) end)).
85568

当然，如果进行许多操作，则85ms几乎是不能接受的。但是计算这实际上是相当快的。

(如果您需要更多信息，请查看:https://en.wikipedia.org/wiki/Exponentiation_by_squaring)