{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE FlexibleContexts #-}
{-# OPTIONS_HADDOCK hide, prune, ignore-exports #-}

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE NoStarIsType #-}

module Math.NumberTheory.Padic.Analysis where

import Math.NumberTheory.Padic.Types
import Data.Mod
import Data.Ratio
import Data.List (unfoldr, genericLength, tails, inits,find)
import Data.Maybe
import GHC.TypeLits hiding (Mod)
import Control.Applicative ((<|>))

------------------------------------------------------------

-- | Unfolds a number to a list of digits (integers modulo @p@).  
toRadix :: KnownRadix p => Integer -> [Mod p]
toRadix :: Integer -> [Mod p]
toRadix Integer
0 = [Mod p
0]
toRadix Integer
n = [Mod p]
res
  where
    res :: [Mod p]
res = (Integer -> Maybe (Mod p, Integer)) -> Integer -> [Mod p]
forall b a. (b -> Maybe (a, b)) -> b -> [a]
unfoldr Integer -> Maybe (Mod p, Integer)
go Integer
n
    p :: Integer
p = Integer -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Mod p -> Integer
forall (n :: Nat) (proxy :: Nat -> Type).
KnownNat n =>
proxy n -> Integer
natVal (Mod p -> Integer) -> Mod p -> Integer
forall a b. (a -> b) -> a -> b
$ [Mod p] -> Mod p
forall a. [a] -> a
head ([Mod p] -> Mod p) -> [Mod p] -> Mod p
forall a b. (a -> b) -> a -> b
$ Mod p
0 Mod p -> [Mod p] -> [Mod p]
forall a. a -> [a] -> [a]
: [Mod p]
res
    go :: Integer -> Maybe (Mod p, Integer)
go Integer
0 = Maybe (Mod p, Integer)
forall a. Maybe a
Nothing
    go Integer
x =
      let (Integer
q, Integer
r) = Integer -> Integer -> (Integer, Integer)
forall a. Integral a => a -> a -> (a, a)
quotRem Integer
x Integer
p
       in (Mod p, Integer) -> Maybe (Mod p, Integer)
forall a. a -> Maybe a
Just (Integer -> Mod p
forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
r, Integer
q)
  
-- | Folds a list of digits (integers modulo @p@) to a number.
fromRadix :: KnownRadix p => [Mod p] -> Integer
fromRadix :: [Mod p] -> Integer
fromRadix [Mod p]
ds = (Mod p -> Integer -> Integer) -> Integer -> [Mod p] -> Integer
forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\Mod p
x Integer
r -> Mod p -> Integer
forall n. PadicNum n => n -> Integer
lifted Mod p
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
r Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
p) Integer
0 [Mod p]
ds
  where
    p :: Integer
p = Integer -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Mod p -> Integer
forall (n :: Nat) (proxy :: Nat -> Type).
KnownNat n =>
proxy n -> Integer
natVal (Mod p -> Integer) -> Mod p -> Integer
forall a b. (a -> b) -> a -> b
$ [Mod p] -> Mod p
forall a. [a] -> a
head ([Mod p] -> Mod p) -> [Mod p] -> Mod p
forall a b. (a -> b) -> a -> b
$ Mod p
0 Mod p -> [Mod p] -> [Mod p]
forall a. a -> [a] -> [a]
: [Mod p]
ds

extEuclid :: Integral i => (Integer, Integer) -> Ratio i
extEuclid :: (Integer, Integer) -> Ratio i
extEuclid (Integer
n, Integer
m) = (Integer, Integer) -> (Integer, Integer) -> Ratio i
go (Integer
m, Integer
0) (Integer
n, Integer
1)
  where
    go :: (Integer, Integer) -> (Integer, Integer) -> Ratio i
go (Integer
v1, Integer
v2) (Integer
w1, Integer
w2)
      | Integer
2Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
w1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
w1 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer -> Integer
forall a. Num a => a -> a
abs Integer
m =
        let q :: Integer
q = Integer
v1 Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
w1
         in (Integer, Integer) -> (Integer, Integer) -> Ratio i
go (Integer
w1, Integer
w2) (Integer
v1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
w1, Integer
v2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
w2)
      | Bool
otherwise = Rational -> Ratio i
forall a. Fractional a => Rational -> a
fromRational (Integer
w1 Integer -> Integer -> Rational
forall a. Integral a => a -> a -> Ratio a
% Integer
w2)

{- | Extracts p-adic unit from integer number. For radix \(p\) and integer \(n\) returns
pair \((u, k)\) such that \(n = u \cdot p^k\).

Examples:
 
>>> getUnitZ  10 120
(12,1)
>>> getUnitZ 2 120
(15,3)
>>> getUnitZ 3 120
(40,1)
-}
getUnitZ :: (Integral p, Integral n) => p -> n -> (p, Int)
getUnitZ :: p -> n -> (p, Int)
getUnitZ p
_ n
0 = (p
0, Int
0)
getUnitZ p
p n
x = (p
b, [p] -> Int
forall (t :: Type -> Type) a. Foldable t => t a -> Int
length [p]
v)
  where
    ([p]
v, p
b:[p]
_) = (p -> Bool) -> [p] -> ([p], [p])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (\p
n -> p
n p -> p -> p
forall a. Integral a => a -> a -> a
`mod` p
p p -> p -> Bool
forall a. Eq a => a -> a -> Bool
== p
0) ([p] -> ([p], [p])) -> [p] -> ([p], [p])
forall a b. (a -> b) -> a -> b
$ (p -> p) -> p -> [p]
forall a. (a -> a) -> a -> [a]
iterate (p -> p -> p
forall a. Integral a => a -> a -> a
`div` p
p) (p -> [p]) -> p -> [p]
forall a b. (a -> b) -> a -> b
$ n -> p
forall a b. (Integral a, Num b) => a -> b
fromIntegral n
x

{- | Extracts p-adic unit from a rational number. For radix \(p\) and rational number \(x\) returns
pair \((r/s, k)\) such that \(x = r/s \cdot p^k,\quad \gcd(r, s) = \gcd(s, p) = 1\) and \(p \nmid r\).


Examples:

>>> getUnitQ 3 (75/157)
(25 % 157, 1)
>>> getUnitQ 5 (75/157)
(3 % 157, 2)
>>> getUnitQ 157 (75/157)
(75 % 1, -1)
>>> getUnitQ 10 (1/60)
(5 % 3, -2)
-}
getUnitQ :: Integral p => p -> Ratio p -> (Ratio p, Int)
getUnitQ :: p -> Ratio p -> (Ratio p, Int)
getUnitQ p
_ Ratio p
0 = (Ratio p
0, Int
0)
getUnitQ p
p Ratio p
x = ((p
n p -> p -> p
forall a. Num a => a -> a -> a
* p
n') p -> p -> Ratio p
forall a. Integral a => a -> a -> Ratio a
% p
d, Int
vn Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
vd)
  where
    go :: p -> (p, Int) -> (p, p, Int)
go p
m (p
d, Int
vd) = case p -> p -> p
forall a. Integral a => a -> a -> a
gcd p
d p
p of
      p
1 -> (p
m, p
d, Int
vd)
      p
c -> let (p
d', Int
vd') = p -> p -> (p, Int)
forall p n. (Integral p, Integral n) => p -> n -> (p, Int)
getUnitZ p
c p
d
           in p -> (p, Int) -> (p, p, Int)
go (p
m p -> p -> p
forall a. Num a => a -> a -> a
* (p
p p -> p -> p
forall a. Integral a => a -> a -> a
`div` p
c)p -> Int -> p
forall a b. (Num a, Integral b) => a -> b -> a
^Int
vd') (p
d', Int
vd Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
vd')
    (p
n, Int
vn) = p -> p -> (p, Int)
forall p n. (Integral p, Integral n) => p -> n -> (p, Int)
getUnitZ p
p (Ratio p -> p
forall a. Ratio a -> a
numerator Ratio p
x)
    (p
n', p
d, Int
vd) = p -> (p, Int) -> (p, p, Int)
go p
1 ((p, Int) -> (p, p, Int)) -> (p, Int) -> (p, p, Int)
forall a b. (a -> b) -> a -> b
$ p -> p -> (p, Int)
forall p n. (Integral p, Integral n) => p -> n -> (p, Int)
getUnitZ p
p (Ratio p -> p
forall a. Ratio a -> a
denominator Ratio p
x)

-----------------------------------------------------------

{- | For a given list extracts prefix and a cycle, limiting length of prefix and cycle by @len@.
Uses the modified tortiose-and-hare method. -}
findCycle :: Eq a => Int -> [a] -> Maybe ([a], [a])
findCycle :: Int -> [a] -> Maybe ([a], [a])
findCycle Int
len [a]
lst =
  (([a], [a]) -> Bool) -> [([a], [a])] -> Maybe ([a], [a])
forall (t :: Type -> Type) a.
Foldable t =>
(a -> Bool) -> t a -> Maybe a
find ([a], [a]) -> Bool
test [ ([a], [a]) -> ([a], [a])
forall a. Eq a => ([a], [a]) -> ([a], [a])
rollback ([a]
a, [a]
c)
            | ([a]
a, [a]
cs) <- Int -> [a] -> [([a], [a])]
forall a. Eq a => Int -> [a] -> [([a], [a])]
tortoiseHare Int
len [a]
lst
            , [a]
c <- Int -> [[a]] -> [[a]]
forall a. Int -> [a] -> [a]
take Int
1 [ [a]
c | [a]
c <- [[a]] -> [[a]]
forall a. [a] -> [a]
tail ([a] -> [[a]]
forall a. [a] -> [[a]]
inits [a]
cs)
                              , [Bool] -> Bool
forall (t :: Type -> Type). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> [a] -> [a] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==) [a]
cs ([a] -> [a]
forall a. [a] -> [a]
cycle [a]
c) ] ]
  where
    rollback :: ([a], [a]) -> ([a], [a])
rollback ([a]
as, [a]
bs) = ([a], [a]) -> ([a], [a])
go ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
as, [a] -> [a]
forall a. [a] -> [a]
reverse [a]
bs)
      where
        go :: ([a], [a]) -> ([a], [a])
go =
          \case
            ([], [a]
ys) -> ([], [a] -> [a]
forall a. [a] -> [a]
reverse [a]
ys)
            (a
x:[a]
xs, a
y:[a]
ys)
              | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y -> ([a], [a]) -> ([a], [a])
go ([a]
xs, [a]
ys [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x])
            ([a]
xs, [a]
ys) -> ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
xs, [a] -> [a]
forall a. [a] -> [a]
reverse [a]
ys)
    test :: ([a], [a]) -> Bool
test ([a]
_, []) = Bool
False
    test ([a]
pref, [a]
c) = [Bool] -> Bool
forall (t :: Type -> Type). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> [a] -> [a] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==) (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
len [a]
lst) ([a]
pref [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a] -> [a]
forall a. [a] -> [a]
cycle [a]
c)

