Exponentiation modulo n

erlang

Here is a repeated square and multiply implementation for exponentiation modulo n written in Erlang.

power(Base, 0, Modul) -> 1;
power(Base, 1, Modul) -> Base rem Modul;
power(Base, 2, Modul) -> (Base*Base) rem Modul;
power(Base, 3, Modul) -> (power(Base, 2, Modul) * Base) rem Modul;
power(Base, Exp, Modul) when (Exp rem 2 == 0) ->
    X = power(Base, Exp div 2, Modul),
    (X*X) rem Modul;
power(Base, Exp, Modul) ->
    X = power(Base, (Exp-1) div 2, Modul),
    (((X*X) rem Modul) * Base) rem Modul.

The function computes Base^Exp mod Modul. Have fun with it!


Erlang native code – Benchmark

erlang

Normalerweise compiliert Erlang Bytecode (heißt das so in Erlang?). Das coole daran ist, dass man die beam files leicht auf anderen Rechnern benutzen kann. Aber die Geschwindigkeit von diesem Code hat mich nicht überzeugen können. Darum habe ich ausprobiert wie gut der native Code ist den Erlang baut.

Der Versuchsaufbau ist einfach: Ich habe eine simple rekursive Funktion geschrieben, die Fibonaccizahlen berechnet. Dann wir 5-mal Fibonacci von 40 berechnet und die Zeit gemessen. Das ganze mache ich mit nur einem Kern. Diesen Test mache ich insgesamt 3-mal. Einmal mit nativem Erlangcode, einmal mit nicht nativem Erlangcode und einmal mit einem in C geschriebenen Programm. Der Benchmark besteht aus drei Dateien:

cpu_intensive.erl:

-module(cpu_intensive).
-compile(export_all).

fib_test() ->
 fib(40), fib(40), fib(40), fib(40), fib(40).

fib(0) -> 1;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

cpu_intensive.c

unsigned int fib(unsigned int n) {
 if (n == 0 || n == 1) {
 return 1;
 }
 return fib(n-1) + fib(n-2);
}

int main() {
 fib(40); fib(40); fib(40); fib(40); fib(40);
 return 0;
}

Makefile:

all: native normal c

native:
 @erlc +native cpu_intensive.erl
 @echo ""
 @echo "Fibonacci Erlang native code"
 @time erl -noshell -s cpu_intensive fib_test -s erlang halt

normal:
 @erlc cpu_intensive.erl
 @echo ""
 @echo "Fibonacci Erlang non-native code"
 @time erl -noshell -s cpu_intensive fib_test -s erlang halt

c:
 @gcc -O0 -o cpu_intensive cpu_intensive.c
 @echo ""
 @echo "Fibonacci written in C without optimizations"
 @time ./cpu_intensive

Ich habe obige drei Dateien angelegt und die Makefile ausgeführt. Das Ergebnis war bei meinem Core 2 Duo 8400

Fibonacci Erlang native code
 13,99 real        13,00 user         0,95 sys

Fibonacci Erlang non-native code
 116,81 real       115,46 user         1,00 sys

Fibonacci written in C without optimizations
 11,14 real        11,10 user         0,00 sys

Man sieht sehr schön, dass der native Erlangcode fast genauso schnell ist wie nicht optimierter C-Code. Ausserdem sieht man, dass der nicht native Erlangcode hier etwa die zehnfache Zeit braucht.

Fazit: Der native Erlangcode ist super wuschig und ich frage mich warum das +native Flag nicht in der Manpage von erlc dokumentiert ist.


Follow

Bekomme jeden neuen Artikel in deinen Posteingang.