{-# LANGUAGE ConstraintKinds      #-}
{-# LANGUAGE DeriveGeneric        #-}
{-# LANGUAGE FlexibleContexts     #-}
{-# LANGUAGE ScopedTypeVariables  #-}
{-# LANGUAGE TypeFamilies         #-}
{-# LANGUAGE UndecidableInstances #-}
-- |
-- Module      : Data.Array.Accelerate.Internal.BigInt
-- Copyright   : [2016..2020] Trevor L. McDonell
-- License     : BSD3
--
-- Maintainer  : Trevor L. McDonell <trevor.mcdonell@gmail.com>
-- Stability   : experimental
-- Portability : non-portable (GHC extensions)
--
-- Fixed length signed integer types
--

-- Based on the following (BSD3) projects:
--  * https://github.com/mvv/data-bword
--  * https://github.com/mvv/data-dword
--

module Data.Array.Accelerate.Internal.BigInt (

  Int96,
  Int128,
  Int160,
  Int192,
  Int224,
  Int256,
  Int512,

  BigInt(..)

) where

import Data.Bits
import Data.Int
import Data.Ratio
import Data.Word
import GHC.Generics

import Data.Array.Accelerate.Internal.BigWord
import Data.Array.Accelerate.Internal.Num2


type Int96  = BigInt  Int32  Word64
type Int128 = BigInt  Int64  Word64
type Int160 = BigInt  Int32 Word128
type Int192 = BigInt  Int64 Word128
type Int224 = BigInt  Int32 Word192
type Int256 = BigInt Int128 Word128
type Int512 = BigInt Int256 Word256


-- | Large integers of fixed size represented as separate (signed) high and
-- (unsigned) low words.
--
data BigInt    hi lo = I2 !hi !lo deriving (forall x. BigInt hi lo -> Rep (BigInt hi lo) x)
-> (forall x. Rep (BigInt hi lo) x -> BigInt hi lo)
-> Generic (BigInt hi lo)
forall x. Rep (BigInt hi lo) x -> BigInt hi lo
forall x. BigInt hi lo -> Rep (BigInt hi lo) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall hi lo x. Rep (BigInt hi lo) x -> BigInt hi lo
forall hi lo x. BigInt hi lo -> Rep (BigInt hi lo) x
$cto :: forall hi lo x. Rep (BigInt hi lo) x -> BigInt hi lo
$cfrom :: forall hi lo x. BigInt hi lo -> Rep (BigInt hi lo) x
Generic
type BigIntCtx hi lo = (hi ~ Signed hi, lo ~ Unsigned lo, Signed (Unsigned hi) ~ hi)


instance Integral (BigInt a b) => Show (BigInt a b) where
  show :: BigInt a b -> String
show = Integer -> String
forall a. Show a => a -> String
show (Integer -> String)
-> (BigInt a b -> Integer) -> BigInt a b -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BigInt a b -> Integer
forall a. Integral a => a -> Integer
toInteger


instance (Bounded a, Bounded b) => Bounded (BigInt a b) where
  minBound :: BigInt a b
minBound = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
forall a. Bounded a => a
minBound b
forall a. Bounded a => a
minBound
  maxBound :: BigInt a b
maxBound = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
forall a. Bounded a => a
maxBound b
forall a. Bounded a => a
maxBound


instance (Enum a, Num a, Eq a, Enum b, Num b, Eq b, Bounded b)
    => Enum (BigInt a b) where
  succ :: BigInt a b -> BigInt a b
succ (I2 a
hi b
lo)
    | b
lo b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
forall a. Bounded a => a
maxBound    = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> a
forall a. Enum a => a -> a
succ a
hi) b
forall a. Bounded a => a
minBound
    | Bool
otherwise         = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
hi (b -> b
forall a. Enum a => a -> a
succ b
lo)

  pred :: BigInt a b -> BigInt a b
pred (I2 a
hi b
lo)
    | b
lo b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
forall a. Bounded a => a
minBound    = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> a
forall a. Enum a => a -> a
pred a
hi) b
forall a. Bounded a => a
maxBound
    | Bool
otherwise         = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
hi (b -> b
forall a. Enum a => a -> a
pred b
lo)

  toEnum :: Int -> BigInt a b
toEnum Int
x
    | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0             = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (-a
1) (b -> b
forall a. Num a => a -> a
negate (b
1 b -> b -> b
forall a. Num a => a -> a -> a
+ Int -> b
forall a. Enum a => Int -> a
toEnum (Int -> Int
forall a. Num a => a -> a
negate (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1))))
    | Bool
otherwise         = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
0 (Int -> b
forall a. Enum a => Int -> a
toEnum Int
x)

  fromEnum :: BigInt a b -> Int
fromEnum (I2 a
0 b
lo)    = b -> Int
forall a. Enum a => a -> Int
fromEnum b
lo
  fromEnum (I2 (-1) b
lo) = Int -> Int
forall a. Num a => a -> a
negate (b -> Int
forall a. Enum a => a -> Int
fromEnum (b -> b
forall a. Num a => a -> a
negate b
lo))
  fromEnum BigInt a b
_            = String -> Int
forall a. HasCallStack => String -> a
error String
"Enum.fromEnum: bad value"


instance (Ord a, Ord b) => Ord (BigInt a b) where
  compare :: BigInt a b -> BigInt a b -> Ordering
compare (I2 a
xh b
xl) (I2 a
yh b
yl) =
    case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
xh a
yh of
      Ordering
EQ -> b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare b
xl b
yl
      Ordering
r  -> Ordering
r


instance (Eq a, Eq b) => Eq (BigInt a b) where
  I2 a
xh b
xl == :: BigInt a b -> BigInt a b -> Bool
== I2 a
yh b
yl = a
xh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
yh Bool -> Bool -> Bool
&& b
xl b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
yl
  I2 a
xh b
xl /= :: BigInt a b -> BigInt a b -> Bool
/= I2 a
yh b
yl = a
xh a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
yh Bool -> Bool -> Bool
|| b
xl b -> b -> Bool
forall a. Eq a => a -> a -> Bool
/= b
yl


instance ( Integral a, Ord a
         , Integral b, Ord b, Bounded b
         , Ord (BigInt a b)
         , Num (BigInt a b)
         , Num2 (BigInt a b)
         , Num  (BigWord (Unsigned a) b)
         , Num2 (BigWord (Unsigned a) b)
         , BigIntCtx a b
         )
    => Num (BigInt a b) where
  negate :: BigInt a b -> BigInt a b
negate (I2 a
hi b
lo)
    | b
lo b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0   = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> a
forall a. Num a => a -> a
negate a
hi) b
0
    | Bool
otherwise = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> a
forall a. Num a => a -> a
negate (a
hia -> a -> a
forall a. Num a => a -> a -> a
+a
1)) (b -> b
forall a. Num a => a -> a
negate b
lo)

  abs :: BigInt a b -> BigInt a b
abs BigInt a b
x
    | BigInt a b
x BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0     = BigInt a b -> BigInt a b
forall a. Num a => a -> a
negate BigInt a b
x
    | Bool
otherwise = BigInt a b
x

  signum :: BigInt a b -> BigInt a b
signum (I2 a
hi b
lo) =
    case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
hi a
0 of
      Ordering
LT -> a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (-a
1) b
forall a. Bounded a => a
maxBound
      Ordering
EQ -> if b
lo b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
0 then BigInt a b
0 else BigInt a b
1
      Ordering
GT -> a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
0 b
1

  I2 a
xh b
xl + :: BigInt a b -> BigInt a b -> BigInt a b
+ I2 a
yh b
yl = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
hi b
lo
    where
      lo :: b
lo = b
xl b -> b -> b
forall a. Num a => a -> a -> a
+ b
yl
      hi :: a
hi = a
xh a -> a -> a
forall a. Num a => a -> a -> a
+ a
yh a -> a -> a
forall a. Num a => a -> a -> a
+ if b
lo b -> b -> Bool
forall a. Ord a => a -> a -> Bool
< b
xl then a
1 else a
0

  BigInt a b
x * :: BigInt a b -> BigInt a b -> BigInt a b
* BigInt a b
y = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x BigWord (Unsigned a) b
-> BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a -> a
* BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y)

  fromInteger :: Integer -> BigInt a b
fromInteger Integer
x = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (Integer -> a
forall a. Num a => Integer -> a
fromInteger Integer
hi) (Integer -> b
forall a. Num a => Integer -> a
fromInteger Integer
lo)
    where
      (Integer
hi,Integer
lo) = Integer
x Integer -> Integer -> (Integer, Integer)
forall a. Integral a => a -> a -> (a, a)
`divMod` (b -> Integer
forall a. Integral a => a -> Integer
toInteger (b
forall a. Bounded a => a
maxBound::b) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1)


instance ( Integral a
         , Integral b, Bounded b
         , Integral (BigWord (Unsigned a) b)
         , Num2 (BigInt a b)
         , Num2 (BigWord (Unsigned a) b)
         , BigIntCtx a b
         )
    => Integral (BigInt a b) where
  toInteger :: BigInt a b -> Integer
toInteger (I2 a
hi b
lo) =
    a -> Integer
forall a. Integral a => a -> Integer
toInteger a
hi Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (b -> Integer
forall a. Integral a => a -> Integer
toInteger (b
forall a. Bounded a => a
maxBound::b) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ b -> Integer
forall a. Integral a => a -> Integer
toInteger b
lo

  quotRem :: BigInt a b -> BigInt a b -> (BigInt a b, BigInt a b)
quotRem BigInt a b
x BigInt a b
y =
    if BigInt a b
x BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0
      then if BigInt a b
y BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0
             then
               let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x)) (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y))
               in  (BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
q, BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
r))
             else
               let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x)) (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y)
               in  (BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
q), BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
r))
      else if BigInt a b
y BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0
             then
               let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x) (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y))
               in  (BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
q), BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
r)
             else
               let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x) (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y)
               in  (BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
q, BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
r)

  divMod :: BigInt a b -> BigInt a b -> (BigInt a b, BigInt a b)
divMod BigInt a b
x BigInt a b
y =
    if BigInt a b
x BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0
      then if BigInt a b
y BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0
             then let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x)) (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y))
                  in  (BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
q, BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
r))
             else let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x)) (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y)
                      q' :: Signed (BigWord (Unsigned a) b)
q'    = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
q)
                      r' :: Signed (BigWord (Unsigned a) b)
r'    = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
r)
                  in
                  if BigWord (Unsigned a) b
r BigWord (Unsigned a) b -> BigWord (Unsigned a) b -> Bool
forall a. Eq a => a -> a -> Bool
== BigWord (Unsigned a) b
0 then (BigInt a b
Signed (BigWord (Unsigned a) b)
q', BigInt a b
Signed (BigWord (Unsigned a) b)
r')
                            else (BigInt a b
Signed (BigWord (Unsigned a) b)
q'BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
-BigInt a b
1, BigInt a b
Signed (BigWord (Unsigned a) b)
r'BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+BigInt a b
y)
      else if BigInt a b
y BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0
             then let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x) (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y))
                      q' :: Signed (BigWord (Unsigned a) b)
