Jacobi symbol: Difference between revisions
Content added Content deleted
(→{{header|Python}}: Check if n is valid) |
|||
Line 86: | Line 86: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
The <code>jacobi</code> word already exists in the <code>math.extras</code> vocabulary. See the implementation [https://docs.factorcode.org/content/word-jacobi%2Cmath.extras.html here]. |
The <code>jacobi</code> word already exists in the <code>math.extras</code> vocabulary. See the implementation [https://docs.factorcode.org/content/word-jacobi%2Cmath.extras.html here]. |
||
=={{header|Erlang}}== |
|||
jacobi(_, N) when N < 0 -> 0; |
|||
jacobi(_, N) when (N band 1) =:= 0 -> 0; % N is even |
|||
jacobi(A, N) when A < 0 -> |
|||
J2 = ja(-A, N), |
|||
case N band 3 of |
|||
1 -> J2; |
|||
3 -> -J2 |
|||
end; |
|||
jacobi(A, N) -> ja(A, N). |
|||
ja(0, _) -> 0; |
|||
ja(1, _) -> 1; |
|||
ja(A, N) when A >= N -> ja(A rem N, N); |
|||
ja(A, N) when (A band 1) =:= 0 -> % A is even |
|||
J2 = ja(A bsr 1, N), |
|||
case N band 7 of |
|||
1 -> J2; |
|||
3 -> -J2; |
|||
5 -> -J2; |
|||
7 -> J2 |
|||
end; |
|||
ja(A, N) -> % if we get here, A is odd, so we can flip it. |
|||
J2 = ja(N, A), |
|||
case (A band 3 =:= 3) and (N band 3 =:= 3) of |
|||
true -> -J2; |
|||
false -> J2 |
|||
end. |
|||
</lang> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
Line 180: | Line 210: | ||
17 0 1 1 -1 1 -1 -1 -1 1 1 |
17 0 1 1 -1 1 -1 -1 -1 1 1 |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |