Many polynomials can be stored and evaluated efficiently when represented as a straight line program (SLP), also known as an algebraic circuit. By contrast, elements of a PolynomialRing in Macaulay2 are necessarily represented in "expanded" form, e.g. via a monomial basis.
This package provides basic types and methods for constructing and evaluating SLPs.
Here is a simple example illustrating an advantage of SLP representations.
i1 : declareVariable x o1 = x o1 : InputGate |
i2 : f = x + 1 o2 = (x + 1) o2 : SumGate |
i3 : n = 12; |
i4 : for i from 1 to n do f = f*f -- f = (x+1)^(2^n) |
i5 : slp = makeSLProgram({x},{f}) o5 = SLProgram{cache => CacheTable{} } constant positions => {-2} constants => | 1 | number of inputs => 1 number of outputs => 1 RawSLProgram => SLProgram ( consts+vars: 2 noninput nodes: 13 output nodes: 1 ) variable positions => {-1} o5 : SLProgram |
i6 : time A = evaluate(slp,matrix{{1}}); -- used 0.00010682 seconds 1 1 o6 : Matrix ZZ <--- ZZ |
i7 : ZZ[y]; |
i8 : time B = sub((y+1)^(2^n),{y=>1}) -- used 7.0643 seconds o8 = 104438888141315250669175271071662438257996424904738378038423348328395390 797155745684882681193499755834089010671443926283798757343818579360726323 608785136527794595697654370999834036159013438371831442807001185594622637 631883939771274567233468434458661749680790870580370407128404874011860911 446797778359802900668693897688178778594690563019026094059957945343282346 930302669644305902501597239986771421554169383555988529148631823791443449 673408781187263949647510018904134900841706167509366833385055103297208826 955076998361636941193301521379682583718809183365675122131849284636812555 022599830041234478486259567449219461702380650591324561082573183538008760 862210283427019769820231316901767800667519548507992163641937028537512478 401490715913545998279051339961155179427110683113409058427288427979155484 978295432353451706522326906139490598769300212296339568778287894844061600 741294567491982305057164237715481632138063104590291613692670834285644073 044789997190178146576347322385026725305989979599609079946920177462481771 844986745565925017832907047311943316555080756822184657174637329688491281 952031745700244092661691087414838507841192980452298185733897764810312608 590300130241346718972667321649151113160292078173803343609024380470834040 3154190336 |
i9 : A == B o9 = true |