import Control.Monad (unless)

import Test.QuickCheck

import Control.Monad (unless)

import Test.QuickCheck

prop_neg a = a+a == 0

prop_neg a = a + a == 0

prop_assoc_add a b c = a+(b+c) == (a+b)+c

prop_assoc_add a b c = a + (b + c) == (a + b) + c

prop_assoc_mul a b c = a*(b*c) == (a*b)*c

prop_assoc_mul a b c = a * (b * c) == (a * b) * c

prop_distrib a b c = a*(b+c) == a*b+a*c

prop_distrib a b c = a * (b + c) == a * b + a * c
prop_recip :: Nimber -> Bool
prop_recip a = a == 0 || a / a == 1

main = check prop_neg >> check prop_assoc_add >> check prop_assoc_mul >> check prop_distrib
        where check prop = do result <- verboseCheckResult prop
                              unless (isSuccess result) exitFailure

main = check prop_neg >> check prop_assoc_add >> check prop_assoc_mul >> check prop_distrib >> check prop_recip
  where
    check prop = do
      result <- verboseCheckResult prop
      unless (isSuccess result) exitFailure

{-# OPTIONS_GHC -Wno-type-defaults #-}

import Control.Monad
import Data.Bits

import Data.Vector qualified as V
import Data.Vector.Mutable qualified as M

type Natural = Int

type Natural = Integer

instance Fractional Nimber where
  fromRational _ = error "Cannot map from field of characteristic 0 to characteristic 2"
  recip 0 = error "Divide by zero"
  recip n@Nimber {getNimber = s} =
    let m = 1 + foldl max 0 (S.unions s) -- 2^2^m is the order of the smallest field containing n
        sw i j u v = do
          a <- M.read v i
          b <- M.read v j
          if b `testBit` (2 ^ m - 1 - i)
            then do M.write v i b
                    M.write v j a
                    a' <- M.read u i
                    b' <- M.read u j
                    M.write u i b'
                    M.write u j a'
            else sw i (j + 1) u v
        pivot :: (Bits a, M.PrimMonad m) => M.MVector (M.PrimState m) a -> M.MVector (M.PrimState m) a -> Int -> m ()
        pivot u v i = do sw i i u v
                         p <- M.read u i
                         q <- M.read v i
                         forM_ [i+1..2^m-1] $ \j -> do a <- M.read v j
                                                       when (a `testBit` (2^m-1-i)) $ M.modify v (xor q) j >> M.modify u (xor p) j
        r = V.create $
          do
            tab1 <- M.generate (2 ^ m) (2 ^) -- All two-powers less than 2^2^m
            tab2 <- M.generate (2 ^ m) (nimberToNatural . (n *) . fromIntegral . (2 ^)) -- n times all two-powers less than 2^2^m
            forM_ [0..2^m-1] $ pivot tab1 tab2
            pure tab1
     in fromIntegral $ r V.! (2 ^ m - 1)

                      vector,