q'    = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a
negate BigWord (Unsigned a) b
q)
                      r' :: Signed (BigWord (Unsigned a) b)
r'    = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
r
                  in
                  if BigWord (Unsigned a) b
r BigWord (Unsigned a) b -> BigWord (Unsigned a) b -> Bool
forall a. Eq a => a -> a -> Bool
== BigWord (Unsigned a) b
0
                    then (BigInt a b
Signed (BigWord (Unsigned a) b)
q', BigInt a b
Signed (BigWord (Unsigned a) b)
r')
                    else (BigInt a b
Signed (BigWord (Unsigned a) b)
q'BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
-BigInt a b
1, BigInt a b
Signed (BigWord (Unsigned a) b)
r'BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+BigInt a b
y)
             else let (BigWord (Unsigned a) b
q,BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, BigWord (Unsigned a) b)
forall a. Integral a => a -> a -> (a, a)
quotRem (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x) (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y)
                  in  (BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
q, BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
r)


instance (Integral (BigInt a b), Num (BigInt a b), Ord (BigInt a b))
    => Real (BigInt a b) where
  toRational :: BigInt a b -> Rational
toRational BigInt a b
x = BigInt a b -> Integer
forall a. Integral a => a -> Integer
toInteger BigInt a b
x Integer -> Integer -> Rational
forall a. Integral a => a -> a -> Ratio a
% Integer
1


instance ( Ord a
         , Num a
         , Num2 a
         , Num (BigInt a b)
         , Ord (BigInt a b)
         , Num2 (BigInt a b)
         , Bits (BigInt a b)
         , Num  (BigWord (Unsigned a) b)
         , Num2 (BigWord (Unsigned a) b)
         , Bounded (BigWord (Unsigned a) b)
         , BigIntCtx a b
         , Unsigned (Unsigned a) ~ Unsigned a
         )
    => Num2 (BigInt a b) where
  type Signed   (BigInt a b) = BigInt (Signed a) b
  type Unsigned (BigInt a b) = BigWord (Unsigned a) b
  --
  signed :: BigInt a b -> Signed (BigInt a b)
signed              = BigInt a b -> Signed (BigInt a b)
forall a. a -> a
id
  unsigned :: BigInt a b -> Unsigned (BigInt a b)
unsigned (I2 a
hi b
lo) = Unsigned a -> b -> BigWord (Unsigned a) b
forall hi lo. hi -> lo -> BigWord hi lo
W2 (a -> Unsigned a
forall w. Num2 w => w -> Unsigned w
unsigned a
hi) b
lo
  --
  addWithCarry :: BigInt a b -> BigInt a b -> (BigInt a b, Unsigned (BigInt a b))
addWithCarry BigInt a b
x BigInt a b
y = (BigInt a b
Signed (BigWord (Unsigned a) b)
c, Unsigned (BigInt a b)
BigWord (Unsigned a) b
r)
    where
      t1 :: BigWord (Unsigned a) b
t1      = if BigInt a b
x BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0 then BigWord (Unsigned a) b
forall a. Bounded a => a
maxBound else BigWord (Unsigned a) b
forall a. Bounded a => a
minBound
      t2 :: BigWord (Unsigned a) b
t2      = if BigInt a b
y BigInt a b -> BigInt a b -> Bool
forall a. Ord a => a -> a -> Bool
< BigInt a b
0 then BigWord (Unsigned a) b
forall a. Bounded a => a
maxBound else BigWord (Unsigned a) b
forall a. Bounded a => a
minBound
      (BigWord (Unsigned a) b
t3, BigWord (Unsigned a) b
r) = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, Unsigned (BigWord (Unsigned a) b))
forall w. Num2 w => w -> w -> (w, Unsigned w)
addWithCarry (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x) (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y)
      c :: Signed (BigWord (Unsigned a) b)