tortoiseHare :: Eq a => Int -> [a] -> [([a], [a])]
tortoiseHare :: Int -> [a] -> [([a], [a])]
tortoiseHare Int
l [a]
x =
  (([a], ([a], [a])) -> ([a], [a]))
-> [([a], ([a], [a]))] -> [([a], [a])]
forall a b. (a -> b) -> [a] -> [b]
map ((([a], [a]) -> [a]) -> ([a], ([a], [a])) -> ([a], [a])
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap ([a], [a]) -> [a]
forall a b. (a, b) -> a
fst) ([([a], ([a], [a]))] -> [([a], [a])])
-> [([a], ([a], [a]))] -> [([a], [a])]
forall a b. (a -> b) -> a -> b
$
  (([a], ([a], [a])) -> Bool)
-> [([a], ([a], [a]))] -> [([a], ([a], [a]))]
forall a. (a -> Bool) -> [a] -> [a]
filter (\([a]
_, ([a]
a, [a]
b)) -> [[a]] -> [a]
forall (t :: Type -> Type) a. Foldable t => t [a] -> [a]
concat (Int -> [a] -> [[a]]
forall a. Int -> a -> [a]
replicate Int
3 [a]
a) [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
b) ([([a], ([a], [a]))] -> [([a], ([a], [a]))])
-> [([a], ([a], [a]))] -> [([a], ([a], [a]))]
forall a b. (a -> b) -> a -> b
$
  [[a]] -> [([a], [a])] -> [([a], ([a], [a]))]
forall a b. [a] -> [b] -> [(a, b)]
zip ([a] -> [[a]]
forall a. [a] -> [[a]]
inits [a]
x) ([([a], [a])] -> [([a], ([a], [a]))])
-> [([a], [a])] -> [([a], ([a], [a]))]
forall a b. (a -> b) -> a -> b
$
  (Int -> [a] -> ([a], [a])) -> [Int] -> [[a]] -> [([a], [a])]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt [Int
1 .. Int
l] ([[a]] -> [([a], [a])]) -> [[a]] -> [([a], [a])]
forall a b. (a -> b) -> a -> b
$ (Int -> [a] -> [a]) -> [Int] -> [[a]] -> [[a]]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take [Int
4, Int
8 ..] ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ [a] -> [[a]]
forall a. [a] -> [[a]]
tails [a]
x

 
{- | Returns p-adic solutions (if any) of the equation \(f(x) = 0\) using Hensel lifting method.
First, solutions of \(f(x) = 0\ \mathrm{mod}\ p\) are found, then by Newton's method this solution is get lifted to p-adic number (up to specified precision).

Examples:

>>> henselLifting (\x -> x*x - 2) (\x -> 2*x) :: [Z 7]
[…64112011266421216213,…02554655400245450454]
>>> henselLifting (\x -> x*x - x) (\x -> 2*x-1) :: [Q 10]
[0,1,…92256259918212890625,…07743740081787109376]
-}
henselLifting ::
     (Eq n, PadicNum n, KnownRadix p, Digit n ~ Mod p)
  => (n -> n) -- ^ Function to be vanished.
  -> (n -> n) -- ^ Derivative of the function.
  -> [n] -- ^ The result.
henselLifting :: (n -> n) -> (n -> n) -> [n]
henselLifting n -> n
f n -> n
f' = [n]
res
  where
    pr :: Int
pr = n -> Int
forall n i. (PadicNum n, Integral i) => n -> i
precision ([n] -> n
forall a. [a] -> a
head [n]
res)
    res :: [n]
res = (n -> n) -> [n]
forall n (p :: Nat).
(PadicNum n, KnownRadix p, Digit n ~ Mod p) =>
(n -> n) -> [n]
findSolutionMod n -> n
f [n] -> (n -> [n]) -> [n]
forall (m :: Type -> Type) a b. Monad m => m a -> (a -> m b) -> m b
>>= Int -> (n -> n) -> (n -> n) -> n -> [n]
forall n. PadicNum n => Int -> (n -> n) -> (n -> n) -> n -> [n]
newtonsMethod Int
pr n -> n
f n -> n
f'

{- | Returns solution of the equation \(f(x) = 0\ \mathrm{mod}\ p\) in p-adics.
Used as a first step if `henselLifting` function and is usefull for introspection.

>>> findSolutionMod (\x -> x*x - 2) :: [Z 7]
[3,4]
>>> findSolutionMod (\x -> x*x - x) :: [Q 10]
[0.0,1.0,5.0,6.0]
-}
findSolutionMod :: (PadicNum n, KnownRadix p, Digit n ~ Mod p)
                => (n -> n) -> [n]
findSolutionMod :: (n -> n) -> [n]
findSolutionMod n -> n
f = [ Digit n -> n
forall n. PadicNum n => Digit n -> n
fromMod Mod p
Digit n
d | Mod p
d <- [Mod p
0..], Mod p -> Mod p
fm Mod p
d Mod p -> Mod p -> Bool
forall a. Eq a => a -> a -> Bool
== Mod p
0 ]
  where
    fm :: Mod p -> Mod p
fm = n -> Mod p
forall n. PadicNum n => n -> Digit n
firstDigit (n -> Mod p) -> (Mod p -> n) -> Mod p -> Mod p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. n -> n
f (n -> n) -> (Mod p -> n) -> Mod p -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Mod p -> n
forall n. PadicNum n => Digit n -> n
fromMod
    fromMod :: Digit n -> n
fromMod Digit n
x = [Digit n] -> n
forall n. PadicNum n => [Digit n] -> n
fromDigits [Digit n
x]

newtonsMethod
  :: PadicNum n => Int -> (n -> n) -> (n -> n) -> n -> [n]
newtonsMethod :: Int -> (n -> n) -> (n -> n) -> n -> [n]
newtonsMethod Int
n n -> n
f n -> n
f' = Int -> (n -> [n]) -> n -> [n]
forall a (m :: Type -> Type).
(Eq a, Monad m) =>
Int -> (a -> m a) -> a -> m a
iterateM Int
n n -> [n]
step
  where
    step :: n -> [n]
step n
x = do
      n
invf' <- Maybe n -> [n]
forall a. Maybe a -> [a]
maybeToList (n -> Maybe n
forall n. PadicNum n => n -> Maybe n
inverse (n -> n
f' n
x))
      n -> [n]
forall (m :: Type -> Type) a. Monad m => a -> m a
return (n
x n -> n -> n
forall a. Num a => a -> a -> a
- n -> n
f n
x n -> n -> n
forall a. Num a => a -> a -> a
* n
invf')  

iterateM :: (Eq a, Monad m) => Int -> (a -> m a) -> a -> m a
iterateM :: Int -> (a -> m a) -> a -> m a
iterateM Int
n a -> m a
f = Int -> a -> m a
go Int
n
  where
    go :: Int -> a -> m a
go Int
0 a
x = a -> m a
forall (f :: Type -> Type) a. Applicative f => a -> f a
pure a
x
    go Int
i a
x = do
      a
y <- a -> m a
f a
x
      if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y then a -> m a
forall (f :: Type -> Type) a. Applicative f => a -> f a
pure a
x else Int -> a -> m a
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) a
y

{- | Returns a list of m-th roots of unity.  -}
unityRoots :: (KnownRadix p, PadicNum n, Digit n ~ Mod p) => Integer -> [n]
unityRoots :: Integer -> [n]
unityRoots Integer
m = (n -> n) -> (n -> n) -> [n]
forall n (p :: Nat).
(Eq n, PadicNum n, KnownRadix p, Digit n ~ Mod p) =>
(n -> n) -> (n -> n) -> [n]
henselLifting n -> n
f n -> n
f'
  where
    f :: n -> n
f n
x = n
xn -> Integer -> n
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
m n -> n -> n
forall a. Num a => a -> a -> a
- n
1
    f' :: n -> n
f' n
x = Integer -> n
forall a. Num a => Integer -> a
fromInteger Integer
m n -> n -> n
forall a. Num a => a -> a -> a
* n
x n -> Integer -> n
forall a b. (Num a, Integral b) => a -> b -> a
^ (Integer
m Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)    

pSignum :: (PadicNum n, KnownRadix p, Digit n ~ Mod p) => n -> n
pSignum :: n -> n
pSignum n
n
  | Mod p
Digit n
d0 Mod p -> Mod p -> Bool
forall a. Eq a => a -> a -> Bool
== Mod p
0 = n
0
  | Mod p
Digit n
d0Mod p -> Integer -> Mod p
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
p Mod p -> Mod p -> Bool
forall a. Eq a => a -> a -> Bool
/= Mod p
Digit n
d0 = n
1
  | Bool
otherwise = case [n]
res of
      [] -> n
1
      n
x:[n]
_ -> n
x
  where
    d0 :: Digit n
d0 = n -> Digit n
forall n. PadicNum n => n -> Digit n
firstDigit n
n
    p :: Integer
p = n -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
radix n
n
    pr :: Int
pr = n -> Int
forall n i. (PadicNum n, Integral i) => n -> i
precision n
n
    res :: [n]
res = Int -> (n -> n) -> (n -> n) -> n -> [n]
forall n. PadicNum n => Int -> (n -> n) -> (n -> n) -> n -> [n]
newtonsMethod Int
pr (\n
x -> n
xn -> Integer -> n
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) n -> n -> n
forall a. Num a => a -> a -> a
- n
1) (\n
x -> Integer -> n
forall a. Num a => Integer -> a
fromInteger (Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)n -> n -> n
forall a. Num a => a -> a -> a
*n
xn -> Integer -> n
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
pInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
2)) ([Digit n] -> n
forall n. PadicNum n => [Digit n] -> n
fromDigits [Digit n
d0])
    
