{-
	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@]	Generates the constant, conceptually infinite, list of /prime-numbers/, using /Trial Division/.
-}

module Factory.Math.Implementations.Primes.TrialDivision(
-- * Functions
	trialDivision
-- ** Predicates
--	isIndivisibleBy
) where

import qualified	Control.Arrow
import qualified	Factory.Math.Power		as Math.Power
import qualified	Factory.Math.PrimeFactorisation	as Math.PrimeFactorisation
import qualified	Factory.Data.PrimeWheel		as Data.PrimeWheel

-- | Uses /Trial Division/, to determine whether the specified candidate is indivisible by all potential denominators from the specified list.
isIndivisibleBy :: Integral i
	=> i	-- ^ The numerator.
	-> [i]	-- ^ The denominators of which it must not be a multiple.
	-> Bool
isIndivisibleBy :: i -> [i] -> Bool
isIndivisibleBy i
numerator	= (i -> Bool) -> [i] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((i -> i -> Bool
forall a. Eq a => a -> a -> Bool
/= i
0) (i -> Bool) -> (i -> i) -> i -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i
numerator i -> i -> i
forall a. Integral a => a -> a -> a
`rem`)) ([i] -> Bool) -> ([i] -> [i]) -> [i] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i -> i
forall i. Integral i => i -> i
Math.PrimeFactorisation.maxBoundPrimeFactor i
numerator)

{- |
	* For each candidate, confirm indivisibility, by all /primes/ smaller than its /square-root/.

	* The candidates to sieve, are generated by a 'Data.PrimeWheel.PrimeWheel',
	of parameterised, but static, size; <https://en.wikipedia.org/wiki/Wheel_factorization>.
-}
trialDivision :: Integral prime => Data.PrimeWheel.NPrimes -> [prime]
trialDivision :: NPrimes -> [prime]
trialDivision NPrimes
0	= [prime
2, prime
3] [prime] -> [prime] -> [prime]
forall a. [a] -> [a] -> [a]
++ (prime -> Bool) -> [prime] -> [prime]
forall a. (a -> Bool) -> [a] -> [a]
filter (prime -> [prime] -> Bool
forall i. Integral i => i -> [i] -> Bool
`isIndivisibleBy` NPrimes -> [prime]
forall prime. Integral prime => NPrimes -> [prime]
trialDivision NPrimes
0 {-recurse-}) [prime
5 ..]	-- No faster than using 'Data.PrimeWheel.mkPrimeWheel 0', but apparently better space-complexity ?!
trialDivision NPrimes
wheelSize	= PrimeWheel prime -> [prime]
forall i. PrimeWheel i -> [i]
Data.PrimeWheel.getPrimeComponents PrimeWheel prime
primeWheel [prime] -> [prime] -> [prime]
forall a. [a] -> [a] -> [a]
++ [prime]
indivisible	where
	primeWheel :: PrimeWheel prime
primeWheel	= NPrimes -> PrimeWheel prime
forall i. Integral i => NPrimes -> PrimeWheel i
Data.PrimeWheel.mkPrimeWheel NPrimes
wheelSize
	candidates :: [prime]
candidates	= ((prime, [prime]) -> prime) -> [(prime, [prime])] -> [prime]
forall a b. (a -> b) -> [a] -> [b]
map (prime, [prime]) -> prime
forall a b. (a, b) -> a
fst ([(prime, [prime])] -> [prime]) -> [(prime, [prime])] -> [prime]
forall a b. (a -> b) -> a -> b
$ PrimeWheel prime -> [(prime, [prime])]
forall i. Integral i => PrimeWheel i -> [Distance i]
Data.PrimeWheel.roll PrimeWheel prime
primeWheel
	indivisible :: [prime]
indivisible	= ([prime] -> [prime] -> [prime]) -> ([prime], [prime]) -> [prime]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [prime] -> [prime] -> [prime]
forall a. [a] -> [a] -> [a]
(++) (([prime], [prime]) -> [prime])
-> (([prime], [prime]) -> ([prime], [prime]))
-> ([prime], [prime])
-> [prime]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([prime] -> [prime]) -> ([prime], [prime]) -> ([prime], [prime])
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
Control.Arrow.second (
		(prime -> Bool) -> [prime] -> [prime]
forall a. (a -> Bool) -> [a] -> [a]
filter (prime -> [prime] -> Bool
forall i. Integral i => i -> [i] -> Bool
`isIndivisibleBy` [prime]
indivisible {-recurse-})
	 ) (([prime], [prime]) -> [prime]) -> ([prime], [prime]) -> [prime]
forall a b. (a -> b) -> a -> b
$ (prime -> Bool) -> [prime] -> ([prime], [prime])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (
		prime -> prime -> Bool
forall a. Ord a => a -> a -> Bool
< prime -> prime
forall n. Num n => n -> n
Math.Power.square ([prime] -> prime
forall a. [a] -> a
head [prime]
candidates)	-- The first composite candidate, is the square of the next prime after the wheel's constituent ones.
	 ) [prime]
candidates