P-Adic square roots: Difference between revisions

=={{header|Haskell}}==

Uses solutin for [[P-Adic_numbers,_basic#Haskell]]

<lang haskell>{-# LANGUAGE KindSignatures, DataKinds #-}

import Data.Ratio

import Data.List (find)

import GHC.TypeLits

import Padic

pSqrt :: KnownNat p => Rational -> Padic p

pSqrt r = res

where

res = maybe Null mkUnit series

(a, b) = (numerator r, denominator r)

series = case modulo res of

2 | eqMod 4 a 3 -> Nothing

| not (eqMod 8 a 1) -> Nothing

| otherwise -> Just $ 1 : 0 : go 8 1

where

go pk x =

let q = ((b*x*x - a) `div` pk) `mod` 2

in q : go (2*pk) (x + q * (pk `div` 2))

p -> do

y <- find (\x -> eqMod p (b*x*x) a) [1..p-1]

df <- recipMod p (2*b*y)

let go pk x =

let f = (b*x*x - a) `div` pk

d = (f * (p - df)) `mod` p

in x `div` (pk `div` p) : go (p*pk) (x + d*pk)

Just $ go p y

eqMod :: Integral a => a -> a -> a -> Bool

eqMod p a b = a `mod` p == b `mod` p</lang>

<pre>λ> :set -XDataKinds

λ> pSqrt 2 :: Padic 7

7-adic: 12011266421216213.0

λ> pSqrt 39483088 :: Padic 7

7-adic: 22666526525245311.0

λ> pSqrt 5 :: Padic 7

Null

λ> pSqrt 9 :: Padic 2

2-adic: 11111111111111101.0

λ> it ^ 2

2-adic: 1001.0

λ> toRational it

9 % 1

λ> pSqrt 17 ^ 2 == (17 :: Padic 2)

True

λ> pSqrt 50 ^ 2 == (50 :: Padic 7)

True

λ> pSqrt 52 ^ 2 == (52 :: Padic 7)

False

λ> pSqrt 52 :: Padic 7

Null</pre>