-------------------------------------------------------------

{- | Returns p-adic exponent function, calculated via Taylor series.
For given radix \(p\) converges for numbers which satisfy inequality:

\[|x|_p < p^\frac{1}{1-p}.\]

-}
pExp :: (Eq n, PadicNum n, Fractional n) => n -> Either String n
pExp :: n -> Either String n
pExp n
x | Rational -> Double
forall a. Fractional a => Rational -> a
fromRational (n -> Rational
forall i n. (Integral i, PadicNum n) => n -> Ratio i
norm n
x) Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
p Double -> Double -> Double
forall a. Floating a => a -> a -> a
** (-Double
1Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/(Double
pDouble -> Double -> Double
forall a. Num a => a -> a -> a
-Double
1)) = String -> Either String n
forall a b. a -> Either a b
Left String
"exp does not converge!"
       | Bool
otherwise = Integer -> n -> n -> n -> Either String n
go (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* n -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
precision n
x) n
0 n
1 n
1
  where
    p :: Double
p = Integer -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (n -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
radix n
x)
    go :: Integer -> n -> n -> n -> Either String n
go Integer
n n
s n
t n
i
      | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = String -> Either String n
forall a b. a -> Either a b
Left String
"exp failed to converge within precision!"
      | n
t n -> n -> Bool
forall a. Eq a => a -> a -> Bool
== n
0 = n -> Either String n
forall a b. b -> Either a b
Right n
s
      | Bool
