Safe Haskell	Safe-Inferred
Language	Haskell2010

ZkFold.Base.Algebra.Polynomials.Univariate

Synopsis

toPoly :: (Ring c, Eq c) => Vector c -> Poly c
fromPoly :: Poly c -> Vector c
data Poly c
removeZeros :: (Ring c, Eq c) => Poly c -> Poly c
scaleP :: Ring c => c -> Natural -> Poly c -> Poly c
qr :: (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c)
eea :: (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c)
lt :: Poly c -> c
deg :: Poly c -> Integer
vec2poly :: (Ring c, Eq c) => PolyVec c size -> Poly c
data PolyVec c (size :: Natural)
fromPolyVec :: PolyVec c size -> Vector c
toPolyVec :: forall c size. (Ring c, KnownNat size) => Vector c -> PolyVec c size
rewrapPolyVec :: (Vector c -> Vector c) -> PolyVec c size -> PolyVec c size
castPolyVec :: forall c size size'. (Ring c, KnownNat size, KnownNat size', Eq c) => PolyVec c size -> PolyVec c size'
evalPolyVec :: Ring c => PolyVec c size -> c -> c
scalePV :: Ring c => c -> PolyVec c size -> PolyVec c size
polyVecZero :: forall c size size'. (Field c, KnownNat size, KnownNat size', Eq c) => PolyVec c size'
polyVecDiv :: forall c size. (Field c, KnownNat size, Eq c) => PolyVec c size -> PolyVec c size -> PolyVec c size
polyVecLinear :: forall c size. (Ring c, KnownNat size) => c -> c -> PolyVec c size
polyVecLagrange :: forall c size size'. (Field c, Eq c, KnownNat size, KnownNat size') => Natural -> c -> PolyVec c size'
polyVecGrandProduct :: forall c size. (Field c, KnownNat size) => PolyVec c size -> PolyVec c size -> PolyVec c size -> c -> c -> PolyVec c size
polyVecInLagrangeBasis :: forall c size size'. (Field c, Eq c, KnownNat size, KnownNat size') => c -> PolyVec c size -> PolyVec c size'
polyVecQuadratic :: forall c size. (Ring c, KnownNat size) => c -> c -> c -> PolyVec c size
mulVector :: forall a. Field a => Vector a -> Vector a -> Vector a
mulDft :: forall c. Field c => Integer -> c -> Vector c -> Vector c -> Vector c
mulKaratsuba :: forall a. Field a => Vector a -> Vector a -> Vector a
mulPoly :: forall a. Field a => Poly a -> Poly a -> Poly a
mulPolyKaratsuba :: (Eq a, Field a) => Poly a -> Poly a -> Poly a
mulPolyDft :: forall a. (Eq a, Field a) => Poly a -> Poly a -> Poly a
mulPolyNaive :: Field a => Poly a -> Poly a -> Poly a

Documentation

toPoly :: (Ring c, Eq c) => Vector c -> Poly c Source #

fromPoly :: Poly c -> Vector c Source #

data Poly c Source #

Instances

Instances details

