Rosetta Code

Jacobi symbol: Difference between revisions

Page Discussion

Jacobi symbol (view source)

Revision as of 08:56, 7 April 2024

13,160 bytes added ,  1 month ago
m
→‎{{header|11l}}: X.throw
m (syntax highlighting fixup automation)
 
(13 intermediate revisions by 6 users not shown)
Line 18:
<syntaxhighlight lang="11l">F jacobi(=a, =n)
I n <= 0
X.throw ValueError(‘'n' must be a positive integer.’)
I n % 2 == 0
X.throw ValueError(‘'n' must be odd.’)
a %= n
V result = 1
Line 162:
37│ 0 1 -1 -1 1 -1 1 1 -1 1 1
39│ 0 1 1 0 1 1 0 1 1 0 1
</pre>
 
=={{header|ALGOL 68}}==
{{Trans|Wren}}
<syntaxhighlight lang="algol68">
BEGIN # Jacobi symbol - translation of the Wren sample #
 
PROC jacobi = ( INT a in, n in )INT:
IF n in <= 0 OR NOT ODD n in THEN
print( ( "The 'n' parameter of jacobi must be an odd positive integer.", newline ) );
stop
ELSE
INT a := a in MOD n in, n := n in;
INT result := 1;
WHILE a /= 0 DO
WHILE NOT ODD a DO
a OVERAB 2;
INT nm8 = n MOD 8;
IF nm8 = 3 OR nm8 = 5 THEN result := - result FI
OD;
INT t = a;
a := n;
n := t;
IF a MOD 4 = 3 AND n MOD 4 = 3 THEN result := - result FI;
a MODAB n
OD;
IF n = 1 THEN result ELSE 0 FI
FI # jacobi # ;
 
print( ( "Table of jacobi(a, n):", newline ) );
print( ( "n/a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15", newline ) );
print( ( "---------------------------------------------------------------", newline ) );
FOR n BY 2 TO 29 DO
print( ( whole( n, -3 ) ) );
FOR a TO 15 DO print( ( whole( jacobi( a, n ), -4 ) ) ) OD;
print( ( newline ) )
OD
 
END
</syntaxhighlight>
{{out}}
<pre>
Table of jacobi(a, n):
n/a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------
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
5 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
9 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
13 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1
15 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
19 1 -1 -1 1 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
23 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1
25 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
29 1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1
</pre>
 
=={{header|ALGOL W}}==
{{Trans|Wren}}
<syntaxhighlight lang="algolw">
begin % Jacobi symbol %
 
integer procedure jacobi( integer value aIn, nIn ) ;
if nIn <= 0 or not odd( nIn ) then begin
write( "The 'n' parameter of jacobi must be an odd positive integer." );
0
end
else begin
integer a, n, js;
a := aIn rem nIn; n := nIn; js := 1;
while a not = 0 do begin
while a rem 2 = 0 do begin
integer nm8;
a := a div 2;
nm8 := n rem 8;
if nm8 = 3 or nm8 = 5 then js := - js;
end while_a_rem_2_eq_0 ;
begin integer t; t := a; a := n; n := t end;
if a rem 4 = 3 and n rem 4 = 3 then js := - js;
a := a rem n
end;
if n = 1 then js else 0
end jacobi ;
 
write( "Table of jacobi(a, n):" );;
write( "n/a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15" );
write( "---------------------------------------------------------------" );
for n := 1 step 2 until 29 do begin
write( i_w := 3, s_w := 0, n );
for a := 1 until 15 do writeon( i_w := 4, s_w := 0, jacobi( a, n ) );
end
 
end.
</syntaxhighlight>
{{out}}
<pre>
Table of jacobi(a, n):
n/a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------
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
5 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
9 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
13 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1
15 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
19 1 -1 -1 1 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
23 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1
25 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
29 1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1
</pre>
 
Line 211 ⟶ 330:
17 | 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1 -1
19 | 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 0 1
21 | 1 -1 0 1 1 0 0 -1 0 -1 -1 0 -1 0 0 1 1 0 -1 1</pre>
</pre>
 