c       = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b
t1BigWord (Unsigned a) b
-> BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a -> a
+BigWord (Unsigned a) b
t2BigWord (Unsigned a) b
-> BigWord (Unsigned a) b -> BigWord (Unsigned a) b
forall a. Num a => a -> a -> a
+BigWord (Unsigned a) b
t3)

  mulWithCarry :: BigInt a b -> BigInt a b -> (BigInt a b, Unsigned (BigInt a b))
mulWithCarry x :: BigInt a b
x@(I2 a
xh b
_) y :: BigInt a b
y@(I2 a
yh b
_) = (BigInt a b
hi,Unsigned (BigInt a b)
BigWord (Unsigned a) b
lo)
    where
      t1 :: BigInt a b
t1        = BigInt a b -> BigInt a b
forall a. Bits a => a -> a
complement BigInt a b
y BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+ BigInt a b
1
      t2 :: BigInt a b
t2        = BigInt a b -> BigInt a b
forall a. Bits a => a -> a
complement BigInt a b
x BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+ BigInt a b
1
      (BigWord (Unsigned a) b
t3, BigWord (Unsigned a) b
lo)  = BigWord (Unsigned a) b
-> BigWord (Unsigned a) b
-> (BigWord (Unsigned a) b, Unsigned (BigWord (Unsigned a) b))
forall w. Num2 w => w -> w -> (w, Unsigned w)
mulWithCarry (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x) (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
y)
      t4 :: Signed (BigWord (Unsigned a) b)
t4        = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed BigWord (Unsigned a) b
t3
      hi :: BigInt a b
hi        = if a
xh a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0
                    then if a
