Rosetta Code

Jacobi symbol: Difference between revisions

Page Discussion

Jacobi symbol (view source)

Revision as of 08:56, 7 April 2024

17,118 bytes added ,  1 month ago
m
→‎{{header|11l}}: X.throw
No edit summary
 
(24 intermediate revisions by 11 users not shown)
Line 16:
{{trans|Python}}
 
<langsyntaxhighlight 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 50:
L(k) 0..kmax
print(‘#3’.format(jacobi(k, n)), end' ‘’)
print()</langsyntaxhighlight>
 
{{out}}
Line 71:
=={{header|Action!}}==
{{libheader|Action! Tool Kit}}
<langsyntaxhighlight Actionlang="action!">INCLUDE "D2:PRINTF.ACT" ;from the Action! Tool Kit
 
INT FUNC Jacobi(INT a,n)
Line 136:
Put(125) PutE() ;clear the screen
PrintTable(10,39)
RETURN</langsyntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Jacobi_symbol.png Screenshot from Atari 8-bit computer]
Line 163:
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>
 
=={{header|Arturo}}==
{{trans|Nim}}
<syntaxhighlight lang="rebol">jacobi: function [n,k][
N: n % k
K: k
 
result: 1
while [N <> 0][
while [even? N][
N: shr N 1
if contains? [3 5] and K 7 ->
result: neg result
]
[N,K]: @[K,N]
if and? 3=and N 3 3=and K 3 ->
result: neg result
N: N % K
]
if K <> 1 ->
result: 0
 
return result
]
 
print ["" "k/n" "|"] ++ map to [:string] 1..20 'item -> pad.left item 2
print repeat "=" 67
loop range.step:2 1 21 'k [
print [
"" pad to :string k 3 "|" join.with:" " map to [:string] map 1..20 'n -> jacobi n k
'item -> pad.left item 2
]
]</syntaxhighlight>
 
{{out}}
 
<pre> k/n | 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
3 | 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1
5 | 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
9 | 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
11 | 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -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
15 | 1 1 0 1 0 0 -1 1 0 0 -1 0 -1 -1 0 1 1 0 1 0
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>
 
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">result := "n/k|"
loop 20
result .= SubStr(" " A_Index, -1) " "
l := StrLen(result)
result .= "`n"
loop % l
result .= "-"
result .= "`n"
 
loop 21
{
if !Mod(n := A_Index, 2)
continue
result .= SubStr(" " n, -1) " |"
loop 20
result .= SubStr(" " jacobi(a := A_Index, n), -1) " "
result .= "`n"
}
MsgBox, 262144, , % result
return
 
jacobi(a, n) {
a := Mod(a, n), t := 1
while (a != 0) {
while !Mod(a, 2)
a := a >> 1, r := Mod(n, 8), t := (r=3 || r=5) ? -t : t
r := n, n := a, a := r
if (Mod(a, 4)=3 && Mod(n, 4)=3)
t := -t
a := Mod(a, n)
}
return (n=1) ? t : 0
}</syntaxhighlight>
{{out}}
<pre>n/k| 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
3 | 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 1 -1
5 | 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
9 | 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
11 | 1 -1 1 1 1 -1 -1 -1 1 -1 0 1 -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
15 | 1 1 0 1 0 0 -1 1 0 0 -1 0 -1 -1 0 1 1 0 1 0
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>
 
