Jacobi symbol
You are encouraged to solve this task according to the task description, using any language you may know.
The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p)
- (a | p) ≡ 1 if a is a square (mod p)
- (a | p) ≡ -1 if a is not a square (mod p)
- (a | p) ≡ 0 if a ≡ 0
If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).
- Task
Calculate the Jacobi symbol (a | n).
- Reference
AWK
<lang AWK>
- syntax: GAWK -f JACOBI_SYMBOL.AWK
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>
- Output:
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
Crystal
<lang ruby>def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
until (a %= n) == 0
while a.even?
a >>= 1
res = -res if [3, 5].includes? n % 8
end
a, n = n, a
res = -res if a % 4 == n % 4 == 3
end
n == 1 ? res : 0
end
puts "Jacobian symbols for jacobi(a, n)" puts "n\\a 0 1 2 3 4 5 6 7 8 9 10" puts "------------------------------------" 1.step(to: 17, by: 2) do |n|
printf("%2d ", n)
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
end</lang>
- Output:
Jacobian symbols for jacobi(a, n) n\a 0 1 2 3 4 5 6 7 8 9 10 ------------------------------------ 1 1 1 1 1 1 1 1 1 1 1 1 3 0 1 -1 0 1 -1 0 1 -1 0 1 5 0 1 -1 -1 1 0 1 -1 -1 1 0 7 0 1 1 -1 1 -1 -1 0 1 1 -1 9 0 1 1 0 1 1 0 1 1 0 1 11 0 1 -1 1 1 1 -1 -1 -1 1 -1 13 0 1 -1 1 1 -1 -1 -1 -1 1 1 15 0 1 1 0 1 0 0 -1 1 0 0 17 0 1 1 -1 1 -1 -1 -1 1 1 -1
Erlang
<lang Erlang> jacobi(_, N) when N =< 0 -> jacobi_domain_error; jacobi(_, N) when (N band 1) =:= 0 -> jacobi_domain_error; 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>
Factor
The jacobi word already exists in the math.extras vocabulary. See the implementation here.
Go
The big.Jacobi function in the standard library (for 'big integers') returns the Jacobi symbol for given values of 'a' and 'n'.
This translates the Lua code in the above referenced Wikipedia article to Go (for 8 byte integers) and checks that it gives the same answers for a small table of values - which it does. <lang go>package main
import (
"fmt" "log" "math/big"
)
func jacobi(a, n uint64) int {
if n%2 == 0 {
log.Fatal("'n' must be a positive odd integer")
}
a %= n
result := 1
for a != 0 {
for a%2 == 0 {
a /= 2
nn := n % 8
if nn == 3 || nn == 5 {
result = -result
}
}
a, n = n, a
if a%4 == 3 && n%4 == 3 {
result = -result
}
a %= n
}
if n == 1 {
return result
}
return 0
}
func main() {
fmt.Println("Using hand-coded version:")
fmt.Println("n/a 0 1 2 3 4 5 6 7 8 9")
fmt.Println("---------------------------------")
for n := uint64(1); n <= 17; n += 2 {
fmt.Printf("%2d ", n)
for a := uint64(0); a <= 9; a++ {
fmt.Printf(" % d", jacobi(a, n))
}
fmt.Println()
}
ba, bn := new(big.Int), new(big.Int)
fmt.Println("\nUsing standard library function:")
fmt.Println("n/a 0 1 2 3 4 5 6 7 8 9")
fmt.Println("---------------------------------")
for n := uint64(1); n <= 17; n += 2 {
fmt.Printf("%2d ", n)
for a := uint64(0); a <= 9; a++ {
ba.SetUint64(a)
bn.SetUint64(n)
fmt.Printf(" % d", big.Jacobi(ba, bn))
}
fmt.Println()
}
}</lang>
- Output:
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 standard 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
Haskell
<lang haskell>jacobi :: Integer -> Integer -> Integer jacobi 0 1 = 1 jacobi 0 _ = 0 jacobi a n =
let a_mod_n = rem a n
in if even a_mod_n
then case rem n 8 of
1 -> jacobi (div a_mod_n 2) n
3 -> negate $ jacobi (div a_mod_n 2) n
5 -> negate $ jacobi (div a_mod_n 2) n
7 -> jacobi (div a_mod_n 2) n
else if rem a_mod_n 4 == 3 && rem n 4 == 3
then negate $ jacobi n a_mod_n
else jacobi n a_mod_n</lang>
Or, expressing it slightly differently, and adding a tabulation:
<lang haskell>import Data.List (replicate, transpose)
import Data.List.Split (chunksOf)
import Data.Bool (bool)
jacobi :: Int -> Int -> Int jacobi = go
where
go 0 1 = 1
go 0 _ = 0
go x y
| even r = plusMinus (rem y 8 `elem` [3, 5]) (go (div r 2) y)
| otherwise = plusMinus (p r && p y) (go y r)
where
plusMinus = bool id negate
p = (3 ==) . flip rem 4
r = rem x y
DISPLAY -------------------------
jacobiTable :: Int -> Int -> String jacobiTable nCols nRows =
let rowLabels = [1,3 .. (2 * nRows)]
colLabels = [0 .. pred nCols]
in withColumnLabels ("" : fmap show colLabels) $
labelledRows (fmap show rowLabels) $
paddedCols $
chunksOf nRows $
uncurry jacobi <$> ((,) <$> colLabels <*> rowLabels)
TEST ---------------------------
main :: IO () main = putStrLn $ jacobiTable 11 9
TABULATION FUNCTIONS -------------------
paddedCols
:: Show a => a -> String
paddedCols cols =
let scols = fmap show <$> cols
w = maximum $ length <$> concat scols
in map (justifyRight w ' ') <$> scols
labelledRows :: [String] -> String -> String labelledRows labels cols =
let w = maximum $ map length labels in zipWith (:) ((++ " ->") . justifyRight w ' ' <$> labels) (transpose cols)
withColumnLabels :: [String] -> String -> String withColumnLabels labels rows@(x:_) =
let labelRow = unwords $ zipWith (`justifyRight` ' ') (length <$> x) labels in unlines $ labelRow : replicate (length labelRow) '-' : fmap unwords rows
justifyRight :: Int -> a -> [a] -> [a] justifyRight n c = (drop . length) <*> (replicate n c ++)</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 10 -------------------------------------- 1 -> 1 1 1 1 1 1 1 1 1 1 1 3 -> 0 1 -1 0 1 -1 0 1 -1 0 1 5 -> 0 1 -1 -1 1 0 1 -1 -1 1 0 7 -> 0 1 1 -1 1 -1 -1 0 1 1 -1 9 -> 0 1 1 0 1 1 0 1 1 0 1 11 -> 0 1 -1 1 1 1 -1 -1 -1 1 -1 13 -> 0 1 -1 1 1 -1 -1 -1 -1 1 1 15 -> 0 1 1 0 1 0 0 -1 1 0 0 17 -> 0 1 1 -1 1 -1 -1 -1 1 1 -1
J
<lang J> NB. direct translation of the Lua program found NB. at the wikipedia entry incorporated here in comments.
NB.function jacobi(n, k) jacobi=: dyad define every
k=. x NB. k is the left argument n=. y NB. n is the right hand argument
NB.assert(k > 0 and k % 2 == 1)
assert. (k > 0) *. 1 = 2 | k
NB.n = n % k
n =. k | n
NB.t = 1
t =. 1
NB.while n ~= 0 do
while. n do.
NB. while n % 2 == 0 do
while. -. 2 | n do.
NB. n = n / 2
n =. <. n % 2
NB. r = k % 8
r =. 8 | k
NB. if r == 3 or r == 5 then
if. r e. 3 5 do.
NB. t = -t
t =. -t
NB. end
end.
NB. end
end.
NB. n, k = k, n
'n k' =. k , n
NB. if n % 4 == 3 and k % 4 == 3 then
if. (3 = 4 | n) *. (3 = 4 | k) do.
NB. t = -t
t =. -t
NB. end
end.
NB. n = n % k
n =. k | n
NB.end
end.
NB.if k == 1 then
if. k = 1 do.
NB. return t
t
NB.else
else.
NB. return 0
0
NB.end
end.
NB.end ) </lang>
k=: 1 2 p. i. 30 n=: #\ k k jacobi table n +------+--------------------------------------------------------------------------------------+ |jacobi|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| |31 |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| |33 |1 1 0 1 _1 0 _1 1 0 _1 0 0 _1 _1 0 1 1 0 _1 _1 0 0 _1 0 1 _1 0 _1 1 0| |35 |1 _1 1 1 0 _1 0 _1 1 0 1 1 1 0 0 1 1 _1 _1 0 0 _1 _1 _1 0 _1 1 0 1 0| |37 |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| |39 |1 1 0 1 1 0 _1 1 0 1 1 0 0 _1 0 1 _1 0 _1 1 0 1 _1 0 1 0 0 _1 _1 0| |41 |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| |43 |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| |45 |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| |47 |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| |49 |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| |51 |1 _1 0 1 1 0 _1 _1 0 _1 1 0 1 1 0 1 0 0 1 1 0 _1 1 0 1 _1 0 _1 1 0| |53 |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| |55 |1 1 _1 1 0 _1 1 1 1 0 0 _1 1 1 0 1 1 1 _1 0 _1 0 _1 _1 0 1 _1 1 _1 0| |57 |1 1 0 1 _1 0 1 1 0 _1 _1 0 _1 1 0 1 _1 0 0 _1 0 _1 _1 0 1 _1 0 1 1 0| |59 |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| +------+--------------------------------------------------------------------------------------+
Java
<lang java>
public class JacobiSymbol {
public static void main(String[] args) {
int max = 30;
System.out.printf("n\\k ");
for ( int k = 1 ; k <= max ; k++ ) {
System.out.printf("%2d ", k);
}
System.out.printf("%n");
for ( int n = 1 ; n <= max ; n += 2 ) {
System.out.printf("%2d ", n);
for ( int k = 1 ; k <= max ; k++ ) {
System.out.printf("%2d ", jacobiSymbol(k, n));
}
System.out.printf("%n");
}
}
// Compute (k n), where k is numerator
private static int jacobiSymbol(int k, int n) {
if ( k < 0 || n % 2 == 0 ) {
throw new IllegalArgumentException("Invalid value. k = " + k + ", n = " + n);
}
k %= n;
int jacobi = 1;
while ( k > 0 ) {
while ( k % 2 == 0 ) {
k /= 2;
int r = n % 8;
if ( r == 3 || r == 5 ) {
jacobi = -jacobi;
}
}
int temp = n;
n = k;
k = temp;
if ( k % 4 == 3 && n % 4 == 3 ) {
jacobi = -jacobi;
}
k %= n;
}
if ( n == 1 ) {
return jacobi;
}
return 0;
}
} </lang>
- Output:
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 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
Julia
<lang julia>function jacobi(a, n)
a %= n
result = 1
while a != 0
while iseven(a)
a ÷= 2
((n % 8) in [3, 5]) && (result *= -1)
end
a, n = n, a
(a % 4 == n % 4 == 3) && (result *= -1)
a %= n
end
return n == 1 ? result : 0
end
print(" Table of jacobi(a, n) for a 1 to 12, n 1 to 31\n 1 2 3 4 5 6 7 8",
" 9 10 11 12\nn\n_____________________________________________________")
for n in 1:2:31
print("\n", rpad(n, 3))
for a in 1:11
print(lpad(jacobi(a, n), 4))
end
end
</lang>
- Output:
Table of jacobi(a, n) for a 1 to 12, n 1 to 31 1 2 3 4 5 6 7 8 9 10 11 12 n _____________________________________________________ 1 1 1 1 1 1 1 1 1 1 1 1 3 1 -1 0 1 -1 0 1 -1 0 1 -1 5 1 -1 -1 1 0 1 -1 -1 1 0 1 7 1 1 -1 1 -1 -1 0 1 1 -1 1 9 1 1 0 1 1 0 1 1 0 1 1 11 1 -1 1 1 1 -1 -1 -1 1 -1 0 13 1 -1 1 1 -1 -1 -1 -1 1 1 -1 15 1 1 0 1 0 0 -1 1 0 0 -1 17 1 1 -1 1 -1 -1 -1 1 1 -1 -1 19 1 -1 -1 1 1 1 1 -1 1 -1 1 21 1 -1 0 1 1 0 0 -1 0 -1 -1 23 1 1 1 1 -1 1 -1 1 1 -1 -1 25 1 1 1 1 0 1 1 1 1 0 1 27 1 -1 0 1 -1 0 1 -1 0 1 -1 29 1 -1 -1 1 1 1 1 -1 1 -1 -1 31 1 1 -1 1 1 -1 1 1 1 1 -1
Kotlin
<lang scala>fun jacobi(A: Int, N: Int): Int {
assert(N > 0 && N and 1 == 1)
var a = A % N
var n = N
var result = 1
while (a != 0) {
var aMod4 = a and 3
while (aMod4 == 0) { // remove factors of four
a = a shr 2
aMod4 = a and 3
}
if (aMod4 == 2) { // if even
a = a shr 1 // remove factor 2 and possibly change sign
if ((n and 7).let { it == 3 || it == 5 })
result = -result
aMod4 = a and 3
}
if (aMod4 == 3 && n and 3 == 3)
result = -result
a = (n % a).also { n = a }
}
return if (n == 1) result else 0
}</lang>
Perl
<lang perl>use strict; use warnings;
sub J {
my($k,$n) = @_;
$k %= $n;
my $jacobi = 1;
while ($k) {
while (0 == $k % 2) {
$k = int $k / 2;
$jacobi *= -1 if $n%8 == 3 or $n%8 == 5;
}
($k, $n) = ($n, $k);
$jacobi *= -1 if $n%4 == 3 and $k%4 == 3;
$k %= $n;
}
$n == 1 ? $jacobi : 0
}
my $maxa = 1 + (my $maxn = 29);
print 'n\k'; printf '%4d', $_ for 1..$maxa; print "\n"; print ' ' . '-' x (4 * $maxa) . "\n";
for my $n (1..$maxn) {
next if 0 == $n % 2; printf '%3d', $n; printf '%4d', J($_, $n) for 1..$maxa; print "\n"
}</lang>
- Output:
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 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
Phix
<lang Phix>function jacobi(integer a, n)
atom result = 1
a = remainder(a,n)
while a!=0 do
while remainder(a,2)==0 do
a /= 2
if find(remainder(n,8),{3,5}) then result *= -1 end if
end while
{a, n} = {n, a}
if remainder(a,4)==3 and remainder(n,4)==3 then result *= -1 end if
a = remainder(a,n)
end while
return iff(n==1 ? result : 0)
end function
printf(1,"n\\a 0 1 2 3 4 5 6 7 8 9 10 11\n") printf(1," ________________________________________________\n") for n=1 to 31 by 2 do
printf(1,"%3d", n)
for a=0 to 11 do
printf(1,"%4d",jacobi(a, n))
end for
printf(1,"\n")
end for</lang>
- Output:
n\a 0 1 2 3 4 5 6 7 8 9 10 11 ________________________________________________ 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 5 0 1 -1 -1 1 0 1 -1 -1 1 0 1 7 0 1 1 -1 1 -1 -1 0 1 1 -1 1 9 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 13 0 1 -1 1 1 -1 -1 -1 -1 1 1 -1 15 0 1 1 0 1 0 0 -1 1 0 0 -1 17 0 1 1 -1 1 -1 -1 -1 1 1 -1 -1 19 0 1 -1 -1 1 1 1 1 -1 1 -1 1 21 0 1 -1 0 1 1 0 0 -1 0 -1 -1 23 0 1 1 1 1 -1 1 -1 1 1 -1 -1 25 0 1 1 1 1 0 1 1 1 1 0 1 27 0 1 -1 0 1 -1 0 1 -1 0 1 -1 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
Python
<lang python>def jacobi(a, n):
if n <= 0:
raise ValueError("'n' must be a positive integer.")
if n % 2 == 0:
raise ValueError("'n' must be odd.")
a %= n
result = 1
while a != 0:
while a % 2 == 0:
a /= 2
n_mod_8 = n % 8
if n_mod_8 in (3, 5):
result = -result
a, n = n, a
if a % 4 == 3 and n % 4 == 3:
result = -result
a %= n
if n == 1:
return result
else:
return 0</lang>
Raku
(formerly Perl 6)
<lang perl6># Jacobi function sub infix:<J> (Int $k is copy, Int $n is copy where * % 2) {
$k %= $n;
my $jacobi = 1;
while $k {
while $k %% 2 {
$k div= 2;
$jacobi *= -1 if $n % 8 == 3 | 5;
}
($k, $n) = $n, $k;
$jacobi *= -1 if 3 == $n%4 & $k%4;
$k %= $n;
}
$n == 1 ?? $jacobi !! 0
}
- Testing
my $maxa = 30; my $maxn = 29;
say 'n\k ', (1..$maxa).fmt: '%3d'; say ' ', '-' x 4 * $maxa; for 1,*+2 … $maxn -> $n {
print $n.fmt: '%3d';
for 1..$maxa -> $k {
print ($k J $n).fmt: '%4d';
}
print "\n";
}</lang>
- Output:
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 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
REXX
A little extra code was added to make a prettier grid.
<lang rexx>/*REXX pgm computes/displays the Jacobi symbol, the # of rows & columns can be specified*/
parse arg rows cols . /*obtain optional arguments from the CL*/
if rows= | rows=="," then rows= 17 /*Not specified? Then use the default.*/
if cols= | cols=="," then cols= 16 /* " " " " " " */
call hdrs /*display the (two) headers to the term*/
do r=1 by 2 to rows; _= right(r, 3) /*build odd (numbered) rows of a table.*/
do c=0 to cols /* [↓] build a column for a table row.*/
_= _ ! right(jacobi(c, r), 2); != '│' /*reset grid end char.*/
end /*c*/
say _ '║'; != '║' /*display a table row; reset grid glyph*/
end /*r*/
say translate(@.2, '╩╧╝', "╬╤╗") /*display the bottom of the grid border*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ hdrs: @.1= 'n/a ║'; do c=0 to cols; @.1= @.1 || right(c, 3)" "; end
L= length(@.1); @.1= left(@.1, L - 1) ; say @.1
@.2= '════╬'; do c=0 to cols; @.2= @.2 || "════╤" ; end
L= length(@.2); @.2= left(@.2, L - 1)"╗" ; say @.2
!= '║' ; return /*define an external grid border glyph.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ jacobi: procedure; parse arg a,n; er= '***error***'; $ = 1 /*define result.*/
if n//2==0 then do; say er n " must be a positive odd integer."; exit 13
end
a= a // n /*obtain A modulus N */
do while a\==0 /*perform while A isn't zero. */
do while a//2==0; a= a % 2 /*divide A (as a integer) by 2 */
if n//8==3 | n//8==5 then $= -$ /*use N mod 8 */
end /*while a//2==0*/
parse value a n with n a /*swap values of variables: A N */
if a//4==3 & n//4==3 then $= -$ /* A mod 4, N mod 4. Both ≡ 3 ?*/
a= a // n /*obtain A modulus N */
end /*while a\==0*/
if n==1 then return $
return 0</lang>
- output when using the default inputs:
n/a ║ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ════╬════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗ 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 ║ 5 ║ 0 │ 1 │ -1 │ -1 │ 1 │ 0 │ 1 │ -1 │ -1 │ 1 │ 0 │ 1 │ -1 │ -1 │ 1 │ 0 │ 1 ║ 7 ║ 0 │ 1 │ 1 │ -1 │ 1 │ -1 │ -1 │ 0 │ 1 │ 1 │ -1 │ 1 │ -1 │ -1 │ 0 │ 1 │ 1 ║ 9 ║ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │ 0 │ 1 ║ 11 ║ 0 │ 1 │ -1 │ 1 │ 1 │ 1 │ -1 │ -1 │ -1 │ 1 │ -1 │ 0 │ 1 │ -1 │ 1 │ 1 │ 1 ║ 13 ║ 0 │ 1 │ -1 │ 1 │ 1 │ -1 │ -1 │ -1 │ -1 │ 1 │ 1 │ -1 │ 1 │ 0 │ 1 │ -1 │ 1 ║ 15 ║ 0 │ 1 │ 1 │ 0 │ 1 │ 0 │ 0 │ -1 │ 1 │ 0 │ 0 │ -1 │ 0 │ -1 │ -1 │ 0 │ 1 ║ 17 ║ 0 │ 1 │ 1 │ -1 │ 1 │ -1 │ -1 │ -1 │ 1 │ 1 │ -1 │ -1 │ -1 │ 1 │ -1 │ 1 │ 1 ║ ════╩════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
Ruby
<lang ruby>def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
until (a %= n) == 0
while a.even?
a >>= 1
res = -res if [3, 5].include? n % 8
end
a, n = n, a
res = -res if [a % 4, n % 4] == [3, 3]
end
n == 1 ? res : 0
end
puts "Jacobian symbols for jacobi(a, n)" puts "n\\a 0 1 2 3 4 5 6 7 8 9 10" puts "------------------------------------" 1.step(to: 17, by: 2) do |n|
printf("%2d ", n)
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
end</lang>
- Output:
Jacobian symbols for jacobi(a, n) n\a 0 1 2 3 4 5 6 7 8 9 10 ------------------------------------ 1 1 1 1 1 1 1 1 1 1 1 1 3 0 1 -1 0 1 -1 0 1 -1 0 1 5 0 1 -1 -1 1 0 1 -1 -1 1 0 7 0 1 1 -1 1 -1 -1 0 1 1 -1 9 0 1 1 0 1 1 0 1 1 0 1 11 0 1 -1 1 1 1 -1 -1 -1 1 -1 13 0 1 -1 1 1 -1 -1 -1 -1 1 1 15 0 1 1 0 1 0 0 -1 1 0 0 17 0 1 1 -1 1 -1 -1 -1 1 1 -1
Scala
<lang scala> def jacobi(a_p: Int, n_p: Int): Int = {
var a = a_p var n = n_p if (n <= 0) return -1 if (n % 2 == 0) return -1
a %= n
var result = 1
while (a != 0) {
while (a % 2 == 0) {
a /= 2
if (n % 8 == 3 || n % 8 == 5) result = -result
}
val t = a
a = n
n = t
if (a % 4 == 3 && n % 4 == 3) result = -result
a %= n
}
if (n != 1) result = 0
result
}
def main(args: Array[String]): Unit = {
for {
a <- 0 until 11
n <- 1 until 31 by 2
} yield println("n = " + n + ", a = " + a + ": " + jacobi(a, n))
} </lang>
- output:
n = 1, a = 0: 1 n = 3, a = 0: 0 n = 5, a = 0: 0 n = 7, a = 0: 0 n = 9, a = 0: 0 n = 1, a = 1: 1 n = 3, a = 1: 1 n = 5, a = 1: 1 n = 7, a = 1: 1 n = 9, a = 1: 1 n = 1, a = 2: 1 n = 3, a = 2: -1 n = 5, a = 2: -1 n = 7, a = 2: 1 n = 9, a = 2: 1 n = 1, a = 3: 1 n = 3, a = 3: 0 n = 5, a = 3: -1 n = 7, a = 3: -1 n = 9, a = 3: 0 n = 1, a = 4: 1 n = 3, a = 4: 1 n = 5, a = 4: 1 n = 7, a = 4: 1 n = 9, a = 4: 1 n = 1, a = 5: 1 n = 3, a = 5: -1 n = 5, a = 5: 0 n = 7, a = 5: -1 n = 9, a = 5: 1 n = 1, a = 6: 1 n = 3, a = 6: 0 n = 5, a = 6: 1 n = 7, a = 6: -1 n = 9, a = 6: 0 n = 1, a = 7: 1 n = 3, a = 7: 1 n = 5, a = 7: -1 n = 7, a = 7: 0 n = 9, a = 7: 1 n = 1, a = 8: 1 n = 3, a = 8: -1 n = 5, a = 8: -1 n = 7, a = 8: 1 n = 9, a = 8: 1 n = 1, a = 9: 1 n = 3, a = 9: 0 n = 5, a = 9: 1 n = 7, a = 9: 1 n = 9, a = 9: 0 n = 1, a = 10: 1 n = 3, a = 10: 1 n = 5, a = 10: 0 n = 7, a = 10: -1 n = 9, a = 10: 1
Scheme
<lang scheme>(define jacobi (lambda (a n) (let ((a-mod-n (modulo a n))) (if (zero? a-mod-n) (if (= n 1) 1 0) (if (even? a-mod-n) (case (modulo n 8) ((3 5) (- (jacobi (/ a-mod-n 2) n))) ((1 7) (jacobi (/ a-mod-n 2) n))) (if (and (= (modulo a-mod-n 4) 3) (= (modulo n 4) 3)) (- (jacobi n a-mod-n)) (jacobi n a-mod-n)))))))</lang>
Sidef
Also built-in as kronecker(n,k).
<lang ruby>func jacobi(n, k) {
assert(k > 0, "#{k} must be positive")
assert(k.is_odd, "#{k} must be odd")
var t = 1
while (n %= k) {
var v = n.valuation(2)
t *= (-1)**v if (k%8 ~~ [3,5])
n >>= v
(n,k) = (k,n)
t = -t if ([n%4, k%4] == [3,3])
}
k==1 ? t : 0
}
for n in (0..50), k in (0..50) {
assert_eq(jacobi(n, 2*k + 1), kronecker(n, 2*k + 1))
}</lang>
Swift
<lang swift>import Foundation
func jacobi(a: Int, n: Int) -> Int {
var a = a % n var n = n var res = 1
while a != 0 {
while a & 1 == 0 {
a >>= 1
if n % 8 == 3 || n % 8 == 5 {
res = -res
}
}
(a, n) = (n, a)
if a % 4 == 3 && n % 4 == 3 {
res = -res
}
a %= n
}
return n == 1 ? res : 0
}
print("n/a 0 1 2 3 4 5 6 7 8 9") print("---------------------------------")
for n in stride(from: 1, through: 17, by: 2) {
print(String(format: "%2d", n), terminator: "")
for a in 0..<10 {
print(String(format: " % d", jacobi(a: a, n: n)), terminator: "")
}
print()
}</lang>
- Output:
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
Wren
<lang ecmascript>var jacobi = Fn.new { |a, n|
if (!n.isInteger || n <= 0 || n%2 == 0) {
Fiber.abort("The 'n' parameter must be an odd positive integer.")
}
a = a % n
var result = 1
while (a != 0) {
while (a%2 == 0) {
a = a / 2
var nm8 = n % 8
if ([3, 5].contains(nm8)) result = -result
}
var t = a
a = n
n = t
if (a%4 == 3 && n%4 == 3) result = -result
a = a % n
}
return (n == 1) ? result : 0
}
var rset = Fn.new { |m, n|
var s = "%(n)" var c = s.count return (m > c) ? " " * (m - c) + s : s
}
System.print("Table of jacobi(a, n):") System.print("n/a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15") System.print("---------------------------------------------------------------") var n = 1 while (n < 31) {
System.write(rset.call(3, n)) for (a in 1..15) System.write(rset.call(4, jacobi.call(a, n))) System.print() n = n + 2
}</lang>
- Output:
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
zkl
<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>
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>
- Output:
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