yh a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0
                           then BigInt a b
Signed (BigWord (Unsigned a) b)
t4 BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+ BigInt a b
t1 BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+ BigInt a b
t2
                           else BigInt a b
Signed (BigWord (Unsigned a) b)
t4 BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+ BigInt a b
t1
                    else if a
yh a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0
                           then BigInt a b
Signed (BigWord (Unsigned a) b)
t4 BigInt a b -> BigInt a b -> BigInt a b
forall a. Num a => a -> a -> a
+ BigInt a b
t2
                           else BigInt a b
Signed (BigWord (Unsigned a) b)
t4


instance ( FiniteBits a, Integral a
         , FiniteBits b, Integral b
         , FiniteBits (BigInt a b)
         , Num2 (BigInt a b)
         , Num2 (BigWord (Unsigned a) b)
         , Bits (BigWord (Unsigned a) b)
         , Integral (Signed b), Bits (Signed b)
         , BigIntCtx a b
         )
    => Bits (BigInt a b) where
  isSigned :: BigInt a b -> Bool
isSigned BigInt a b
_   = Bool
True
  bitSize :: BigInt a b -> Int
bitSize      = BigInt a b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize
  bitSizeMaybe :: BigInt a b -> Maybe Int
bitSizeMaybe = Int -> Maybe Int
forall a. a -> Maybe a
Just (Int -> Maybe Int)
-> (BigInt a b -> Int) -> BigInt a b -> Maybe Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BigInt a b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize

  I2 a
xh b
xl .&. :: BigInt a b -> BigInt a b -> BigInt a b
.&. I2 a
yh b
yl   = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a
xh a -> a -> a
forall a. Bits a => a -> a -> a
.&. a
yh) (b
xl b -> b -> b
forall a. Bits a => a -> a -> a
.&. b
yl)
  I2 a
xh b
xl .|. :: BigInt a b -> BigInt a b -> BigInt a b
.|. I2 a
yh b
yl   = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a
xh a -> a -> a
forall a. Bits a => a -> a -> a
.|. a
yh) (b
xl b -> b -> b
forall a. Bits a => a -> a -> a
.|. b
yl)
  I2 a
xh b
xl xor :: BigInt a b -> BigInt a b -> BigInt a b
`xor` I2 a
yh b
yl = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a
xh a -> a -> a
forall a. Bits a => a -> a -> a
`xor` a
yh) (b
xl b -> b -> b
forall a. Bits a => a -> a -> a
`xor` b
yl)
  complement :: BigInt a b -> BigInt a b
complement (I2 a
hi b
lo)   = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> a
forall a. Bits a => a -> a
complement a
hi) (b -> b
forall a. Bits a => a -> a
complement b
lo)

  shiftL :: BigInt a b -> Int -> BigInt a b
shiftL (I2 a
hi b
lo) Int
x
    | Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0     = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftL a
hi Int
x a -> a -> a
forall a. Bits a => a -> a -> a
.|. b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
lo Int
y)) (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL b
lo Int
x)
    | Bool
otherwise = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (b -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral (b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL b
lo (Int -> Int
forall a. Num a => a -> a
negate Int
y))) b
0
    where
      y :: Int
y = b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x

  shiftR :: BigInt a b -> Int -> BigInt a b
shiftR (I2 a
hi b
lo) Int
x = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
hi' b
lo'
    where
      hi' :: a
hi' = a -> Int -> a
forall a. Bits a => a -> Int -> a
shiftR a
hi Int
x
      lo' :: b
lo' | Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0    = b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftL (a -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
hi) Int
y b -> b -> b
forall a. Bits a => a -> a -> a
.|. b -> Int -> b
forall a. Bits a => a -> Int -> a
shiftR b
lo Int
x
          | Bool
otherwise = b
z
      --
      y :: Int
y = b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
      z :: b
z = Signed b -> b
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Signed b -> Int -> Signed b
forall a. Bits a => a -> Int -> a
shiftR (a -> Signed b
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
hi :: Signed b) (Int -> Int
forall a. Num a => a -> a
negate Int
y))

  rotateL :: BigInt a b -> Int -> BigInt a b
