{-# OPTIONS_GHC -Wall -fwarn-tabs #-}
{-# LANGUAGE BangPatterns #-}
module Math.Combinatorics.Exact.Factorial (factorial) where
import Data.Bits
factorial :: (Integral a, Bits a) => Int -> a
factorial :: Int -> a
factorial Int
n
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = a
0
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2 = a
1
| Bool
otherwise = Int -> Int -> Int -> Int -> a -> a -> a -> a
forall p.
(Bits p, Integral p) =>
Int -> Int -> Int -> Int -> p -> p -> p -> p
go (Int -> Int
highestBitPosition_Int Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
0 Int
0 Int
1 a
1 a
1 a
1
where
go :: Int -> Int -> Int -> Int -> p -> p -> p -> p
go !Int
k !Int
lo !Int
s !Int
hi !p
j !p
p !p
r
| Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 =
let lo' :: Int
lo' = Int
n Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftR` Int
k
hi' :: Int
hi' = (Int
lo' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. Int
1
len :: Int
len = (Int
hi' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
hi) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
in if Int
len Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
then let
(p
q, p
j') = Int -> p -> (p, p)
forall a. Integral a => Int -> a -> (a, a)
partialProduct Int
len p
j
p' :: p
p' = p
p p -> p -> p
forall a. Num a => a -> a -> a
* p
q
r' :: p
r' = p
r p -> p -> p
forall a. Num a => a -> a -> a
* p
p'
in Int -> Int -> Int -> Int -> p -> p -> p -> p
go (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
lo' (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lo) Int
hi' p
j' p
p' p
r'
else Int -> Int -> Int -> Int -> p -> p -> p -> p
go (Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Int
lo' (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lo) Int
hi' p
j p
p p
r
| Bool
otherwise = p
r p -> Int -> p
forall a. Bits a => a -> Int -> a
`shiftL` Int
s
partialProduct :: (Integral a) => Int -> a -> (a,a)
partialProduct :: Int -> a -> (a, a)
partialProduct Int
len a
j
| Int
half Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = (,) (a -> a -> (a, a)) -> a -> a -> (a, a)
forall a b. (a -> b) -> a -> b
<!> (a
ja -> a -> a
forall a. Num a => a -> a -> a
+a
2) (a -> (a, a)) -> a -> (a, a)
forall a b. (a -> b) -> a -> b
<!> (a
ja -> a -> a
forall a. Num a => a -> a -> a
+a
2)
| Int
len Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
2 = (,) (a -> a -> (a, a)) -> a -> a -> (a, a)
forall a b. (a -> b) -> a -> b
<!> ((a
ja -> a -> a
forall a. Num a => a -> a -> a
+a
2)a -> a -> a
forall a. Num a => a -> a -> a
*(a
ja -> a -> a
forall a. Num a => a -> a -> a
+a
4)) (a -> (a, a)) -> a -> (a, a)
forall a b. (a -> b) -> a -> b
<!> (a
ja -> a -> a
forall a. Num a => a -> a -> a
+a
4)
| Bool
otherwise =
let (a
qL, a
j' ) = Int -> a -> (a, a)
forall a. Integral a => Int -> a -> (a, a)
partialProduct (Int
len Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
half) a
j
(a
qR, a
j'') = Int -> a -> (a, a)
forall a. Integral a => Int -> a -> (a, a)
partialProduct Int
half a
j'
in (,) (a -> a -> (a, a)) -> a -> a -> (a, a)
forall a b. (a -> b) -> a -> b
<!> (a
qLa -> a -> a
forall a. Num a => a -> a -> a
*a
qR) (a -> (a, a)) -> a -> (a, a)
forall a b. (a -> b) -> a -> b
<!> a
j''
where
half :: Int
half = Int
len Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
2
<!> :: (a -> b) -> a -> b
(<!>) = (a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
($!)
highestBitPosition_Int :: Int -> Int
highestBitPosition_Int :: Int -> Int
highestBitPosition_Int Int
w =
if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
15
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
7
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
3
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
0
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then Int
32 else Int
0
else Int
1
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
2 then Int
2 else Int
3
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
5
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
4 then Int
4 else Int
5
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
6 then Int
6 else Int
7
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
11
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
9
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
8 then Int
8 else Int
9
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
10 then Int
10 else Int
11
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
13
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
12 then Int
12 else Int
13
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
14 then Int
14 else Int
15
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
23
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
19
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
17
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
16 then Int
16 else Int
17
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
18 then Int
18 else Int
19
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
21
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
20 then Int
20 else Int
21
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
22 then Int
22 else Int
23
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
27
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
25
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
24 then Int
24 else Int
25
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
26 then Int
26 else Int
27
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
29
then if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
28 then Int
28 else Int
29
else if Int
w Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
30 then Int
30 else Int
31