otherwise = Integer -> n -> n -> n -> Either String n
go (Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) (n
s n -> n -> n
forall a. Num a => a -> a -> a
+ n
t) (n
tn -> n -> n
forall a. Num a => a -> a -> a
*n
xn -> n -> n
forall a. Fractional a => a -> a -> a
/n
i) (n
in -> n -> n
forall a. Num a => a -> a -> a
+n
1)

{- | Returns p-adic logarithm function, calculated via Taylor series.
For given radix \(p\) converges for numbers which satisfy inequality:

\[|x|_p < 1.\]

-}
pLog :: (Eq b, PadicNum b, Fractional b) => b -> Either String b
pLog :: b -> Either String b
pLog b
x' | Rational -> Double
forall a. Fractional a => Rational -> a
fromRational (b -> Rational
forall i n. (Integral i, PadicNum n) => n -> Ratio i
norm (b
x' b -> b -> b
forall a. Num a => a -> a -> a
- b
1)) Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>= Double
1 = String -> Either String b
forall a b. a -> Either a b
Left String
"log does not converge!"
        | Bool
otherwise = b -> Either String b
forall n. (Fractional n, PadicNum n) => n -> Either String n
f (b
x' b -> b -> b
forall a. Num a => a -> a -> a
- b
1)
  where
    f :: n -> Either String n