rotateL BigInt a b
x Int
y = BigWord (Unsigned a) b -> Signed (BigWord (Unsigned a) b)
forall w. Num2 w => w -> Signed w
signed (BigWord (Unsigned a) b -> Int -> BigWord (Unsigned a) b
forall a. Bits a => a -> Int -> a
rotateL (BigInt a b -> Unsigned (BigInt a b)
forall w. Num2 w => w -> Unsigned w
unsigned BigInt a b
x) Int
y)
  rotateR :: BigInt a b -> Int -> BigInt a b
rotateR BigInt a b
x Int
y = BigInt a b -> Int -> BigInt a b
forall a. Bits a => a -> Int -> a
rotateL BigInt a b
x (BigInt a b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (BigInt a b
forall a. HasCallStack => a
undefined::BigInt a b) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
y)

  bit :: Int -> BigInt a b
bit Int
n
    | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0    = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (Int -> a
forall a. Bits a => Int -> a
bit Int
m) b
0
    | Bool
otherwise = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
0 (Int -> b
forall a. Bits a => Int -> a
bit Int
n)
    where
      m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)

  testBit :: BigInt a b -> Int -> Bool
testBit (I2 a
hi b
lo) Int
n
    | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0    = a -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit a
hi Int
m
    | Bool
otherwise = b -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit b
lo Int
n
    where
      m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)

  setBit :: BigInt a b -> Int -> BigInt a b
setBit (I2 a
hi b
lo) Int
n
    | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0    = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
setBit a
hi Int
m) b
lo
    | Bool
otherwise = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
hi (b -> Int -> b
forall a. Bits a => a -> Int -> a
setBit b
lo Int
n)
    where
      m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)

  clearBit :: BigInt a b -> Int -> BigInt a b
clearBit (I2 a
hi b
lo) Int
n
    | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0    = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
clearBit a
hi Int
m) b
lo
    | Bool
otherwise = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
hi (b -> Int -> b
forall a. Bits a => a -> Int -> a
clearBit b
lo Int
n)
    where
      m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)

  complementBit :: BigInt a b -> Int -> BigInt a b
complementBit (I2 a
hi b
lo) Int
n
    | Int
m Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0    = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 (a -> Int -> a
forall a. Bits a => a -> Int -> a
complementBit a
hi Int
m) b
lo
    | Bool
otherwise = a -> b -> BigInt a b
forall hi lo. hi -> lo -> BigInt hi lo
I2 a
hi (b -> Int -> b
forall a. Bits a => a -> Int -> a
complementBit b
lo Int
n)
    where
      m :: Int
m = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)

  popCount :: BigInt a b -> Int
popCount (I2 a
hi b
lo) = a -> Int
forall a. Bits a => a -> Int
popCount a
hi Int -> Int -> Int
forall a. Num a => a -> a -> a
+ b -> Int
forall a. Bits a => a -> Int
popCount b
lo


instance ( FiniteBits a
         , FiniteBits b
         , Bits (BigInt a b)
         , Num2 (BigInt a b)
         , FiniteBits (BigWord (Unsigned a) b)
         , BigIntCtx a b
         )
    => FiniteBits (BigInt a b) where
  finiteBitSize :: BigInt a b -> Int
finiteBitSize BigInt a b
_ = a -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (a
forall a. HasCallStack => a
undefined::a)
                  Int -> Int -> Int
forall a. Num a => a -> a -> a
+ b -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (b
forall a. HasCallStack => a
undefined::b)

  countLeadingZeros :: BigInt a b -> Int
countLeadingZeros  = BigWord (Unsigned a) b -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros (BigWord (Unsigned a) b -> Int)
-> (BigInt a b -> BigWord (Unsigned a) b) -> BigInt a b -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BigInt a b -> BigWord (Unsigned a) b
forall w. Num2 w => w -> Unsigned w
unsigned
  countTrailingZeros :: BigInt a b -> Int
countTrailingZeros = BigWord (Unsigned a) b -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros (BigWord (Unsigned a) b -> Int)
-> (BigInt a b -> BigWord (Unsigned a) b) -> BigInt a b -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BigInt a b -> BigWord (Unsigned a) b
forall w. Num2 w => w -> Unsigned w
unsigned