Functor Poly Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods fmap :: (a -> b) -> Poly a -> Poly b # (<$) :: a -> Poly b -> Poly a #
(Ring c, Arbitrary c, Eq c) => Arbitrary (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods arbitrary :: Gen (Poly c) # shrink :: Poly c -> [Poly c] #
Generic (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Associated Types type Rep (Poly c) :: Type -> Type # Methods from :: Poly c -> Rep (Poly c) x # to :: Rep (Poly c) x -> Poly c #
Show c => Show (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods showsPrec :: Int -> Poly c -> ShowS # show :: Poly c -> String # showList :: [Poly c] -> ShowS #
NFData c => NFData (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods rnf :: Poly c -> () #
Eq c => Eq (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (==) :: Poly c -> Poly c -> Bool # (/=) :: Poly c -> Poly c -> Bool #
(Ring c, Eq c) => AdditiveGroup (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (-) :: Poly c -> Poly c -> Poly c Source # negate :: Poly c -> Poly c Source #
(Ring c, Eq c) => AdditiveMonoid (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods zero :: Poly c Source #
(Ring c, Eq c) => AdditiveSemigroup (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (+) :: Poly c -> Poly c -> Poly c Source #
(Field c, Eq c) => MultiplicativeMonoid (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods one :: Poly c Source #
(Field c, Eq c) => MultiplicativeSemigroup (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (*) :: Poly c -> Poly c -> Poly c Source #
(Field c, Eq c) => Exponent (Poly c) Natural Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (^) :: Poly c -> Natural -> Poly c Source #
type Rep (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate type Rep (Poly c) = D1 ('MetaData "Poly" "ZkFold.Base.Algebra.Polynomials.Univariate" "zkfold-base-0.1.0.0-inplace" 'True) (C1 ('MetaCons "P" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Vector c))))

removeZeros :: (Ring c, Eq c) => Poly c -> Poly c Source #

scaleP :: Ring c => c -> Natural -> Poly c -> Poly c Source #

qr :: (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c) Source #

eea :: (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c) Source #

Extended Euclidean algorithm.

lt :: Poly c -> c Source #

deg :: Poly c -> Integer Source #

Degree of zero polynomial is `-1`

vec2poly :: (Ring c, Eq c) => PolyVec c size -> Poly c Source #

data PolyVec c (size :: Natural) Source #

Instances

Instances details

Scale c' c => Scale c' (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods scale :: c' -> PolyVec c size -> PolyVec c size Source #
(Ring c, Arbitrary c, KnownNat size) => Arbitrary (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods arbitrary :: Gen (PolyVec c size) # shrink :: PolyVec c size -> [PolyVec c size] #
Generic (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Associated Types type Rep (PolyVec c size) :: Type -> Type # Methods from :: PolyVec c size -> Rep (PolyVec c size) x # to :: Rep (PolyVec c size) x -> PolyVec c size #
Show c => Show (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods showsPrec :: Int -> PolyVec c size -> ShowS # show :: PolyVec c size -> String # showList :: [PolyVec c size] -> ShowS #
NFData c => NFData (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods rnf :: PolyVec c size -> () #
Eq c => Eq (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (==) :: PolyVec c size -> PolyVec c size -> Bool # (/=) :: PolyVec c size -> PolyVec c size -> Bool #
(Ring c, KnownNat size) => AdditiveGroup (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (-) :: PolyVec c size -> PolyVec c size -> PolyVec c size Source # negate :: PolyVec c size -> PolyVec c size Source #
(Ring c, KnownNat size) => AdditiveMonoid (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods zero :: PolyVec c size Source #
Ring c => AdditiveSemigroup (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (+) :: PolyVec c size -> PolyVec c size -> PolyVec c size Source #
(Field c, KnownNat size, Eq c) => MultiplicativeMonoid (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods one :: PolyVec c size Source #
(Field c, KnownNat size, Eq c) => MultiplicativeSemigroup (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (*) :: PolyVec c size -> PolyVec c size -> PolyVec c size Source #
(Field c, KnownNat size, Eq c) => Exponent (PolyVec c size) Natural Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (^) :: PolyVec c size -> Natural -> PolyVec c size Source #
type Rep (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate type Rep (PolyVec c size) = D1 ('MetaData "PolyVec" "ZkFold.Base.Algebra.Polynomials.Univariate" "zkfold-base-0.1.0.0-inplace" 'True) (C1 ('MetaCons "PV" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Vector c))))

fromPolyVec :: PolyVec c size -> Vector c Source #

toPolyVec :: forall c size. (Ring c, KnownNat size) => Vector c -> PolyVec c size Source #

rewrapPolyVec :: (Vector c -> Vector c) -> PolyVec c size -> PolyVec c size Source #

castPolyVec :: forall c size size'. (Ring c, KnownNat size, KnownNat size', Eq c) => PolyVec c size -> PolyVec c size' Source #

evalPolyVec :: Ring c => PolyVec c size -> c -> c Source #

scalePV :: Ring c => c -> PolyVec c size -> PolyVec c size Source #

polyVecZero :: forall c size size'. (Field c, KnownNat size, KnownNat size', Eq c) => PolyVec c size' Source #

polyVecDiv :: forall c size. (Field c, KnownNat size, Eq c) => PolyVec c size -> PolyVec c size -> PolyVec c size Source #

polyVecLinear :: forall c size. (Ring c, KnownNat size) => c -> c -> PolyVec c size Source #

polyVecLagrange :: forall c size size'. (Field c, Eq c, KnownNat size, KnownNat size') => Natural -> c -> PolyVec c size' Source #

polyVecGrandProduct :: forall c size. (Field c, KnownNat size) => PolyVec c size -> PolyVec c size -> PolyVec c size -> c -> c -> PolyVec c size Source #

polyVecInLagrangeBasis :: forall c size size'. (Field c, Eq c, KnownNat size, KnownNat size') => c -> PolyVec c size -> PolyVec c size' Source #

polyVecQuadratic :: forall c size. (Ring c, KnownNat size) => c -> c -> c -> PolyVec c size Source #

mulVector :: forall a. Field a => Vector a -> Vector a -> Vector a Source #

mulDft :: forall c. Field c => Integer -> c -> Vector c -> Vector c -> Vector c Source #

mulKaratsuba :: forall a. Field a => Vector a -> Vector a -> Vector a Source #

mulPoly :: forall a. Field a => Poly a -> Poly a -> Poly a Source #

Naive vector multiplication, O(n^2)

mulPolyKaratsuba :: (Eq a, Field a) => Poly a -> Poly a -> Poly a Source #

Adaptation of Karatsuba's algorithm. O(n^log_2(3))

mulPolyDft :: forall a. (Eq a, Field a) => Poly a -> Poly a -> Poly a Source #

mulPolyNaive :: Field a => Poly a -> Poly a -> Poly a Source #