Calculating 2-adic square roots

This returns the first n binary digits of the two 2-adic sqroot x of an integer a=8k+1.
This is a BCMATH translation of a BC program.

A sequence of positive integers an < 2n+2, n ≥ 0 is constructed, which converges 2-adically to a 2-adic square root of a:
an-12 ≡ a (mod 2n+2),
a0 = 1 or 3, an = an-1 + bn2n+1, n ≥ 1.
bn is 0 or 1 and is determined by bn ≡ (an-12 - a)/2n+2 (mod 2).
a0 = 1 implies x = 1 +0*2 + b122 + ···
a0 = 3 implies x = 3 +1*2 + b122 + ···

(See lecture notes and solutions).

Enter a (a ≡ 1 (mod 8)):
Enter n (≥ 2):
Last modified 17th March 2011
Return to main page