=={{header|AWK}}==
{{trans|Go}}
<syntaxhighlight lang="awk">
<lang AWK>
# syntax: GAWK -f JACOBI_SYMBOL.AWK
BEGIN {
Line 213 ⟶ 431:
return(0)
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 236 ⟶ 454:
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdlib.h>
#include <stdio.h>
 
Line 274 ⟶ 492:
print_table(20, 21);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 295 ⟶ 513:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <cassert>
#include <iomanip>
Line 338 ⟶ 556:
print_table(std::cout, 20, 21);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 359 ⟶ 577:
=={{header|Crystal}}==
{{trans|Swift}}
<langsyntaxhighlight lang="ruby">def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
Line 380 ⟶ 598:
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
end</langsyntaxhighlight>
 
{{out}}
Line 399 ⟶ 617:
 
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
<lang Erlang>
jacobi(_, N) when N =< 0 -> jacobi_domain_error;
jacobi(_, N) when (N band 1) =:= 0 -> jacobi_domain_error;
Line 427 ⟶ 645:
false -> J2
end.
</syntaxhighlight>
</lang>
 
=={{header|F_Sharp|F#}}==
<langsyntaxhighlight lang="fsharp">
//Jacobi Symbol. Nigel Galloway: July 14th., 2020
let J n m=let rec J n m g=match n with
Line 439 ⟶ 657:
printfn "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\n ----------------------------------------------------------------------------------------------------------------------"
[1..2..29]|>List.iter(fun m->printf "%3d" m; [1..30]|>List.iter(fun n->printf "%4d" (J n m)); printfn "")
</syntaxhighlight>
</lang>
{{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 465 ⟶ 683:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">function gcdp( a as uinteger, b as uinteger ) as uinteger
if b = 0 then return a
return gcdp( b, a mod b )
Line 509 ⟶ 727:
next k
print outstr
next pn</langsyntaxhighlight>
{{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 535 ⟶ 753:
 
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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 594 ⟶ 812:
fmt.Println()
}
}</langsyntaxhighlight>
 
{{out}}
Line 627 ⟶ 845:
=={{header|Haskell}}==
{{trans|Scheme}}
<langsyntaxhighlight lang="haskell">jacobi :: Integer -> Integer -> Integer
jacobi 0 1 = 1
jacobi 0 _ = 0
Line 640 ⟶ 858:
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</langsyntaxhighlight>
 
 
Or, expressing it slightly differently, and adding a tabulation:
<syntaxhighlight lang ="haskell">import Data.ListBool (replicate, transposebool)
import Data.List (replicate, transpose)
import Data.List.Split (chunksOf)
 
import Data.Bool (bool)
---------------------- JACOBI SYMBOL ---------------------
 
jacobi :: Int -> Int -> Int
Line 654 ⟶ 874:
go 0 _ = 0
go x y
| even r = plusMinus (rem y 8 `elem` [3, 5]) (go (div r 2) y)
plusMinus
(rem y 8 `elem` [3, 5])
(go (div r 2) y)
| otherwise = plusMinus (p r && p y) (go y r)
where
Line 661 ⟶ 884:
r = rem x y
 
 
------------------------- DISPLAY -------------------------
--------------------------- TEST -------------------------
main :: IO ()
main = putStrLn $ jacobiTable 11 9
 
------------------------- 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
uncurry jacobi <$> ((,) <$> colLabels <*> rowLabels)
<$> ((,) <$> colLabels <*> rowLabels)
 
-------------------------- TESTTABULATION FUNCTIONS ---------------------------
paddedCols ::
main :: IO ()
Show a =>
main = putStrLn $ jacobiTable 11 9
[[a]] ->
 
[[String]]
------------------ 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
in zipWith (:) ((++ " ->") . justifyRight w ' ' <$> labels) (transpose cols)
(:)
((<> " ->") . justifyRight w ' ' <$> labels)
(transpose cols)
 
withColumnLabels :: [String] -> [[String]] -> String
withColumnLabels labels rows@(x:_) [] = ""
withColumnLabels labels rows@(x : _) =
let labelRow = unwords $ zipWith (`justifyRight` ' ') (length <$> x) labels
let labelRow =
in unlines $ labelRow : replicate (length labelRow) '-' : fmap unwords rows
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 ++<>)</langsyntaxhighlight>
{{Out}}
<pre> 0 1 2 3 4 5 6 7 8 9 10
Line 711 ⟶ 948:
 
=={{header|J}}==
<syntaxhighlight lang="j">
<lang J>
NB. directfunctionally equivalent translation of the Lua program found
NB. at https://en.wikipedia.org/wiki/Jacobi_symbol
NB. at the wikipedia entry incorporated here in comments.
jacobi=: {{
 
assert. (0<x) * 1=2|x
NB.function jacobi(n, k)
y=. x|y
jacobi=: dyad define every
t=. 1
 
while. y do.
k=. x NB. k is the left argument
e=. (|.#:y) i.1
n=. y NB. n is the right hand argument
y=. <.y%2^e
 
t=. t*_1^(*/3 = 4|x,y)+(2|e)*(8|x) e.3 5
NB.assert(k > 0 and k % 2 == 1)
assert. (k >'x 0) *y'=. 1 = 2y, y| kx
 
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.
t*x=1
}}"0</syntaxhighlight>
 
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>
<pre>
k=: 1 2 p. i. 30
Line 832 ⟶ 1,007:
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">
 
public class JacobiSymbol {
Line 883 ⟶ 1,058:
 
}
</syntaxhighlight>
</lang>
{{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 906 ⟶ 1,081:
=={{header|jq}}==
{{trans|Julia}}
<syntaxhighlight lang="jq">
<lang jq>
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def rpad($len): tostring | ($len - length) as $l | . + (" " * $l)[:$l];
Line 927 ⟶ 1,102:
(range( 1; 32; 2) as $n
| "\($n|rpad(3))" + reduce range(1; 13) as $a (""; . + (jacobi($a; $n) | lpad(4) ))
)</langsyntaxhighlight>
{{out}}
<pre>
Line 952 ⟶ 1,127:
=={{header|Julia}}==
{{trans|Python}}
<langsyntaxhighlight lang="julia">function jacobi(a, n)
a %= n
result = 1
Line 975 ⟶ 1,150:
end
end
</langsyntaxhighlight>{{out}}
<pre>
Table of jacobi(a, n) for a 1 to 12, n 1 to 31
Line 1,000 ⟶ 1,175:
 
=={{header|Kotlin}}==
<langsyntaxhighlight lang="scala">fun jacobi(A: Int, N: Int): Int {
assert(N > 0 && N and 1 == 1)
var a = A % N
Line 1,022 ⟶ 1,197:
}
return if (n == 1) result else 0
}</langsyntaxhighlight>
 
=={{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}}==
<langsyntaxhighlight Mathematicalang="mathematica">TableForm[Table[JacobiSymbol[n, k], {n, 1, 17, 2}, {k, 16}],
TableHeadings -> {ReplacePart[Range[1, 17, 2], 1 -> "n=1"],
ReplacePart[Range[16], 1 -> "k=1"]}]</langsyntaxhighlight>
{{out}}
Produces a nicely typeset table.
Line 1,033 ⟶ 1,267:
=={{header|Nim}}==
Translation of the Lua program from Wikipedia page.
<langsyntaxhighlight Nimlang="nim">template isOdd(n: int): bool = (n and 1) != 0
template isEven(n: int): bool = (n and 1) == 0
 
Line 1,066 ⟶ 1,300:
for n in 1..20:
stdout.write align($jacobi(n, k), 3)
echo ""</langsyntaxhighlight>
 
{{out}}
Line 1,085 ⟶ 1,319:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
 
Line 1,117 ⟶ 1,351:
printf '%4d', J($_, $n) for 1..$maxa;
print "\n"
}</langsyntaxhighlight>
{{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,138 ⟶ 1,372:
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">jacobi</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 1,164 ⟶ 1,398:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,185 ⟶ 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>
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">def jacobi(a, n):
if n <= 0:
raise ValueError("'n' must be a positive integer.")
Line 1,208 ⟶ 1,539:
return result
else:
return 0</langsyntaxhighlight>
 
=={{header|Raku}}==
Line 1,214 ⟶ 1,545:
{{works with|Rakudo|2019.11}}
 
<syntaxhighlight lang="raku" perl6line># Jacobi function
sub infix:<J> (Int $k is copy, Int $n is copy where * % 2) {
$k %= $n;
Line 1,243 ⟶ 1,574:
}
print "\n";
}</langsyntaxhighlight>
{{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,267 ⟶ 1,598:
 
<br>A little extra code was added to make a prettier grid.
<langsyntaxhighlight 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.*/
Line 1,300 ⟶ 1,631:
end /*while a\==0*/
if n==1 then return $
return 0</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 1,319 ⟶ 1,650:
=={{header|Ruby}}==
{{trans|Crystal}}
<langsyntaxhighlight lang="ruby">def jacobi(a, n)
raise ArgumentError.new "n must b positive and odd" if n < 1 || n.even?
res = 1
Line 1,340 ⟶ 1,671:
(0..10).each { |a| printf(" % 2d", jacobi(a, n)) }
puts
end</langsyntaxhighlight>
 
{{out}}
Line 1,359 ⟶ 1,690:
=={{header|Rust}}==
{{trans|C++}}
<langsyntaxhighlight lang="rust">fn jacobi(mut n: i32, mut k: i32) -> i32 {
assert!(k > 0 && k % 2 == 1);
n %= k;
Line 1,405 ⟶ 1,736:
fn main() {
print_table(20, 21);
}</langsyntaxhighlight>
 
{{out}}
Line 1,425 ⟶ 1,756:
 
=={{header|Scala}}==
<langsyntaxhighlight lang="scala">
def jacobi(a_p: Int, n_p: Int): Int =
{
Line 1,458 ⟶ 1,789:
} yield println("n = " + n + ", a = " + a + ": " + jacobi(a, n))
}
</syntaxhighlight>
</lang>
 
{{out|output}}
Line 1,574 ⟶ 1,905:
 
=={{header|Scheme}}==
<langsyntaxhighlight lang="scheme">(define jacobi (lambda (a n)
(let ((a-mod-n (modulo a n)))
(if (zero? a-mod-n)
Line 1,586 ⟶ 1,917:
(if (and (= (modulo a-mod-n 4) 3) (= (modulo n 4) 3))
(- (jacobi n a-mod-n))
(jacobi n a-mod-n)))))))</langsyntaxhighlight>
 
=={{header|Sidef}}==
Line 1,592 ⟶ 1,923:
Also built-in as '''kronecker(n,k)'''.
 
<langsyntaxhighlight 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))
}</langsyntaxhighlight>
 
=={{header|Swift}}==
 
<langsyntaxhighlight lang="swift">import Foundation
 
func jacobi(a: Int, n: Int) -> Int {
Line 1,654 ⟶ 1,987:
 
print()
}</langsyntaxhighlight>
 
{{out}}
Line 1,670 ⟶ 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,713 ⟶ 2,046:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,732 ⟶ 2,065:
{{trans|Python}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Fmt
 
var jacobi = Fn.new { |a, n|
Line 1,760 ⟶ 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
}</langsyntaxhighlight>
 
{{out}}
Line 1,786 ⟶ 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>
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn jacobi(a,n){
if(n.isEven or n<1)
throw(Exception.ValueError("'n' must be a positive odd integer"));
Line 1,803 ⟶ 2,195:
}
if(n==1) result else 0
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">println("Using hand-coded version:");
println("n/a 0 1 2 3 4 5 6 7 8 9");
println("---------------------------------");
Line 1,811 ⟶ 2,203:
foreach a in (10){ print(" % d".fmt(jacobi(a,n))) }
println();
}</langsyntaxhighlight>
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
<langsyntaxhighlight 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");
Line 1,821 ⟶ 2,213:
foreach a in (10){ print(" % d".fmt(BI(a).jacobi(n))) }
println();
}</langsyntaxhighlight>
{{out}}
<pre>
Alextretyak
1,463

edits

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