f n
x = Integer -> n -> n -> n -> Either String n
go (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* n -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
precision n
x) n
0 n
x n
1
      where
        nx :: n
nx = n -> n
forall a. Num a => a -> a
negate n
x
        go :: Integer -> n -> n -> n -> Either String n
go Integer
n n
s n
t n
i
          | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = String -> Either String n
forall a b. a -> Either a b
Left String
"log failed to converge within precision!"
          | n
t n -> n -> Bool
forall a. Eq a => a -> a -> Bool
== n
0 = n -> Either String n
forall a b. b -> Either a b
Right n
s
          | Bool
otherwise = Integer -> n -> n -> n -> Either String n
go (Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) (n
s n -> n -> n
forall a. Num a => a -> a -> a
+ n
tn -> n -> n
forall a. Fractional a => a -> a -> a
/n
i) (n
nxn -> n -> n
forall a. Num a => a -> a -> a
*n
t) (n
in -> n -> n
forall a. Num a => a -> a -> a
+n
1)

{- | Returns p-adic hyperbolic sine function, calculated via Taylor series.
For given radix \(p\) converges for numbers which satisfy inequality:

\[|x|_p < p^\frac{1}{1-p}.\]

-}
pSinh :: (PadicNum b, Fractional b) => b -> Either [Char] b
pSinh :: b -> Either String b
pSinh b
x
  | Rational -> Double
forall a. Fractional a => Rational -> a
fromRational (b -> Rational
forall i n. (Integral i, PadicNum n) => n -> Ratio i
norm b
x) Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
p Double -> Double -> Double
forall a. Floating a => a -> a -> a
** (-Double
1Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/(Double
pDouble -> Double -> Double
forall a. Num a => a -> a -> a
-Double
1)) = String -> Either String b
forall a b. a -> Either a b
Left String
"sinh does not converge!"
  | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
precision b
x) b
0 b
x b
2
  where
    p :: Double
p = Integer -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
radix b
x)
    x2 :: b
x2 = b
xb -> b -> b
forall a. Num a => a -> a -> a
*b
x
    go :: Integer -> b -> b -> b -> Either String b
go Integer
n b
s b
t b
i
      | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = String -> Either String b
forall a b. a -> Either a b
Left String
"sinh failed to converge within precision!"
      | b
t b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 = b -> Either String b
forall a b. b -> Either a b
Right b
s
      | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) (b
s b -> b -> b
forall a. Num a => a -> a -> a
+ b
t) (b
tb -> b -> b
forall a. Num a => a -> a -> a
*b
x2b -> b -> b
forall a. Fractional a => a -> a -> a
/(b
ib -> b -> b
forall a. Num a => a -> a -> a
*(b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
1))) (b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
2)

{- | Returns p-adic inverse hyperbolic sine function, calculated as

\[\mathrm{sinh}^{ -1} x = \log(x + \sqrt{x^2+1})\]

with convergence, corresponding to `pLog` and `pPow` functions.
-}
pAsinh :: (PadicNum b, Fractional b) => b -> Either String b
pAsinh :: b -> Either String b
pAsinh b
x = do b
y <- b -> b -> Either String b
forall p. (PadicNum p, Fractional p) => p -> p -> Either String p
pPow (b
xb -> b -> b
forall a. Num a => a -> a -> a
*b
x b -> b -> b
forall a. Num a => a -> a -> a
+ b
1) (b
1b -> b -> b
forall a. Fractional a => a -> a -> a
/b
2)
              b -> Either String b
forall b. (Eq b, PadicNum b, Fractional b) => b -> Either String b
pLog (b
x b -> b -> b
forall a. Num a => a -> a -> a
+ b
y)

