finite-field 0.6.0 → 0.7.0

raw patch · 4 files changed

+44/−73 lines, 4 filesdep +hashabledep ~type-level-numbersPVP ok

version bump matches the API change (PVP)

Dependencies added: hashable

Dependency ranges changed: type-level-numbers

API changes (from Hackage documentation)

Files

• finite-field.cabal +14/−4
• src/Data/FiniteField/PrimeField.hs +29/−3
• src/Data/FiniteField/SomeNat.hs +0/−58
• test/TestPrimeField.hs +1/−8

@@ -1,5 +1,5 @@ Name:		finite-field-Version:	0.6.0+Version:	0.7.0 License:	BSD3 License-File:	COPYING Author:		Masahiro Sakai (masahiro.sakai@gmail.com)@@ -11,8 +11,18 @@   This is an implementation of finite fields.   Currently only prime fields are supported.   .+  Changes in 0.7.0+  .+  * use extended GCD to compute reciprocals+  .+  * conform with the addition of SomeNat type to type-level-numbers-0.1.1.0.+  .   Changes in 0.6.0   .+  * add Hashable instance+  .+  Changes in 0.6.0+  .   * add allValues to FiniteField class   .   Changes in 0.5.0@@ -34,7 +44,7 @@ Library   Hs-source-dirs: src   Build-Depends:-     base >=4 && <5, template-haskell, deepseq, type-level-numbers, algebra >=3.1+     base >=4 && <5, template-haskell, deepseq, hashable, type-level-numbers >=0.1.1.0 && <0.2.0.0, algebra >=3.1   Default-Language: Haskell2010   Other-Extensions:      DeriveDataTypeable@@ -43,11 +53,11 @@      Rank2Types      GADTs      TemplateHaskell+     BangPatterns   Exposed-Modules:      Data.FiniteField      Data.FiniteField.Base      Data.FiniteField.PrimeField-     Data.FiniteField.SomeNat  Test-suite TestPrimeField   Type:              exitcode-stdio-1.0@@ -64,6 +74,6 @@       QuickCheck >=2 && <3,       finite-field,       primes,-      type-level-numbers+      type-level-numbers >=0.1.1.0 && <0.2.0.0   Default-Language: Haskell2010   Other-Extensions: TemplateHaskell

