Jacobi symbol: Difference between revisions

<lang zkl>fcn jacobi(a,n){

if(n.isEven or n<1)

throw(Exception.ValueError("'n' must be a positive odd integer"));

a=a%n; result,t := 1,0;

while(a!=0){

while(a.isEven){

a/=2; n_mod_8:=n%8;

if(n_mod_8==3 or n_mod_8==5) result=-result;

}

t,a,n = a,n,t;

if(a%4==3 and n%4==3) result=-result;

a=a%n;

}

if(n==1) result else 0

}</lang>

<lang zkl>println("Using hand-coded version:");

println("n/a 0 1 2 3 4 5 6 7 8 9");

println("---------------------------------");

foreach n in ([1..17,2]){

print("%2d ".fmt(n));

foreach a in (10){ print(" % d".fmt(jacobi(a,n))) }

println();

}</lang>

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library

<lang zkl>var [const] BI=Import.lib("zklBigNum"); // libGMP

println("\nUsing BigInt library function:");

println("n/a 0 1 2 3 4 5 6 7 8 9");

println("---------------------------------");

foreach n in ([1..17,2]){

print("%2d ".fmt(n));

foreach a in (10){ print(" % d".fmt(BI(a).jacobi(n))) }

println();

}</lang>

Using hand-coded version:

n/a 0 1 2 3 4 5 6 7 8 9

---------------------------------

1 1 1 1 1 1 1 1 1 1 1

3 0 1 -1 0 1 -1 0 1 -1 0

5 0 1 -1 -1 1 0 1 -1 -1 1

7 0 1 1 -1 1 -1 -1 0 1 1

9 0 1 1 0 1 1 0 1 1 0

11 0 1 -1 1 1 1 -1 -1 -1 1

13 0 1 -1 1 1 -1 -1 -1 -1 1

15 0 1 1 0 1 0 0 -1 1 0

17 0 1 1 -1 1 -1 -1 -1 1 1

Using BigInt library function:

n/a 0 1 2 3 4 5 6 7 8 9

---------------------------------

1 1 1 1 1 1 1 1 1 1 1

3 0 1 -1 0 1 -1 0 1 -1 0

5 0 1 -1 -1 1 0 1 -1 -1 1

7 0 1 1 -1 1 -1 -1 0 1 1

9 0 1 1 0 1 1 0 1 1 0

11 0 1 -1 1 1 1 -1 -1 -1 1

13 0 1 -1 1 1 -1 -1 -1 -1 1

15 0 1 1 0 1 0 0 -1 1 0

17 0 1 1 -1 1 -1 -1 -1 1 1