{- | Returns p-adic hyperbolic cosine function, calculated via Taylor series.
For given radix \(p\) converges for numbers which satisfy inequality:

\[|x|_p < p^\frac{1}{1-p}.\]

-}
pCosh :: (PadicNum b, Fractional b) => b -> Either [Char] b
pCosh :: b -> Either String b
pCosh b
x
  | Rational -> Double
forall a. Fractional a => Rational -> a
fromRational (b -> Rational
forall i n. (Integral i, PadicNum n) => n -> Ratio i
norm b
x) Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
p Double -> Double -> Double
forall a. Floating a => a -> a -> a
** (-Double
1Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/(Double
pDouble -> Double -> Double
forall a. Num a => a -> a -> a
-Double
1)) = String -> Either String b
forall a b. a -> Either a b
Left String
"cosh does not converge!"
  | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
precision b
x) b
0 b
1 b
1
  where
    p :: Double
p = Integer -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
radix b
x)
    x2 :: b
x2 = b
xb -> b -> b
forall a. Num a => a -> a -> a
*b
x
    go :: Integer -> b -> b -> b -> Either String b
go Integer
n b
s b
t b
i
      | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = String -> Either String b
forall a b. a -> Either a b
Left String
"cosh failed to converge within precision!"
      | b
t b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 = b -> Either String b
forall a b. b -> Either a b
Right b
s
      | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) (b
s b -> b -> b
forall a. Num a => a -> a -> a
+ b
t) (b
tb -> b -> b
forall a. Num a => a -> a -> a
*b
x2b -> b -> b
forall a. Fractional a => a -> a -> a
/(b
ib -> b -> b
forall a. Num a => a -> a -> a
*(b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
1))) (b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
2)

{- | Returns p-adic inverse hyperbolic cosine function, calculated as

\[\mathrm{cosh}^{ -1}\ x = \log(x + \sqrt{x^2-1}),\]

with convergence, corresponding to `pLog` and `pPow` functions.

-}
pAcosh :: (PadicNum b, Fractional b) => b -> Either String b
pAcosh :: b -> Either String b
pAcosh b
x = do b
y <- b -> b -> Either String b
forall p. (PadicNum p, Fractional p) => p -> p -> Either String p
pPow (b
xb -> b -> b
forall a. Num a => a -> a -> a
*b
x b -> b -> b
forall a. Num a => a -> a -> a
- b
1) (b
1b -> b -> b
forall a. Fractional a => a -> a -> a
/b
2)
              b -> Either String b
forall b. (Eq b, PadicNum b, Fractional b) => b -> Either String b
pLog (b
x b -> b -> b
forall a. Num a => a -> a -> a
+ b
y)

{- | Returns p-adic hyperbolic tan function, calculated as

\[\mathrm{tanh}\ x = \frac{\mathrm{sinh}\ x}{\mathrm{cosh}\ x},\]

with convergence, corresponding to `pSinh` and `pCosh` functions.
-}
pTanh :: (Fractional b, PadicNum b) => b -> Either [Char] b
pTanh :: b -> Either String b
pTanh b
x = b -> b -> b
forall a. Fractional a => a -> a -> a
(/) (b -> b -> b) -> Either String b -> Either String (b -> b)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> b -> Either String b
forall b. (PadicNum b, Fractional b) => b -> Either String b
pSinh b
x Either String (b -> b) -> Either String b -> Either String b
forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> b -> Either String b
forall b. (PadicNum b, Fractional b) => b -> Either String b
pCosh b
x

{- | Returns p-adic inverse hyperbolic tan function, calculated as

\[\mathrm{tanh}^{ -1 }\ x = \frac{1}{2} \log\left(\frac{x + 1}{x - 1}\right)\]

with convergence, corresponding to `pLog` function.
-}
pAtanh :: (PadicNum b, Fractional b) => b -> Either String b
pAtanh :: b -> Either String b
pAtanh b
x = do b
y <- b -> Either String b
forall b. (Eq b, PadicNum b, Fractional b) => b -> Either String b
pLog ((b
x b -> b -> b
forall a. Num a => a -> a -> a
+ b
1) b -> b -> b
forall a. Fractional a => a -> a -> a
/ (b
x b -> b -> b
forall a. Num a => a -> a -> a
- b
1))
              b -> Either String b
forall (m :: Type -> Type) a. Monad m => a -> m a
return (b -> Either String b) -> b -> Either String b
forall a b. (a -> b) -> a -> b
$ b
y b -> b -> b
forall a. Fractional a => a -> a -> a
/ b
2


{- | Returns p-adic hyperbolic cosine function, calculated via Taylor series.
For given radix \(p\) converges for numbers which satisfy inequality:

\[|x|_p < p^\frac{1}{1-p}.\]

-}
pSin :: (PadicNum b, Fractional b) => b -> Either [Char] b
pSin :: b -> Either String b
pSin b
x
  | Rational -> Double
forall a. Fractional a => Rational -> a
fromRational (b -> Rational
forall i n. (Integral i, PadicNum n) => n -> Ratio i
norm b
x) Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
p Double -> Double -> Double
forall a. Floating a => a -> a -> a
** (-Double
1Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/(Double
pDouble -> Double -> Double
forall a. Num a => a -> a -> a
-Double
1)) = String -> Either String b
forall a b. a -> Either a b
Left String
"sin does not converge!"
  | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
