如何计算Erlang中的5 ^ 262144

Question

基于这个问题,我意识到计算这些数字似乎不可能以常规方式进行.有什么建议？

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)