@@ -1,4 +1,4 @@-{-# LANGUAGE ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable, TemplateHaskell #-}+{-# LANGUAGE ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable, TemplateHaskell, BangPatterns #-} {-# OPTIONS_GHC -Wall #-} ----------------------------------------------------------------------------- -- |@@ -8,7 +8,7 @@ -- -- Maintainer  :  masahiro.sakai@gmail.com -- Stability   :  provisional--- Portability :  non-portable (ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable, TemplateHaskell)+-- Portability :  non-portable (ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable, TemplateHaskell, BangPatterns) -- -- Finite field of prime order p, Fp = Z/pZ. --@@ -27,6 +27,7 @@  import Prelude hiding (toInteger) import Control.DeepSeq+import Data.Hashable import Data.Ratio (denominator, numerator) import Data.Typeable import qualified Language.Haskell.TH as TH@@ -66,7 +67,13 @@  instance TL.Nat p => Fractional (PrimeField p) where   fromRational r = fromInteger (numerator r) / fromInteger (denominator r)-  recip a = a ^ (TL.toInt (undefined :: p) - 2 :: Integer)+--  recip a = a ^ (TL.toInt (undefined :: p) - 2 :: Integer)+  recip (PrimeField a) =+    case exgcd a p of+      (_, r, _) -> fromInteger r+    where+      p :: Integer+      p = TL.toInt (undefined :: p)  instance TL.Nat p => Bounded (PrimeField p) where   minBound = PrimeField 0@@ -88,6 +95,25 @@   char _    = TL.toInt (undefined :: p)   pthRoot a = a   allValues = [minBound .. maxBound]++instance TL.Nat p => Hashable (PrimeField p) where+  hashWithSalt s (PrimeField a) =+    s `hashWithSalt` (TL.toInt (undefined :: p) :: Int) `hashWithSalt` a++-- | Extended GCD algorithm+exgcd :: (Eq a, Integral a) => a -> a -> (a, a, a)+exgcd f1 f2 = f $ go f1 f2 1 0 0 1+  where+    go !r0 !r1 !s0 !s1 !t0 !t1+      | r1 == 0   = (r0, s0, t0)+      | otherwise = go r1 r2 s1 s2 t1 t2+      where+        (q, r2) = r0 `divMod` r1+        s2 = s0 - q*s1+        t2 = t0 - q*t1+    f (g,u,v)+      | g < 0 = (-g, -u, -v)+      | otherwise = (g,u,v)  -- --------------------------------------------------------------------------- 

@@ -1,58 +0,0 @@-{-# LANGUAGE ScopedTypeVariables, Rank2Types, GADTs, DeriveDataTypeable #-}-{-# OPTIONS_GHC -Wall #-}--------------------------------------------------------------------------------- |--- Module      :  Data.FiniteField.SomeNat--- Copyright   :  (c) Masahiro Sakai 2013--- License     :  BSD-style------ Maintainer  :  masahiro.sakai@gmail.com--- Stability   :  provisional--- Portability :  non-portable (ScopedTypeVariables, Rank2Types, GADTs, DeriveDataTypeable)------ Utility for type-level manipulation of natural numbers----------------------------------------------------------------------------------module Data.FiniteField.SomeNat-  ( SomeNat (..)-  , fromInteger-  ) where--import Prelude hiding (fromInteger)-import Control.DeepSeq-import Data.Bits-import Data.Typeable-import TypeLevel.Number.Nat--data SomeNat where-  SomeNat :: Nat n => n -> SomeNat-  deriving Typeable--instance Show SomeNat where-  showsPrec d (SomeNat n) = showParen (d > 10) $-    showString "fromInteger " . shows (toInt n :: Integer)--instance NFData SomeNat--fromInteger :: Integer -> SomeNat-fromInteger a | a < 0  = error "Data.FiniteField.SomeNat.fromInteger: negative number"-fromInteger 0 = SomeNat (undefined :: Z)-fromInteger a = f a (\n -> SomeNat n) (\n -> SomeNat n)-  where-    f :: Integer-      -> (forall n m. (Nat n, n ~ O m) => n -> SomeNat)-      -> (forall n m. (Nat n, n ~ I m) => n -> SomeNat)-      -> SomeNat-    f 1 _  k1 = k1 (undefined :: I Z)-    f x k0 k1 = f (x `shiftR` 1) k0' k1'-      where-        k0' :: forall n m. (Nat n, n ~ O m) => n -> SomeNat-        k0' _ =-          if testBit x 0-          then k1 (undefined :: I n)-          else k0 (undefined :: O n)-        k1' :: forall n m. (Nat n, n ~ I m) => n -> SomeNat-        k1' _ =-          if testBit x 0-          then k1 (undefined :: I n)-          else k0 (undefined :: O n)

@@ -11,8 +11,6 @@ import Data.Numbers.Primes (primes)  import Data.FiniteField-import Data.FiniteField.SomeNat (SomeNat (..))-import qualified Data.FiniteField.SomeNat as SomeNat import TypeLevel.Number.Nat  -- ----------------------------------------------------------------------@@ -121,11 +119,6 @@  -- ---------------------------------------------------------------------- -prop_intToSomeNat = do-  forAll arbitrary $ \n ->-    case SomeNat.fromInteger (abs n) of-      SomeNat m -> abs n == toInt m- case_primeFieldT = a @?= 1   where     a :: $(primeField 15485867)@@ -136,7 +129,7 @@ smallPrimes :: Gen SomeNat smallPrimes = do   i <- choose (0, 2^(16::Int))-  return $ SomeNat.fromInteger $ primes !! i+  return $ withNat SomeNat (primes !! i)  instance Nat p => Arbitrary (PrimeField p) where   arbitrary = liftM fromInteger arbitrary