precision b
x) b
0 b
x b
2
  where
    p :: Double
p = Integer -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
radix b
x)
    x2 :: b
x2 = b -> b
forall a. Num a => a -> a
negate b
xb -> b -> b
forall a. Num a => a -> a -> a
*b
x
    go :: Integer -> b -> b -> b -> Either String b
go Integer
n b
s b
t b
i
      | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = String -> Either String b
forall a b. a -> Either a b
Left String
"sin failed to converge within precision!"
      | b
t b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 = b -> Either String b
forall a b. b -> Either a b
Right b
s
      | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) (b
s b -> b -> b
forall a. Num a => a -> a -> a
+ b
t) (b
tb -> b -> b
forall a. Num a => a -> a -> a
*b
x2b -> b -> b
forall a. Fractional a => a -> a -> a
/(b
ib -> b -> b
forall a. Num a => a -> a -> a
*(b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
1))) (b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
2)

{- | Returns p-adic cosine function, calculated via Taylor series.
For given radix \(p\) converges for numbers which satisfy inequality:

\[|x|_p < p^\frac{1}{1-p}.\]

-}
pCos :: (PadicNum b, Fractional b) => b -> Either [Char] b
pCos :: b -> Either String b
pCos b
x
  | Rational -> Double
forall a. Fractional a => Rational -> a
fromRational (b -> Rational
forall i n. (Integral i, PadicNum n) => n -> Ratio i
norm b
x) Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
> Double
p Double -> Double -> Double
forall a. Floating a => a -> a -> a
** (-Double
1Double -> Double -> Double
forall a. Fractional a => a -> a -> a
/(Double
pDouble -> Double -> Double
forall a. Num a => a -> a -> a
-Double
1)) = String -> Either String b
forall a b. a -> Either a b
Left String
"cos does not converge!"
  | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
2 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
precision b
x) b
0 b
1 b
1
  where
    p :: Double
p = Integer -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
radix b
x)
    x2 :: b
x2 = b -> b
forall a. Num a => a -> a
negate b
xb -> b -> b
forall a. Num a => a -> a -> a
*b
x
    go :: Integer -> b -> b -> b -> Either String b
go Integer
n b
s b
t b
i
      | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = String -> Either String b
forall a b. a -> Either a b
Left String
"cos failed to converge within precision!"
      | b
t b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 = b -> Either String b
forall a b. b -> Either a b
Right b
s
      | Bool
otherwise = Integer -> b -> b -> b -> Either String b
go (Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) (b
s b -> b -> b
forall a. Num a => a -> a -> a
+ b
t) (b
tb -> b -> b
forall a. Num a => a -> a -> a
*b
x2b -> b -> b
forall a. Fractional a => a -> a -> a
/(b
ib -> b -> b
forall a. Num a => a -> a -> a
*(b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
1))) (b
ib -> b -> b
forall a. Num a => a -> a -> a
+b
2)

{- | Returns p-adic arcsine function, calculated via Taylor series.
For given radix \(p\) converges for numbers which satisfy inequality:

\[|x|_p < 1.\]

-}
pAsin :: b -> Either String b
pAsin b
x | b -> Rational
forall i n. (Integral i, PadicNum n) => n -> Ratio i
norm b
x Rational -> Rational -> Bool
forall a. Ord a => a -> a -> Bool
>= Rational
1 = String -> Either String b
forall a b. a -> Either a b
Left String
"asin does not converge!"
        | Bool
otherwise = b -> Either String b
forall a b. b -> Either a b
Right (b -> Either String b) -> b -> Either String b
forall a b. (a -> b) -> a -> b
$
          [b] -> b
forall (t :: Type -> Type) a. (Foldable t, Num a) => t a -> a
sum ([b] -> b) -> [b] -> b
forall a b. (a -> b) -> a -> b
$ (b -> Bool) -> [b] -> [b]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\b
t -> b -> Int
forall n. PadicNum n => n -> Int
valuation b
t Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
pr) ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$
          Int -> [b] -> [b]
forall a. Int -> [a] -> [a]
take (Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
pr) ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$ (b -> b -> b) -> [b] -> [b] -> [b]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith b -> b -> b
forall a. Num a => a -> a -> a
(*) [b]
xs [b]
cs
  where
    pr :: Int
pr = b -> Int
forall n i. (PadicNum n, Integral i) => n -> i
precision b
x
    x2 :: b
x2 = b
xb -> b -> b
forall a. Num a => a -> a -> a
*b
x
    xs :: [b]
xs = (b -> b) -> b -> [b]
forall a. (a -> a) -> a -> [a]
iterate (b
x2 b -> b -> b
forall a. Num a => a -> a -> a
*) b
x
    cs :: [b]
cs = (b -> b -> b) -> [b] -> [b] -> [b]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith b -> b -> b
forall a. Fractional a => a -> a -> a
(/) ((b -> b -> b) -> [b] -> [b] -> [b]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith b -> b -> b
forall a. Fractional a => a -> a -> a
(/) [b]
n2f [b]
nf2) [b
2b -> b -> b
forall a. Num a => a -> a -> a
*b
nb -> b -> b
forall a. Num a => a -> a -> a
+b
1 | b
n <- Integer -> b
forall a. Num a => Integer -> a
fromInteger (Integer -> b) -> [Integer] -> [b]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [Integer
0..]]
    n2f :: [b]
