Safe Haskell	Safe-Inferred
Language	Haskell2010

ZkFold.Base.Algebra.Polynomials.Univariate

Synopsis

toPoly :: (Ring c, Eq c) => Vector c -> Poly c
constant :: c -> Poly c
monomial :: Ring c => Natural -> c -> Poly c
fromPoly :: Poly c -> Vector c
data Poly c
evalPoly :: Ring c => Poly c -> c -> 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
poly2vec :: forall c size. (Ring c, KnownNat size) => Poly c -> PolyVec c size
data PolyVec c (size :: Natural)
fromPolyVec :: PolyVec c size -> Vector c
toPolyVec :: forall c size. (Ring c, KnownNat size) => Vector c -> PolyVec c size
(.*.) :: forall c size. (Field c, KnownNat size) => PolyVec c size -> PolyVec c size -> PolyVec c size
(./.) :: forall c size. (Field c, KnownNat size) => PolyVec c size -> PolyVec c size -> PolyVec c size
(.*) :: forall c size. Field c => PolyVec c size -> c -> PolyVec c size
(*.) :: forall c size. Field c => c -> PolyVec c size -> PolyVec c size
(.+) :: forall c size. Field c => PolyVec c size -> c -> PolyVec c size
(+.) :: forall c size. Field c => c -> PolyVec c size -> 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 n size. (Field c, KnownNat n, 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
polyVecLagrange :: forall c n size. (Field c, Eq c, KnownNat n, 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 n size. (Field c, Eq c, KnownNat n, KnownNat size) => c -> PolyVec c n -> PolyVec c size
polyVecConstant :: forall c size. (Ring c, KnownNat size) => c -> PolyVec c size
polyVecLinear :: forall c size. (Ring c, KnownNat size) => c -> c -> 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 #

constant :: c -> Poly c Source #

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

A polynomial of form cx^d

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 #
FromConstant c c' => FromConstant c (Poly c') Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods fromConstant :: c -> Poly c' Source #
Scale k c => Scale k (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods scale :: k -> Poly c -> Poly c Source #
(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 #
FromConstant (Poly c) (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods fromConstant :: Poly c -> Poly c Source #
(Field c, Eq c) => Scale (Poly c) (Poly c) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods scale :: Poly c -> Poly c -> Poly c Source #
(Field f, Eq f, IrreduciblePoly f e) => FromConstant (Poly f) (Ext2 f e) Source #
Instance details Defined in ZkFold.Base.Algebra.Basic.Field Methods fromConstant :: Poly f -> Ext2 f e Source #
(Field f, Eq f, IrreduciblePoly f e) => FromConstant (Poly f) (Ext3 f e) Source #
Instance details Defined in ZkFold.Base.Algebra.Basic.Field Methods fromConstant :: Poly f -> Ext3 f e 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" "symbolic-base-0.1.0.0-inplace" 'True) (C1 ('MetaCons "P" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Vector c))))

evalPoly :: Ring c => Poly c -> c -> c Source #

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 #

poly2vec :: forall c size. (Ring c, KnownNat size) => Poly c -> PolyVec c size 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 #
(KnownNat size, Ring c) => IsList (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Associated Types type Item (PolyVec c size) # Methods fromList :: [Item (PolyVec c size)] -> PolyVec c size # fromListN :: Int -> [Item (PolyVec c size)] -> PolyVec c size # toList :: PolyVec c size -> [Item (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) => MultiplicativeMonoid (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods one :: PolyVec c size Source #
(Field c, KnownNat size) => 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) => Exponent (PolyVec c size) Natural Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods (^) :: PolyVec c size -> Natural -> PolyVec c size Source #
(Field c, KnownNat size) => Scale (PolyVec c size) (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate Methods scale :: PolyVec c size -> PolyVec c size -> PolyVec c size Source #
(Ring a, Ord key, KnownNat k) => LinearCombination (Map key a) (Map key (PolyVec a k)) Source #
Instance details Defined in ZkFold.Base.Protocol.Protostar.Fold Methods linearCombination :: Map key a -> Map key a -> Map key (PolyVec a k) Source #
(Ring a, KnownNat n, KnownNat k) => LinearCombination (Vector n a) (Vector n (PolyVec a k)) Source #
Instance details Defined in ZkFold.Base.Protocol.Protostar.Fold Methods linearCombination :: Vector n a -> Vector n a -> Vector n (PolyVec a k) 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" "symbolic-base-0.1.0.0-inplace" 'True) (C1 ('MetaCons "PV" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Vector c))))
type Item (PolyVec c size) Source #
Instance details Defined in ZkFold.Base.Algebra.Polynomials.Univariate type Item (PolyVec c size) = c

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

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

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

Multiply the corresponding coefficients of two polynomials.

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

Divide the corresponding coefficients of two polynomials.

(.*) :: forall c size. Field c => PolyVec c size -> c -> PolyVec c size infixl 7 Source #

Multiply every coefficient of the polynomial by a constant.

(*.) :: forall c size. Field c => c -> PolyVec c size -> PolyVec c size infixl 7 Source #

Multiply every coefficient of the polynomial by a constant.

(.+) :: forall c size. Field c => PolyVec c size -> c -> PolyVec c size infixl 6 Source #

Add a constant to every coefficient of the polynomial.

(+.) :: forall c size. Field c => c -> PolyVec c size -> PolyVec c size infixl 6 Source #

Add a constant to every coefficient of the polynomial.

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 n size. (Field c, KnownNat n, 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 #

polyVecLagrange :: forall c n size. (Field c, Eq c, KnownNat n, 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 n size. (Field c, Eq c, KnownNat n, KnownNat size) => c -> PolyVec c n -> PolyVec c size Source #

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

polyVecLinear :: forall c size. (Ring c, KnownNat size) => c -> c -> 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 #