Anonymous user
Talk:Miller–Rabin primality test: Difference between revisions
no edit summary
m (→Erlang) |
No edit summary |
||
Line 18:
== Erlang ==
Miller-Rabin primality test in Erlang uses a floating point power function and truncation to restore to integer.
This combination begins to fall short when the integer being tested is up to approximately 90,000,000. At these
large sizes, the primes found are correct but too many correct primes are not found. The following modifications
are helpful: an integer power function, power/2, will replace floating point power function, math:pow/2; in function
mr_series/4 math:pow/2 is replaced by power:power/2; in function pow_mod/3, the same replacement is made
and truncations are eliminated, also the expression E/2 is replaced by E div 2.
-module(power).
-export([power/2]).
power(X, N) ->▼
▲power(X, N) ->
power(X, N, 1).
power(X, N, Acc) ->
if
N /= 0 -> power(X, N - 1, X * Acc);
Line 32 ⟶ 36:
end.
mr_series(N, A, D, S) when N rem 2 == 1 ->▼
▲mr_series(N, A, D, S) when N rem 2 == 1 ->
Js = lists:seq(0, S),
lists:map(fun(J) -> pow_mod(A, power:power(2, J)*D, N) end, Js).
pow_mod(B, E, M) ->▼
▲pow_mod(B, E, M) ->
case E of
0 -> 1;
Line 52 ⟶ 50:
end.
== Tcl ==
| |||