How to calculate 5^262144 in Erlang

Question

Based on THIS question, I realized that calculating such numbers seems not possible in regular ways. Any suggestions?

Answer 1

It is possible, but you need an algorithm that is a bit more clever than the naive solution. If you write the naive power function, you do something along the lines of:

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

which just unrolls the power function. But the problem is that in your case, that will be 262144 multiplications, on increasingly larger numbers. The trick is a pretty simple insight: if you divide N by 2, and square A, you almost have the right answer, except if N is odd. So if we add a fixing term for the odd case, we obtain:

-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).

This completes almost instantly on my machine:

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

of course, if doing many operations, 85ms is hardly acceptable. But computing this is actually rather fast.

(if you want more information, take a look at: https://en.wikipedia.org/wiki/Exponentiation_by_squaring )

Answer 2

If you are interested how compute power using same algorithm as in I GIVE CRAP ANSWERS's solution but in tail recursive code, there it is:

power(X, 0) when is_integer(X) -> 1;
power(X, Y) when is_integer(X), is_integer(Y), Y > 0 ->
    Bits = bits(Y, []),
    power(X, Bits, X).

power(_, [], Acc) -> Acc;
power(X, [0|Bits], Acc) -> power(X, Bits, Acc*Acc);
power(X, [1|Bits], Acc) -> power(X, Bits, Acc*Acc*X).

bits(1, Acc) -> Acc;
bits(Y, Acc) ->
    bits(Y div 2, [Y rem 2 | Acc]).