Wie berechnet man 5^262144 in Erlang

Question

Basierend auf THIS Frage, erkannte ich, dass die Berechnung solcher Zahlen scheint nicht möglich auf regelmäßige Weise. Irgendwelche Vorschläge?

Answer 1

Es ist möglich, aber Sie brauchen einen Algorithmus, der ein bisschen cleverer ist als die naive Lösung. Wenn Sie die naive Power-Funktion schreiben, tun Sie etwas in der Art von:

, die gerade die Power-Funktion entrollt. Aber das Problem ist, dass es in Ihrem Fall 262144 Multiplikationen mit immer größeren Zahlen sein wird. Der Trick ist eine ziemlich einfache Erkenntnis: Wenn Sie N durch 2 und Quadrat A teilen, haben Sie fast die richtige Antwort, außer wenn N ungerade ist. Wenn wir also einen Befestigungs Begriff für den ungeraden Fall addieren, so erhalten wir:

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

Diese fast sofort auf meiner Maschine ergänzt:

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

natürlich, wenn viele Operationen zu tun, 85 ms kaum akzeptabel ist. Aber das ist ziemlich schnell.

(falls Sie weitere Informationen wünschen, nehmen Sie einen Blick auf: https://en.wikipedia.org/wiki/Exponentiation_by_squaring)

Answer 2

Es einfach, da Erlang beliebige Genauigkeit für ganze Zahlen (große Zahlen) verwendet, kann man für Integer-eigene Funktion pow definieren, zum Beispiel:

-module(test). 
-export([int_pow/2]). 

int_pow(N,M)->int_pow(N,M,1). 

int_pow(_,0,R) -> R; 
int_pow(N,M,R) -> int_pow(N,M-1,R*N). 

Hinweis, habe ich nicht die Argumente prüfen und zeigte die Implementierung für Ihr Beispiel.

Answer 3

Wenn Sie daran interessiert sind, wie Rechenleistung gleichen Algorithmus wie in I GIVE CRAP ANSWERS ‚s solution aber in Schwanz rekursive Code verwendet wird, gibt es:

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