Jacobi symbol: Difference between revisions

=={{header|J}}==

<lang J>

NB. direct translation of the Lua program found

NB. at the wikipedia entry incorporated here as comment.

NB. &> makes jacobi work atomically. rank 0.

NB.function jacobi(n, k)

jacobi=: 4 :0&>

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>

<pre>

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|

+------+--------------------------------------------------------------------------------------+

</pre>