-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Numeric type with asymptotically faster multiplications. -- -- This numeric type internally reorders multiplications to achieve -- asymptotically faster multiplication of large numbers of small -- integers in particular. See the module docs for more detail. @package fast-mult @version 0.1.0.2 module Data.FastMult.Internal -- | FastMult is a Numeric type that can be used in any place a 'Num -- a' is required. It represents a standard integer using three -- components, which multiplied together represent the stored number: -- --
    --
  1. The number's sign
    2. --
  2. An unsigned machine word.
    3. --
  3. A (possibly empty) list of BigNats, which are the internal -- type for Integers which are too large to fit in a machine -- word.
    4. --
-- -- Each BigNat in the list has a scale. It's scale is the log base -- 2 of the number of words to store the machine word, minus 1. -- -- Note that we never store BigNats with length of only one machine word -- in this list, we instead convert them to an ordinary unsigned machine -- word and multiply them by item 2 in the list above. Only then if the -- result overflows we place them in this BigNat list. -- -- This is a few examples of "MachineWords: Scale" -- -- -- -- etc. -- -- Note this "scale" has the very nice property that multipling -- BigNats of scale x always results in a BigNat -- of scale x+1. -- -- The list of BigNats only ever contains one BigNat of -- each "scale". As the size of BigNats increases exponentially -- with scale, this list should always be relatively small. The -- BigNat list is always sorted as well, smallest to largest. -- -- When we multiply two FastMults, we merge the BigNat lists. This -- is basically a simple merge of sorted list, but with one significant -- change. Note that we said that the BigNat list cannot contain -- two BigNats of the same scale. So if find that a BigNat -- in the left hand list of the multiplication is the same scale as a -- BigNat in right hand list, we multiply these two BigNats -- to create a BigNat one "scale" larger. We then continue the -- merge, including this new BigNat. -- -- As a result, we only ever multiply numbers of the same "scale", that -- is, no more than double the length of one another. -- -- Why do we do this? Well, an ordinary product, say product -- [1..1000000], towards the end of the list involves -- multiplications of a very large number by a machine word. These take -- O(n) time. So the whole product takes O(n^2) time. -- -- If we instead did the following: -- -- 
--   product x y = product x mid * product mid y
--     mid = (x + y) div 2
--   
--   (suitible base case here)
--   
--
-- -- We find that this runs a lot faster. The reason is that with this -- approach we're minimising products involving very large numbers, and -- importantly, multiplying two n length numbers doesn't take -- O(n^2) but more like O(n*log(n)) time. For this -- reason it's better to do a few multiplication of large numbers by -- large numbers, instead of lots of multiplications of large numbers by -- small numbers. -- -- But to do this I've had to redefine product. What if you don't want to -- change the algorithm, but just want to use one that's already been -- written, perhaps inefficiently. Well this is where FastMult is -- useful. Instead of making the algorithm smarter, FastMult just -- makes numbers smarter. The numbers themselves reorder the -- multiplications so you don't have too. -- -- As well as having the advantage of speeding up existing algorithms, -- FastMult dynamically behaves differently based on what numbers -- it's actually multiplying and always maintains the invariant that -- multiplications will not be performed between numbers greater than -- twice the size each other. -- -- At this point I haven't mentioned the meaning of the FastMult -- type parameter n'. FastMult can also add paralellism -- to your multiplication algorithms. However, sparking new GHC threads -- has a cost, so we only want to do it for large multiplications. -- Multiplications of scale > n will spark a new thread, so -- n = 0 will spark new threads for any multiplication involving -- at least 3 machine words. This is probably too small, you can -- experiment with different numbers. Note that n represents the -- scale, not size, so for example setting n=4 will only spark -- threads for multiplications involving at least 33 machine words. -- -- How well parallelism works (or if it works at all) hasn't been tested -- yet however. -- -- We include an ordinary machine word in the type as an optimisation for -- single machine word numbers. This is because multiplying -- BigNats involves calling GMP using a C call, which is a large -- overhead for small multiplications. -- -- To use FastMult, all you have to do is import it's type, not -- it's implementation. If you're not interested in parallelism, just -- import FastMultSeq. -- -- For example, just compare in GHCi: -- -- 
--   product [1..100000]
--   
--
-- -- and: -- -- 
--   product [1::FastMultSeq..100000]
--   
--
-- -- and you should find the latter completes much faster. -- -- Converting to and from Integers can be done with the -- toInteger and fromInteger class methods from -- Integral and Num respectively. data FastMult (n :: Nat) [FastMult] :: KnownNat n => {-# UNPACK #-} !Sign -> {-# UNPACK #-} !Word -> !(List (BigNatWithScale n)) -> FastMult n -- | A type synonym for a fully sequential FastMult. The parameter -- is supposed to be WORD_MAX, but I couldn't find that defined, -- anyway what's important is that anything of scale smaller than -- 0xFFFFFFFF will be sequential, which is everything. type FastMultSeq = FastMult 4294967295 -- | simplify returns a FastMult the same as it's argument -- but "simplified". -- -- To explain this, consider the following for x :: FastMult: -- -- 
--   f x = (show x, x + 1)
--   
--
-- -- It will multiply out x twice, once for the addition, and once -- for show. Note that the list of BigInts in x -- is generally a small number, as only one BigInt is stored for -- each scale, and the sizes of scales increase exponentially, but there -- may be some multiplications required nevertheless. A better way to -- write this is as follows: -- -- 
--   f x = let y = simplify x in (show y, y + 1)
--   
--
-- -- This will ensure that x is multiplied out only once. -- -- Unfortunately using simplify stops your algorithms from being -- generic, so it might be better to define simplify as id with a -- rewrite rule. I'll think about this. simplify :: KnownNat n => FastMult n -> FastMult n instance GHC.Show.Show Data.FastMult.Internal.Sign instance GHC.Show.Show (Data.FastMult.Internal.BigNatWithScale n) instance GHC.TypeLits.KnownNat n => GHC.Classes.Eq (Data.FastMult.Internal.FastMult n) instance GHC.TypeLits.KnownNat n => GHC.Classes.Ord (Data.FastMult.Internal.FastMult n) instance GHC.TypeLits.KnownNat n => GHC.Enum.Enum (Data.FastMult.Internal.FastMult n) instance GHC.TypeLits.KnownNat n => GHC.Num.Num (Data.FastMult.Internal.FastMult n) instance GHC.TypeLits.KnownNat n => GHC.Real.Real (Data.FastMult.Internal.FastMult n) instance GHC.TypeLits.KnownNat n => GHC.Real.Integral (Data.FastMult.Internal.FastMult n) instance GHC.TypeLits.KnownNat n => GHC.Show.Show (Data.FastMult.Internal.FastMult n) instance GHC.TypeLits.KnownNat n => GHC.Read.Read (Data.FastMult.Internal.FastMult n) module Data.FastMult -- | FastMult is a Numeric type that can be used in any place a 'Num -- a' is required. It represents a standard integer using three -- components, which multiplied together represent the stored number: -- --
    --
  1. The number's sign
    2. --
  2. An unsigned machine word.
    3. --
  3. A (possibly empty) list of BigNats, which are the internal -- type for Integers which are too large to fit in a machine -- word.
    4. --
-- -- Each BigNat in the list has a scale. It's scale is the log base -- 2 of the number of words to store the machine word, minus 1. -- -- Note that we never store BigNats with length of only one machine word -- in this list, we instead convert them to an ordinary unsigned machine -- word and multiply them by item 2 in the list above. Only then if the -- result overflows we place them in this BigNat list. -- -- This is a few examples of "MachineWords: Scale" -- -- -- -- etc. -- -- Note this "scale" has the very nice property that multipling -- BigNats of scale x always results in a BigNat -- of scale x+1. -- -- The list of BigNats only ever contains one BigNat of -- each "scale". As the size of BigNats increases exponentially -- with scale, this list should always be relatively small. The -- BigNat list is always sorted as well, smallest to largest. -- -- When we multiply two FastMults, we merge the BigNat lists. This -- is basically a simple merge of sorted list, but with one significant -- change. Note that we said that the BigNat list cannot contain -- two BigNats of the same scale. So if find that a BigNat -- in the left hand list of the multiplication is the same scale as a -- BigNat in right hand list, we multiply these two BigNats -- to create a BigNat one "scale" larger. We then continue the -- merge, including this new BigNat. -- -- As a result, we only ever multiply numbers of the same "scale", that -- is, no more than double the length of one another. -- -- Why do we do this? Well, an ordinary product, say product -- [1..1000000], towards the end of the list involves -- multiplications of a very large number by a machine word. These take -- O(n) time. So the whole product takes O(n^2) time. -- -- If we instead did the following: -- -- 
--   product x y = product x mid * product mid y
--     mid = (x + y) div 2
--   
--   (suitible base case here)
--   
--
-- -- We find that this runs a lot faster. The reason is that with this -- approach we're minimising products involving very large numbers, and -- importantly, multiplying two n length numbers doesn't take -- O(n^2) but more like O(n*log(n)) time. For this -- reason it's better to do a few multiplication of large numbers by -- large numbers, instead of lots of multiplications of large numbers by -- small numbers. -- -- But to do this I've had to redefine product. What if you don't want to -- change the algorithm, but just want to use one that's already been -- written, perhaps inefficiently. Well this is where FastMult is -- useful. Instead of making the algorithm smarter, FastMult just -- makes numbers smarter. The numbers themselves reorder the -- multiplications so you don't have too. -- -- As well as having the advantage of speeding up existing algorithms, -- FastMult dynamically behaves differently based on what numbers -- it's actually multiplying and always maintains the invariant that -- multiplications will not be performed between numbers greater than -- twice the size each other. -- -- At this point I haven't mentioned the meaning of the FastMult -- type parameter n'. FastMult can also add paralellism -- to your multiplication algorithms. However, sparking new GHC threads -- has a cost, so we only want to do it for large multiplications. -- Multiplications of scale > n will spark a new thread, so -- n = 0 will spark new threads for any multiplication involving -- at least 3 machine words. This is probably too small, you can -- experiment with different numbers. Note that n represents the -- scale, not size, so for example setting n=4 will only spark -- threads for multiplications involving at least 33 machine words. -- -- How well parallelism works (or if it works at all) hasn't been tested -- yet however. -- -- We include an ordinary machine word in the type as an optimisation for -- single machine word numbers. This is because multiplying -- BigNats involves calling GMP using a C call, which is a large -- overhead for small multiplications. -- -- To use FastMult, all you have to do is import it's type, not -- it's implementation. If you're not interested in parallelism, just -- import FastMultSeq. -- -- For example, just compare in GHCi: -- -- 
--   product [1..100000]
--   
--
-- -- and: -- -- 
--   product [1::FastMultSeq..100000]
--   
--
-- -- and you should find the latter completes much faster. -- -- Converting to and from Integers can be done with the -- toInteger and fromInteger class methods from -- Integral and Num respectively. data FastMult (n :: Nat) -- | A type synonym for a fully sequential FastMult. The parameter -- is supposed to be WORD_MAX, but I couldn't find that defined, -- anyway what's important is that anything of scale smaller than -- 0xFFFFFFFF will be sequential, which is everything. type FastMultSeq = FastMult 4294967295 -- | simplify returns a FastMult the same as it's argument -- but "simplified". -- -- To explain this, consider the following for x :: FastMult: -- -- 
--   f x = (show x, x + 1)
--   
--
-- -- It will multiply out x twice, once for the addition, and once -- for show. Note that the list of BigInts in x -- is generally a small number, as only one BigInt is stored for -- each scale, and the sizes of scales increase exponentially, but there -- may be some multiplications required nevertheless. A better way to -- write this is as follows: -- -- 
--   f x = let y = simplify x in (show y, y + 1)
--   
--
-- -- This will ensure that x is multiplied out only once. -- -- Unfortunately using simplify stops your algorithms from being -- generic, so it might be better to define simplify as id with a -- rewrite rule. I'll think about this. simplify :: KnownNat n => FastMult n -> FastMult n