=={{header|AutoHotkey}}==
Line 539 ⟶ 659:
</syntaxhighlight>
{{out}}
<pre style="font-size: 12px">
<pre>
n\m 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
----------------------------------------------------------------------------------------------------------------------
Line 609 ⟶ 729:
next pn</syntaxhighlight>
{{out}}
<pre style="font-size: 11px"> k 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 31 32 33 34 35 36
n
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 1 -1 0 1 -1 0
Line 940 ⟶ 1,060:
</syntaxhighlight>
{{out}}
<pre style="font-size: 13px">
<pre>
n\k 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
Line 1,078 ⟶ 1,198:
return if (n == 1) result else 0
}</syntaxhighlight>
 
=={{header|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
do -- Jacobi symbol - translation of the Algol 68 sample
 
 
local function jacobi( aIn, nIn )
if nIn <= 0 or nIn % 2 == 0 then
print( "The 'n' parameter of jacobi must be an odd positive integer." )
return 0
else
local a, n, result = aIn % nIn, nIn, 1
while a ~= 0 do
while a % 2 == 0 do
a = math.floor( a / 2 )
local nm8 = n % 8
if nm8 == 3 or nm8 == 5 then result = - result end
end
a, n = n, a;
if a % 4 == 3 and n % 4 == 3 then result = - result end
a = a % n
end
return n == 1 and result or 0
end
end
 
print( "Table of jacobi(a, n):" );
print( "n/a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15" )
print( "---------------------------------------------------------------" )
for n = 1, 29, 2 do
io.write( string.format( "%3d", n ) )
for a = 1, 15 do io.write( string.format( "%4d", jacobi( a, n ) ) ) end
io.write( "\n" )
end
 
end
</syntaxhighlight>
{{out}}
<pre>
Table of jacobi(a, n):
n/a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------
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
5 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
9 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
13 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1
15 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
19 1 -1 -1 1 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
23 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1
25 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
29 1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1
</pre>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Line 1,174 ⟶ 1,353:
}</syntaxhighlight>
{{out}}
<pre style="font-size: 13px">n\k 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
Line 1,240 ⟶ 1,419:
29 0 1 -1 -1 1 1 1 1 -1 1 -1 -1
31 0 1 1 -1 1 1 -1 1 1 1 1 -1
</pre>
 
=={{header|PL/M}}==
{{Trans|Wren}}...via Algol W.
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
Note that although the 8080 PL/M compiler only supports unsigned integers, the unary minus operator produces a correct two's complement result, so for byte values, -1 = 255 and -255 = 1.
<syntaxhighlight lang="plm">
100H: /* JACOBI SYMBOL */
 
/* CP/M BDOS SYSTEM CALLS AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$STRING( .( 0DH, 0AH, '$' ) ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
 
/* TASK */
 
JACOBI: PROCEDURE( A$IN, N$IN )BYTE;
DECLARE ( A$IN, N$IN ) ADDRESS;
IF N$IN MOD 2 <> 1 THEN DO;
CALL PR$STRING( .'JACOBI PARAMETER NOT ODD$' );
RETURN 0;
END;
ELSE DO;
DECLARE ( A, N, NM8, T ) ADDRESS;
DECLARE JS BYTE;
A = A$IN MOD N$IN; N = N$IN; JS = 1;
DO WHILE A <> 0;
DO WHILE A MOD 2 = 0;
A = A / 2;
NM8 = N MOD 8;
IF NM8 = 3 OR NM8 = 5 THEN JS = - JS;
END;
T = A; A = N; N = T;
IF A MOD 4 = 3 AND N MOD 4 = 3 THEN JS = - JS;
A = A MOD N;
END;
IF N = 1 THEN RETURN JS;
ELSE RETURN 0;
END;
END JACOBI ;
 
DECLARE ( A, N )ADDRESS;
DECLARE JS BYTE;
 
CALL PR$STRING( .'TABLE OF JACOBI(A, N):$' );CALL PR$NL;
CALL PR$STRING( .'N/A 1 2 3 4 5 6 7$' );
CALL PR$STRING( .' 8 9 10 11 12 13 14 15$' );CALL PR$NL;
CALL PR$STRING( .'-------------------------------$' );
CALL PR$STRING( .'--------------------------------$' );CALL PR$NL;
DO N = 1 TO 29 BY 2;
CALL PR$CHAR( ' ' );
IF N < 10 THEN CALL PR$CHAR( ' ' );
CALL PR$NUMBER( N );
DO A = 1 TO 15;
JS = JACOBI( A, N );
IF JS = 0 THEN CALL PR$STRING( .' 0$' );
ELSE IF JS = 1 THEN CALL PR$STRING( .' 1$' );
ELSE CALL PR$STRING( .' -1$' );
END;
CALL PR$NL;
END;
 
EOF
</syntaxhighlight>
{{out}}
<pre>
TABLE OF JACOBI(A, N):
N/A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
---------------------------------------------------------------
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
5 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
9 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
13 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1
15 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
19 1 -1 -1 1 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
23 1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1
25 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
29 1 -1 -1 1 1 1 1 -1 1 -1 -1 -1 1 -1 -1
</pre>
 
Line 1,300 ⟶ 1,576:
}</syntaxhighlight>
{{out}}
<pre style="font-size: 13px">n\k 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
Line 1,647 ⟶ 1,923:
Also built-in as '''kronecker(n,k)'''.
 
