-- |
-- Module: Symtegration.Numeric
-- Description: Numerical algorithms that are useful for implementing symbolic integration.
-- Copyright: Copyright 2025 Yoo Chung
-- License: Apache-2.0
-- Maintainer: dev@chungyc.org
--
-- This module contains numerical algorithms that are useful to more than one module,
-- ultimately for the purpose of symbolic integration of mathematical expressions.
-- By numerical algorithms here, we means algorithm that work on pure numbers and not symbols.
-- The algorithms should still return exact results.
module Symtegration.Numeric (root) where

-- | Compute the integer root to the given power.
-- I.e., find \(m\) such that \(m^k = n\).
--
-- >>> root 27 3
-- Just 3
-- >>> root (-27) 3
-- Just (-3)
-- >>> root 2 2
-- Nothing
root ::
  -- | Number \(n\) whose root we want.
  Integer ->
  -- | The power \(k\) of the root.
  Integer ->
  -- | The root \(m\).
  Maybe Integer
root :: Integer -> Integer -> Maybe Integer
root Integer
0 Integer
_ = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
0
root Integer
1 Integer
_ = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
1
root Integer
n Integer
k
  | Integer
k Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = Maybe Integer
forall a. Maybe a
Nothing
  | Ordering
GT <- Integer -> Integer -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Integer
n Integer
0 = Integer -> Integer -> Integer -> Maybe Integer
forall {t}. Integral t => t -> t -> t -> Maybe t
search Integer
n Integer
1 Integer
n
  | Ordering
LT <- Integer -> Integer -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Integer
n Integer
0, Integer -> Bool
forall a. Integral a => a -> Bool
odd Integer
k = (Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (-Integer
1)) (Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Integer -> Integer -> Integer -> Maybe Integer
forall {t}. Integral t => t -> t -> t -> Maybe t
search (-Integer
n) Integer
1 (-Integer
n)
  | Bool
otherwise = Maybe Integer
forall a. Maybe a
Nothing
  where
    search :: t -> t -> t -> Maybe t
search t
m t
low t
hi
      | t
low t -> t -> Bool
forall a. Ord a => a -> a -> Bool
>= t
hi, Ordering
c Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
/= Ordering
EQ = Maybe t
forall a. Maybe a
Nothing
      | Ordering
EQ <- Ordering
c = t -> Maybe t
forall a. a -> Maybe a
Just t
mid
      | Ordering
GT <- Ordering
c = t -> t -> t -> Maybe t
search t
m t
low (t
mid t -> t -> t
forall a. Num a => a -> a -> a
- t
1)
      | Ordering
LT <- Ordering
c = t -> t -> t -> Maybe t
search t
m (t
mid t -> t -> t
forall a. Num a => a -> a -> a
+ t
1) t
hi
      where
        mid :: t
mid = (t
low t -> t -> t
forall a. Num a => a -> a -> a
+ t
hi) t -> t -> t
forall a. Integral a => a -> a -> a
`div` t
2
        c :: Ordering
c = t -> t -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (t
mid t -> Integer -> t
forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
k) t
m