P-Adic square roots: Difference between revisions

</pre>

=={{header|Julia}}==

<lang julia>using Nemo, LinearAlgebra

set_printing_mode(FlintPadicField, :terse)

""" convert to Rational (rational reconstruction) """

function toRational(pa::padic)

rat = lift(QQ, pa)

r, den = BigInt(numerator(rat)), Int(denominator(rat))

p, k = Int(prime(parent(pa))), Int(precision(pa))

N = BigInt(p^k)

a1, a2 = [N, 0], [r, 1]

while dot(a1, a1) > dot(a2, a2)

q = dot(a1, a2) // dot(a2, a2)

a1, a2 = a2, a1 - BigInt(round(q)) * a2

end

if dot(a1, a1) < N

return (Rational{Int}(a1[1]) // Rational{Int}(a1[2])) // Int(den)

else

return Int(r) // den

end

end

function dstring(pa::padic)

u, v, n, p, k = pa.u, pa.v, pa.N, pa.parent.p, pa.parent.prec_max

d = digits(v > 0 ? u * p^v : u, base=p, pad=k)

return prod([i == k + v && v != 0 ? "$x . " : "$x " for (i, x) in enumerate(reverse(d))])

end

const DATA = [

[-7, 1, 2, 7],

[9, 1, 2, 8],

[17, 1, 2, 9],

[-1, 1, 5, 8],

[86, 25, 5, 8],

[2150, 1, 5, 8],

[2, 1, 7, 8],

[3029, 4821, 7, 9],

[379, 449, 7, 8],

[717, 8, 11, 7],

[1414, 213, 41, 5],

[-255, 256, 257, 3]

]

for (num1, den1, P, K) in DATA

Qp = PadicField(P, K)

a = Qp(QQ(big(num1) // big(den1)))

c = sqrt(a)

r = toRational(c * c)

println(a, "\nsqrt +/-\n", dstring(c), "\n", dstring(-c), "\nCheck sqrt^2:\n", dstring(c * c), "\n", r, "\n")

end

</lang>{{out}}

<pre>

121 + O(2^7)

sqrt +/-

1 1 1 0 1 0 1

0 0 0 1 0 1 1

Check sqrt^2:

1 1 1 1 0 0 1

-7//1

9 + O(2^8)

sqrt +/-

1 1 1 1 1 1 0 1

0 0 0 0 0 0 1 1

Check sqrt^2:

0 0 0 0 1 0 0 1

9//1

17 + O(2^9)

sqrt +/-

0 1 1 1 0 1 0 0 1

1 0 0 0 1 0 1 1 1

Check sqrt^2:

0 0 0 0 1 0 0 0 1

17//1

390624 + O(5^8)

sqrt +/-

3 2 4 3 1 2 1 2

1 2 0 1 3 2 3 3

Check sqrt^2:

4 4 4 4 4 4 4 4

-1//1

86/25 + O(5^6)

sqrt +/-

1 1 0 2 4 1 1 . 1

3 3 4 2 0 3 3 . 4

Check sqrt^2:

0 0 0 0 0 3 . 2 1

86//25

2150 + O(5^10)

sqrt +/-

1 1 0 2 4 1 1 1 0 .

3 3 4 2 0 3 3 4 0 .

Check sqrt^2:

0 0 0 3 2 1 0 0

2150//1

2 + O(7^8)

sqrt +/-

2 1 2 1 6 2 1 3

4 5 4 5 0 4 5 4

Check sqrt^2:

0 0 0 0 0 0 0 2

2//1

39483088 + O(7^9)

sqrt +/-

5 2 5 2 4 5 3 1 1

1 4 1 4 2 1 3 5 6

Check sqrt^2:

6 5 6 4 1 3 0 2 1

3029//4821

4493721 + O(7^8)

sqrt +/-

0 4 5 0 1 2 2 1

6 2 1 6 5 4 4 6

Check sqrt^2:

5 3 1 2 4 1 4 1

379//449

2435986 + O(11^7)

sqrt +/-

2 10 8 7 0 1 5

8 0 2 3 10 9 6

Check sqrt^2:

1 4 1 4 2 1 3

717//8

36443037 + O(41^5)

sqrt +/-

9 1 38 6 8

31 39 2 34 33

Check sqrt^2:

12 36 31 15 23

1414//213

16908285 + O(257^3)

sqrt +/-

134 66 68

122 190 189

Check sqrt^2:

255 255 255

-255//256