<syntaxhighlight lang="ruby">func jacobi(na, kn) {
 
assert(kn > 0, "#{kn} must be positive")
assert(kn.is_odd, "#{kn} must be odd")
 
var t = 1
while (na %= kn) {
varif v = n(a.valuation(2is_even) {
t *= (-1)**v if (k%8var ~~v [3,5]= a.valuation(2)
n >> t *= (-1)**v if (n%8 ~~ [3,5])
(n,k) a >>= (k,n)v
t = -t if ([n%4, k%4] == [3,3])}
(a,n) = (n,a)
t = -t if ([a%4, n%4] == [3,3])
}
 
kn==1 ? t : 0
}
 
for na in (0..50), kn in (0..50) {
assert_eq(jacobi(na, 2*kn + 1), kronecker(na, 2*kn + 1))
}</syntaxhighlight>
 
Line 1,725 ⟶ 2,003:
17 0 1 1 -1 1 -1 -1 -1 1 1</pre>
 
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">fn jacobi(aa u64, na u64) ?int {
mut a := aa
mut n := na
Line 1,787 ⟶ 2,065:
{{trans|Python}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var jacobi = Fn.new { |a, n|
Line 1,815 ⟶ 2,093:
var n = 1
while (n < 31) {
SystemFmt.write(Fmt.d(3"$3d", n))
for (a in 1..15) SystemFmt.write(Fmt.d(4"$4d", jacobi.call(a, n)))
System.print()
n = n + 2
Line 1,841 ⟶ 2,119:
27 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
</pre>
 
=={{header|XPL0}}==
{{trans|C}}
<syntaxhighlight lang "XPL0">func Jacobi(A, N);
int A, N, Result, T;
[if A >= N then A:= rem(A/N);
Result:= 1;
while A do
[while (A&1) = 0 do
[A:= A >> 1;
if (N&7) = 3 or (N&7) = 5 then Result:= -Result;
];
T:= A; A:= N; N:= T;
if (A&3) = 3 and (N&3) = 3 then Result:= -Result;
A:= rem(A/N);
];
if N = 1 then return Result;
return 0;
];
 
proc PrintTable(KMax, NMax);
int KMax, NMax, K, N;
[Text(0, "N\K|");
Format(3, 0);
for K:= 0 to KMax do RlOut(0, float(K));
CrLf(0);
Text(0, "----");
for K:= 0 to KMax do Text(0, "---");
CrLf(0);
for N:= 1 to NMax do
[Format(2, 0);
RlOut(0, float(N));
Text(0, " |");
Format(3, 0);
for K:= 0 to KMax do
RlOut(0, float(Jacobi(K, N)));
CrLf(0);
N:= N+1;
];
];
 
PrintTable(20, 21);
</syntaxhighlight>
{{out}}
<pre>
N\K| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3 | 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1
5 | 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0 1 -1 -1 1 0
7 | 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1 0 1 1 -1 1 -1 -1
9 | 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
11 | 0 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -1 1 1 1 -1 -1 -1 1
13 | 0 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 0 1 -1 1 1 -1 -1 -1
15 | 0 1 1 0 1 0 0 -1 1 0 0 -1 0 -1 -1 0 1 1 0 1 0
17 | 0 1 1 -1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 1 0 1 1 -1
19 | 0 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 -1 0 1
21 | 0 1 -1 0 1 1 0 0 -1 0 -1 -1 0 -1 0 0 1 1 0 -1 1
</pre>
 
Alextretyak
1,480

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327751...363357"