nimber 0.1 → 0.1.1

raw patch · 2 files changed

+12/−29 lines, 2 files

Files

• Data/Nimber.hs +5/−22
• nimber.cabal +7/−7

@@ -5,7 +5,6 @@ -- very, very, very slow for n >= 65535. module Data.Nimber (                Nimber(fromNimber),-               toNimber, nimRecip ) where @@ -15,13 +14,11 @@ import Data.Ratio import Control.Monad import qualified Data.MemoCombinators as Memo-import qualified Data.Set as S newtype Nimber = Nimber {       fromNimber :: Integer } deriving (Eq, Ord) -memoNimber :: (Nimber -> r) -> Nimber -> r-memoNimber = Memo.wrap toNimber fromNimber Memo.integral+memoNimber = Memo.wrap fromInteger fromNimber Memo.integral  -- | cast any non-negative Integer into a Nimber toNimber :: Integer -> Nimber@@ -40,7 +37,7 @@ instance Num Nimber where     abs = id     negate = id-    (+) (Nimber x) (Nimber y) = toNimber (x `xor` y)+    (+) (Nimber x) (Nimber y) = fromInteger (x `xor` y)     signum 0 =  0     signum _ =  1     fromInteger = toNimber@@ -59,15 +56,14 @@                   pow2mult [0] = 1                   pow2mult [1] = 2                   pow2mult (0:xs) = pow2mult xs-                  pow2mult (1:xs) = toNimber $ 2^(2^(length xs)) * (fromNimber $ pow2mult xs)+                  pow2mult (1:xs) = fromInteger $ 2^(2^(length xs)) * (fromNimber $ pow2mult xs)                   pow2mult (x:xs) = pow2mult (x-1:xs) + pow2mult (x-2:(map (+1) xs))         -- bitProduct combines lists of powers of 2 by zero-padding the shorter list:         -- bitProduct [1, 0, 2, 1] [1, 3] = [1, 0, 3, 4]         bitProduct xs ys             | lx == ly = zipWith (+) xs ys             | lx < ly = bitProduct ys xs-            | lx > ly = zipWith (+) xs (replicate (lx - ly) 0 ++ ys)-            | otherwise = error "trichotomy violation"+            | otherwise = zipWith (+) xs (replicate (lx - ly) 0 ++ ys)             where lx = length xs                   ly = length ys      @@ -77,17 +73,4 @@     -- for 65536 <= n <= 4294967295.     recip = memoNimber recip' where         recip' a = fromJust $ find (\n -> n * a == 1) [1..]-    fromRational r = (toNimber $ numerator r) / (toNimber $ denominator r)--{-|-  Find the reciprocal of a nimber from the definition.-  This the very slow, original definition version.-  It's only here because I like it, really.--}-nimRecip :: Nimber -> Nimber-nimRecip = memoNimber nimRecip' where -    nimRecip' a =  mex . S.toList $ fixedPoint enlarge (S.fromList [0]) where-	fixedPoint f x = fromJust $ find (\x -> f x == x) $ iterate f x-        mex xs = fromJust $ find (`notElem` xs) [0..]-        enlarge xs = xs `S.union` (S.fromList (liftM2 f [1 .. pred a] (S.toList xs)))-        f a' b = (1 + (a' + a) * b) * (nimRecip a')+    fromRational r = (fromInteger $ numerator r) / (fromInteger $ denominator r)

@@ -1,20 +1,20 @@ Name:               nimber-Version:            0.1+Version:            0.1.1 Synopsis:           An implementation of (finite) nimbers Description:        This library provides a method to do arithmetic on-		            nimbers, which may be considered an alternative field-			        over the non-negative integers (the general case of-			        transfinite ordinal nimbers is not implementented.)+                    nimbers, which may be considered an alternative field+                    over the non-negative integers (the general case of+                    transfinite ordinal nimbers is not implementented.)                     Note that division is extremely slow at this point,                     due to the lack of a closed-form implementation.-License:		    BSD3+License:            BSD3 License-file:       LICENSE Author:	            Patrick Hurst-Maintainer:	        phurst@mit.edu+Maintainer:         phurst@mit.edu Build-Type:         Simple Cabal-Version:      >=1.2 Stability:          stable-Category:            Math+Category:           Math  Library    Build-Depends:   base >= 2 && < 4, data-memocombinators, containers