Jacobi symbol: Difference between revisions
Content added Content deleted
(Adding Haskell version) |
Catskill549 (talk | contribs) |
||
Line 14: | Line 14: | ||
=={{header|AWK}}== |
|||
<lang AWK> |
|||
# syntax: GAWK -f JACOBI_SYMBOL.AWK |
|||
# converted from Go |
|||
BEGIN { |
|||
max_n = 29 |
|||
max_a = max_n + 1 |
|||
printf("n\\a") |
|||
for (i=1; i<=max_a; i++) { |
|||
printf("%3d",i) |
|||
underline = underline " --" |
|||
} |
|||
printf("\n---%s\n",underline) |
|||
for (n=1; n<=max_n; n+=2) { |
|||
printf("%3d",n) |
|||
for (a=1; a<=max_a; a++) { |
|||
printf("%3d",jacobi(a,n)) |
|||
} |
|||
printf("\n") |
|||
} |
|||
exit(0) |
|||
} |
|||
function jacobi(a,n, result,tmp) { |
|||
if (n%2 == 0) { |
|||
print("error: 'n' must be a positive odd integer") |
|||
exit |
|||
} |
|||
a %= n |
|||
result = 1 |
|||
while (a != 0) { |
|||
while (a%2 == 0) { |
|||
a /= 2 |
|||
if (n%8 == 3 || n%8 == 5) { |
|||
result = -result |
|||
} |
|||
} |
|||
tmp = a |
|||
a = n |
|||
n = tmp |
|||
if (a%4 == 3 && n%4 == 3) { |
|||
result = -result |
|||
} |
|||
a %= n |
|||
} |
|||
if (n == 1) { |
|||
return(result) |
|||
} |
|||
return(0) |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
n\a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|||
--- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- |
|||
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
|||
3 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 |
|||
5 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 |
|||
7 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 |
|||
9 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 |
|||
11 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1 1 1 -1 -1 -1 |
|||
13 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1 1 1 |
|||
15 1 1 0 1 0 0 -1 1 0 0 -1 0 -1 -1 0 1 1 0 1 0 0 -1 1 0 0 -1 0 -1 -1 0 |
|||
17 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 |
|||
19 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 0 1 -1 -1 1 1 1 1 -1 1 -1 1 |
|||
21 1 -1 0 1 1 0 0 -1 0 -1 -1 0 -1 0 0 1 1 0 -1 1 0 1 -1 0 1 1 0 0 -1 0 |
|||
23 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 -1 -1 -1 0 1 1 1 1 -1 1 -1 |
|||
25 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 |
|||
27 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 |
|||
29 1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 1 0 1 |
|||
</pre> |
|||
=={{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]. |