{-
	Copyright (C) 2011 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]	Exports functions involving integral powers.
-}

module Factory.Math.Power(
-- * Functions
	square,
	squaresFrom,
	cube,
	cubeRoot,
	raiseModulo
) where

-- | Mainly for convenience.
square :: Num n => n -> n
square :: n -> n
square n
x	= n
x n -> Int -> n
forall a b. (Num a, Integral b) => a -> b -> a
^ (Int
2 :: Int)	-- CAVEAT: this could be eta-reduced, but it won't then inline when called with a single argument.

{-# INLINE square #-}

-- | Just for convenience.
cube :: Num n => n -> n
cube :: n -> n
cube	= (n -> Int -> n
forall a b. (Num a, Integral b) => a -> b -> a
^ (Int
3 :: Int))

{- |
	* Iteratively generate sequential /squares/, from the specified initial value,
	based on the fact that @(x + 1)^2 = x^2 + 2 * x + 1@.

	* The initial value doesn't need to be either positive or integral.
-}
squaresFrom :: (Enum n, Num n)
	=> n		-- ^ Lower bound.
	-> [(n, n)]	-- ^ @ [(n, n^2)] @.
squaresFrom :: n -> [(n, n)]
squaresFrom n
from	= ((n, n) -> (n, n)) -> (n, n) -> [(n, n)]
forall a. (a -> a) -> a -> [a]
iterate (\(n
x, n
y) -> (n -> n
forall a. Enum a => a -> a
succ n
x, n -> n
forall a. Enum a => a -> a
succ (n -> n) -> n -> n
forall a b. (a -> b) -> a -> b
$ n
y n -> n -> n
forall a. Num a => a -> a -> a
+ n
2 n -> n -> n
forall a. Num a => a -> a -> a
* n
x)) (n
from, n -> n
forall n. Num n => n -> n
square n
from)

-- | Just for convenience.
cubeRoot :: Double -> Double
cubeRoot :: Double -> Double
cubeRoot	= (Double -> Double -> Double
forall a. Floating a => a -> a -> a
** Double -> Double
forall a. Fractional a => a -> a
recip Double
3)

{- |
	* Raise an arbitrary number to the specified positive integral power, using /modular/ arithmetic.

	* Implements exponentiation as a sequence of either /squares/ or multiplications by the base;
	<https://en.wikipedia.org/wiki/Exponentiation_by_squaring>.

	* <https://en.wikipedia.org/wiki/Modular_exponentiation>.
-}
raiseModulo :: (Integral i, Integral power, Show power)
	=> i	-- ^ Base.
	-> power
	-> i	-- ^ Modulus.
	-> i	-- ^ Result.
raiseModulo :: i -> power -> i -> i
raiseModulo i
_ power
_ i
0	= [Char] -> i
forall a. HasCallStack => [Char] -> a
error [Char]
"Factory.Math.Power.raiseModulo:\tzero modulus."
raiseModulo i
_ power
_ i
1	= i
0
raiseModulo i
_ power
0 i
modulus	= i
1 i -> i -> i
forall a. Integral a => a -> a -> a
`mod` i
modulus
raiseModulo i
base power
power i
modulus
	| i
base i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< i
0		= (i -> i -> i
forall a. Integral a => a -> a -> a
`mod` i
modulus) (i -> i) -> (i -> i) -> i -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (if power -> Bool
forall a. Integral a => a -> Bool
even power
power then i -> i
forall a. a -> a
id else i -> i
forall n. Num n => n -> n
negate) (i -> i) -> i -> i
forall a b. (a -> b) -> a -> b
$ i -> power -> i -> i
forall i power.
(Integral i, Integral power, Show power) =>
i -> power -> i -> i
raiseModulo (i -> i
forall n. Num n => n -> n
negate i
base) power
power i
modulus	-- Recurse.
	| power
power power -> power -> Bool
forall a. Ord a => a -> a -> Bool
< power
0		= [Char] -> i
forall a. HasCallStack => [Char] -> a
error ([Char] -> i) -> [Char] -> i
forall a b. (a -> b) -> a -> b
$ [Char]
"Factory.Math.Power.raiseModulo:\tnegative power; " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++ power -> [Char]
forall a. Show a => a -> [Char]
show power
power
	| i
first i -> [i] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [i
0, i
1]	= i
first
	| Bool
otherwise		= power -> i
forall t. Integral t => t -> i
slave power
power
	where
		first :: i
first	= i
base i -> i -> i
forall a. Integral a => a -> a -> a
`mod` i
modulus

		slave :: t -> i
slave t
1	= i
first
		slave t
e	= (i -> i -> i
forall a. Integral a => a -> a -> a
`mod` i
modulus) (i -> i) -> (i -> i) -> i -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (if t
r t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0 {-even-} then i -> i
forall a. a -> a
id else (i -> i -> i
forall a. Num a => a -> a -> a
* i
base)) (i -> i) -> (i -> i) -> i -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. i -> i
forall n. Num n => n -> n
square (i -> i) -> i -> i
forall a b. (a -> b) -> a -> b
$ t -> i
slave t
q {-recurse-}	where
			(t
q, t
r)	= t
e t -> t -> (t, t)
forall a. Integral a => a -> a -> (a, a)
`quotRem` t
2