n2f = (b -> b -> b) -> b -> [b] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl b -> b -> b
forall a. Num a => a -> a -> a
(*) b
1 [b
nb -> b -> b
forall a. Num a => a -> a -> a
*(b
nb -> b -> b
forall a. Num a => a -> a -> a
+b
1) | b
n <- Integer -> b
forall a. Num a => Integer -> a
fromInteger (Integer -> b) -> [Integer] -> [b]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [Integer
1,Integer
3..]]
    nf2 :: [b]
nf2 = (b -> b -> b) -> b -> [b] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl b -> b -> b
forall a. Num a => a -> a -> a
(*) b
1 [b
4b -> b -> b
forall a. Num a => a -> a -> a
*b
nb -> Integer -> b
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
2 | b
n <- Integer -> b
forall a. Num a => Integer -> a
fromInteger (Integer -> b) -> [Integer] -> [b]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> [Integer
1..]]

{- | Returns p-adic square root, calculated for odd radix via Hensel lifting,
and for \(p=2\) by recurrent product.
-}
pSqrt ::
     ( Fractional n
     , PadicNum n
     , KnownRadix p
     , Digit n ~ Mod p
     )
  => n -> [n]
pSqrt :: n -> [n]
pSqrt n
x
  | Integer -> Bool
forall a. Integral a => a -> Bool
odd (n -> Integer
forall n i. (PadicNum n, Integral i) => n -> i
radix n
x) Bool -> Bool -> Bool
&& n -> Bool
forall n (p :: Nat).
(PadicNum n, KnownRadix p, Digit n ~ Mod p) =>
n -> Bool
isSquareResidue n
x =
    (n -> n) -> (n -> n) -> [n]
forall n (p :: Nat).
(Eq n, PadicNum n, KnownRadix p, Digit n ~ Mod p) =>
(n -> n) -> (n -> n) -> [n]
henselLifting (\n
y -> n
y n -> n -> n
forall a. Num a => a -> a -> a
* n
y n -> n -> n
forall a. Num a => a -> a -> a
- n
x) (n
2 n -> n -> n
forall a. Num a => a -> a -> a
*)
  | n -> Integer
forall n. PadicNum n => n -> Integer
lifted n
x Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
3 Bool -> Bool -> Bool
&& n -> Integer
forall n. PadicNum n => n -> Integer
lifted n
x Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
8 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 =
      let r :: n
r = n -> n
forall a. (PadicNum a, Fractional a) => a -> a
pSqrt2 n
x in [n
r, -n
r]
  | Bool
otherwise = []

pSqrt2 :: (PadicNum a, Fractional a) => a -> a
pSqrt2 :: a -> a
pSqrt2 a
a = [a] -> a
forall (t :: Type -> Type) a. (Foldable t, Num a) => t a -> a
product ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$
           (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
1)
           ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take (Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*a -> Int
forall n i. (PadicNum n, Integral i) => n -> i
precision a
a)
           ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ a -> [a]
forall t. Fractional t => t -> [t]
go ((a
a a -> a -> a
forall a. Num a => a -> a -> a
- a
1) a -> a -> a
forall a. Fractional a => a -> a -> a
/ a
8)
  where
    go :: t -> [t]
go t
x = (t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
4t -> t -> t
forall a. Num a => a -> a -> a
*t
x) t -> [t] -> [t]
forall a. a -> [a] -> [a]
: t -> [t]
go ((-t
2)t -> t -> t
forall a. Num a => a -> a -> a
*(t
x t -> t -> t
forall a. Fractional a => a -> a -> a
/ (t
1 t -> t -> t
forall a. Num a => a -> a -> a
+ t
4t -> t -> t
forall a. Num a => a -> a -> a
*t
x))t -> Integer -> t
forall a b. (Num a, Integral b) => a -> b -> a
^Integer
2)

{- | Exponentiation for p-adic numbers, calculated as

\[ x^y = e^{y \log x}, \]

with convergence, corresponding to `pExp` and `pLog` functions.
-}
pPow :: (PadicNum p, Fractional p) => p -> p -> Either String p
pPow :: p -> p -> Either String p
pPow p
x p
y = case p -> Either String p
forall b. (Eq b, PadicNum b, Fractional b) => b -> Either String b
pLog p
x Either String p -> (p -> Either String p) -> Either String p
forall (m :: Type -> Type) a b. Monad m => m a -> (a -> m b) -> m b
>>= \p
z -> p -> Either String p
forall b. (Eq b, PadicNum b, Fractional b) => b -> Either String b
pExp (p
zp -> p -> p
forall a. Num a => a -> a -> a
*p
y) of
      Right p
res -> p -> Either String p
forall a b. b -> Either a b
Right p
res
      Left String
_ -> String -> Either String p
forall a b. a -> Either a b
Left String
"exponentiation doesn't converge!"

{- | Returns @True@ for p-adics with square residue as a first digit.
-}
isSquareResidue :: (PadicNum n, KnownRadix p, Digit n ~ Mod p) => n -> Bool
isSquareResidue :: n -> Bool
isSquareResidue n
x = (Mod p -> Bool) -> [Mod p] -> Bool
forall (t :: Type -> Type) a.
Foldable t =>
(a -> Bool) -> t a -> Bool
any (\Mod p
m -> Mod p
mMod p -> Mod p -> Mod p
forall a. Num a => a -> a -> a
*Mod p
m Mod p -> Mod p -> Bool
forall a. Eq a => a -> a -> Bool
== n -> Digit n
forall n. PadicNum n => n -> Digit n
firstDigit n
x) [Mod p
0..]