shithub: MicroHs

Info  •  Files  •  Log  •  Branches

Integer: Use bit operations

--- a/lib/Data/Integer.hs

+++ b/lib/Data/Integer.hs

@@ -14,6 +14,7 @@

 import Prelude()              -- do not import Prelude

 import Primitives

 import Control.Error

+import Data.Bits

 import Data.Bool

 import Data.Char

 import Data.Enum

@@ -148,7 +149,7 @@

 -- Add 3 digits with carry

 addD :: Digit -> Digit -> Digit -> (Digit, Digit)

-addD x y z = (quot s maxD, rem s maxD)  where s = x + y + z

+addD x y z = (quotMaxD s, remMaxD s)  where s = x + y + z

 -- Invariant: xs >= ys, so result is always >= 0

 sub :: [Digit] -> [Digit] -> [Digit]

@@ -164,7 +165,7 @@

 subW :: Digit -> Digit -> Digit -> (Digit, Digit)

 subW b x y =

   let d = maxD + x - y - b

-  in (1 - quot d maxD, rem d maxD)

+  in (1 - quotMaxD d, remMaxD d)

 -- Remove trailing 0s

 trim0 :: [Digit] -> [Digit]

@@ -196,8 +197,8 @@

 mulD ci (x:xs) y = r : mulD q xs y

   where

     xy = x * y + ci

-    q = quot xy maxD

-    r = rem  xy maxD

+    q = quotMaxD xy

+    r = remMaxD xy

 mulM :: [Digit] -> [Digit] -> [Digit]

 mulM xs ys =

@@ -240,7 +241,7 @@

     qr ci []     res = (res, [ci])

     qr ci (x:xs) res = qr r xs (q:res)

       where

-        cx = ci * maxD + x

+        cx = ci `shiftL` shiftD + x

         q = quot cx y

         r = rem cx y

--- a/lib/Data/Integer_Type.hs

+++ b/lib/Data/Integer_Type.hs

@@ -22,6 +22,21 @@

   else

     error "Integer: unsupported word size"

+shiftD :: Int

+shiftD =

+  if _wordSize `primIntEQ` 64 then

+    (32::Int)

+  else if _wordSize `primIntEQ` 32 then

+    (16::Int)

+  else

+    error "Integer: unsupported word size"

+

+quotMaxD :: Digit -> Digit

+quotMaxD d = d `primWordShr` shiftD

+

+remMaxD :: Digit -> Digit

+remMaxD d = d `primWordAnd` (maxD `primWordSub` 1)

+

 -- Sadly, we also need a bunch of functions.

 _intToInteger :: Int -> Integer