text:
Eratosthenes := function(n)
    local a, i, j;
    a := ListWithIdenticalEntries(n, true);
    if n < 2 then
        return [];
    else
        for i in [2 .. n] do
            if a[i] then
                j := i*i;
                if j > n then
                    return Filtered([2 .. n], i -> a[i]);
                else
                    while j <= n do
                        a[j] := false;
                        j := j + i;
                    od;
                fi;
            fi;
        od;
    fi;
end;

Eratosthenes(100);

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

_SVCT_THRSHOLD := 2^13;

NewRulesFor(GT, rec(
    # Vectorize AxI: A x I_n -> (A x I_n/v) x I_v
    GT_Vec_AxI := rec(
        forTransposition := false,
        requiredFirstTag := [AVecReg, AVecRegCx],
        applicable := t -> t.rank()=1 and t.params[2]=GTVec and t.params[3]=GTVec and
                           IsInt(t.params[4][1] / t.firstTag().v),
        children := t -> let(
        r := t.params[4][1] / t.firstTag().v,
        isa := t.firstTag().isa,
        spl := t.params[1], #.setWrap(VWrap(isa)),
        tags := Drop(t.getTags(), 1),
        [[ GT(spl, GTVec, GTVec, [r]).withTags(tags).setWrap(VWrap(isa)) ]]),

        apply := (t, C, Nonterms) -> VTensor(C[1], t.firstTag().v),
    ),

    GT_Vec_IxA := rec(
        forTransposition := false,
        requiredFirstTag := [AVecReg, AVecRegCx],
        applicable := t -> t.rank()=1 and t.params[2]=GTPar and t.params[3]=GTPar and
                           IsInt(t.params[4][1] / t.firstTag().v),
        children := t -> let(
            tags := t.getTags(),
            v := t.firstTag().v,
#            r := t.params[4][1] / v,
            spl := t.params[1],

            [[  TL(Rows(spl)*v, v, 1, 1).withTags(tags).setWrap(VWrapId),
                spl.withTags(Drop(tags, 1)).setWrap(VWrap(tags[1].isa)),
                TL(Cols(spl)*v, Cols(spl), 1, 1).withTags(tags).setWrap(VWrapId)
            ]]),

        apply := (t, C, Nonterms) ->
            let(P := t.params, v := t.firstTag().v, r := P[4][1] / v,
                A := C[1] * VTensor(C[2], v) * C[3], When(r=1, A, Tensor(I(r), A)))
    ),

    # Push vector tag down to preserve locality: vec(I x A) -> (I x vec(A))
    GT_Vec_IxA_Push := rec(
        forTransposition := false,
        requiredFirstTag := [AVecReg, AVecRegCx],
        applicable := t -> t.rank()=1 and t.params[2]=GTPar and t.params[3]=GTPar,
        children := t -> [[ t.params[1].withTags(t.getTags()) ]],
        apply := (t, C, Nonterms) -> Tensor(I(t.params[4][1]), C[1])
    ),

    # Split off L:  vectorizes (I x A), (I x A) L, or L (I x A)
    #
    GT_Vec_SplitL := rec(
        minSize := _SVCT_THRSHOLD,
        forTransposition := false,
        requiredFirstTag := [AVecReg, AVecRegCx],

        applicable := (self, t) >> t.rank()=1 and Maximum(t.dims()) > self.minSize and
            (t.params{[2,3]} in [[GTPar, GTPar], [GTVec, GTPar], [GTPar, GTVec]]),

        children := t -> let(tags := t.getTags(), spl := t.params[1], n := t.params[4][1],
            g := t.params[2], s := t.params[3],
            [[ GT(spl, GTVec, GTVec, [n]).withTags(tags) ]]),

        apply := (t, C, Nonterms) -> let(spl := t.params[1], n := t.params[4][1], g := t.params[2], s := t.params[3],
                        c := Concatenation(
                            When(s=GTPar, [ L(Rows(spl)*n, n) ], []),
                            [ C[1] ],
                            When(g=GTPar, [ L(Cols(spl)*n, Cols(spl)) ], [])), Product(c))
    ),

    GT_Vec_IxA_L := rec(
        maxSize := _SVCT_THRSHOLD,
        forTransposition := false,
        requiredFirstTag := [AVecReg, AVecRegCx],

        applicable := (self, t) >> t.rank()=1
            and t.params[2]=GTVec
            and t.params[3]=GTPar
            and Maximum(t.dims()) <= self.maxSize
            and IsInt(t.params[4][1] / t.firstTag().v),

        children := t -> let(tags := t.getTags(),
            spl := t.params[1], v:=tags[1].v,
            isa:=tags[1].isa, spl := t.params[1], d:=spl.dims(),

            [[ TL(d[1]*v, v).withTags(tags).setWrap(VWrapId),
               spl.withTags(Drop(tags,1)).setWrap(VWrap(isa)) ]]
        ),

        apply := (t, C, Nonterms) -> let(spl := t.params[1],
            d:=spl.dims(), n := t.params[4][1], tag := t.firstTag(),
            v := tag.v, m := n / v,

            NoDiagPullinLeft(When(m=1,
                C[1] * VTensor(C[2], v),
                Tensor(I(m), C[1] * VTensor(C[2], v)) * VTensor(L(m*d[2], m), v)
            ))
        ),
    ),

    GT_Vec_L_IxA := rec(
        maxSize := _SVCT_THRSHOLD,
        forTransposition := false,
        requiredFirstTag := [AVecReg, AVecRegCx],

        applicable := (self, t) >> t.rank()=1 and t.params[2]=GTPar and t.params[3]=GTVec and Maximum(t.dims()) <= self.maxSize and
                           IsInt(t.params[4][1] / t.firstTag().v),

        children := t -> let(tags := t.getTags(), spl := t.params[1], v:=tags[1].v,
            isa:=tags[1].isa, spl := t.params[1], d:=spl.dims(),
            [[ spl.withTags(Drop(tags,1)).setWrap(VWrap(isa)),
               TL(d[2]*v, d[2]).withTags(tags).setWrap(VWrapId) ]] ),

        apply := (t, C, Nonterms) -> let(spl := t.params[1], d:=spl.dims(), n := t.params[4][1], tag := t.firstTag(), v := tag.v, m := n / v,
            NoDiagPullinRight(When(m=1, VTensor(C[1], v) * C[2], VTensor(L(m*d[2], d[2]), v) * Tensor(I(m), VTensor(C[1], v) * C[2]))))
    )
));

ext: gi


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

NewRulesFor(TRCDiag, rec(
    TRCDiag_VRCLR := rec(
        applicable := (self, t) >> t.hasTags() and ObjId(t.firstTag()) = AVecReg,
        apply := (self, t, C, Nonterms) >> let(isa := t.firstTag().isa, v := isa.v, n := Rows(t),
            FormatPrm(fTensor(fId(n/v), L(2*v, v))) *
            VRCLR(Diag(t.params[1]), v) *
            FormatPrm(fTensor(fId(n/v), L(2*v, 2)))
        )
    )
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

Latex := x -> Cond(IsRec(x) and IsBound(x.latex), x.latex(),
                   IsRec(x) and IsBound(x.cprint), x.cprint(),
                   Print(x));
Cprint := x -> When(IsRec(x) and IsBound(x.cprint), x.cprint(), Print(x));

_infix_print := function ( lst, sep, prfunc )
    local  first, c;
    first := true;
    for c  in lst  do
        if first  then  first := false;
        else            Print(sep);  fi;
        prfunc(c);
    od;
    return "";
end;

Gath.latex := self >> Print("\\Gath{", self.func.latex(), "}");
Scat.latex := self >> Print("\\Scat{", self.func.latex(), "}");
Diag.latex := self >> Print("\\Diag{", self.element.latex(), "}");
Prm.latex := self >> Print("\\Prm{", self.func.latex(), "}");

FuncClass.latex := self >> Print("\\f", self.name,
    DoForAll(self.params, p -> Print("{",Cprint(p),"}")));

FDataOfs.latex := self >> Print("\\f", self.name,
    DoForAll(self.rChildren(), p -> Print("{",Cprint(p),"}")));

HH.latex := self >> PrintEvalF("\\f$1{$2}{$3}{$4}{$5}",
    self.name, ()->Latex(self.params[1]), ()->Latex(self.params[2]), ()->Latex(self.params[3]),
    ()->_infix_print(self.params[4],", ",Latex));
BHH.latex := self >> PrintEvalF("\\f$1{$2}{$3}{$4}{$5}",
    self.name, ()->Cprint(self.params[1]), ()->Cprint(self.params[2]), ()->Cprint(self.params[3]),
    ()->_infix_print(self.params[4],", ",Cprint));
HHZ.latex := self >> PrintEvalF("\\f$1{$2}{$3}{$4}{$5}",
    self.name, ()->Cprint(self.params[1]), ()->Cprint(self.params[2]), ()->Cprint(self.params[3]), ()->_infix_print(self.params[4],", ", Cprint));

NonTerminal.latex := self >> Print("\\n", self.name,
    DoForAll(self.params, p -> Print("{",Latex(p),"}")));

Sym.latex := FuncClass.latex;

ISum.latex := self >> PrintEvalF("\\ISum{$1 0}{$2}{$3}",
   () -> When(IsBound(self.var), Print(self.var, "=")),
   () -> Latex(self.domain-1),
   () -> self.child(1).latex());

Compose.latex := self >> DoForAll(self.children(), c->c.latex());

BaseContainer.latex := self >> PrintEvalF("\\$1{$2}", self.name, ()->self.child(1).latex());

BaseOperation.latex := self >> Print("\\", self.name, DoForAll(self.children(), c->Print("{",c.latex(),"}")));

SUM.latex := self >> Chain(
    DoForAllButLast(self.children(), c->Print(c.latex(), "+")),
    Last(self.children()).latex());

gammaTensor.latex := self >> InfixPrint(self.children(), "\\boxtimes", c->c.latex());
fTensor.latex := self >> InfixPrint(self.children(), "\\otimes", c->c.latex());
fDirsum.latex := self >> InfixPrint(self.children(), "\\oplus", c->c.latex());
fCompose.latex := self >> InfixPrint(self.children(), "\\circ", c->c.latex());

Blk.latex := self >> self.print(0,0);


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# input: imaginary, output: co1 (?)
_j := N -> Tensor(I(approx.CeilingRat(N/2)),J(2)*Diag(-1,1));

RealRR_Out := (N, root) -> let(
    rrind := RR(N, 1, root).tolist(),
    outind := List(rrind{[1..(N+1)/2]}, x->When(x.v >= (N+1)/2, N-x.v, x.v)),
    #same as Refl((N+1)/2, N, (N+1)/2, RR(N,1,root)).tolist(),

    # Reflective RR
    Scat(fTensor(FList((N+1)/2, outind), fId(2))) *
    # Conjugate complex elements that will be reflected
    Diag(ConcatList([0..(N-1)/2], x->When(rrind[x+1].v >= (N+1)/2, [1,-1], [1,1])))
);

RulesFor(PRDFT, rec(

   # PRDFT_PD : Projection of complex DFT partial diagonalization rule to real DFT
   # See also : PRDFT_Rader
   #
   PRDFT_PD := rec(
	forTransposition := true,
	maxSize          := 13,
	isApplicable     := (self, P) >> P[1] > 2 and P[1] <= self.maxSize and IsPrime(P[1]),

	rule := (self,P,C) >> let(N:=P[1], n:=N-1, k:=P[2], root:=PrimitiveRootMod(N),
	    BB(RealRR_Out(N, root) *
	    DirectSum(Mat([[1],[0]]), L(n, n/2)) *
	    Mat(MatSPL(DFT_PD.core(N, k, root, true) * DFT_PD.A(N))) *
	    DirectSum(I(1), Tensor(F(2), I(n/2))) *
	    DirectSum(I(1), OS(n, -1)) *
	    Gath(RR(N, 1, root)))
	)
   ),

   # PRDFT_Rader : Projection of complex DFT Rader rule to real DFT
   #
   #   Note: PRDFT of types 2--4 of odd size (which includes all primes > 2)
   #         can be converted without arithmetic cost to PRDFT1,
   #         which means that this rule enables implementation of a prime
   #         size PRDFT of any type.
   PRDFT_Rader := rec(
	isApplicable := (self, P) >> P[1] > 3 and IsPrime(P[1]),

	diag := (N, k, root) -> let(fulldiag := DFT_Rader.raderDiag(N,k,root),
	    last := Int((N-1)/2),
	    Concatenation(2*fulldiag{[1..last-1]}, [fulldiag[last]])),

	# 3rd col with 0's is for padding used by PRDFT
	raderMid := (self, N, k, root) >> let(n:=N-1,
	    DirectSum(Mat([[1, 1, 0], [1, -1/n, 0], [0,0,0]]),
		      RCDiag(RCData(FData(self.diag(N, k, root)))))),

	allChildren := P -> let(n:=P[1]-1,
	    [[ PRDFT(n/2).transpose(), PRDFT3(n/2).transpose(), PRDFT(n, -1) ]]),

	rule := (self,P,C) >> let(N:=P[1], n:=N-1, k:=P[2], root:=PrimitiveRootMod(N),
	    RealRR_Out(N, root) *
	    DirectSum(Mat([[1],[0]]), ##
		      L(n, n/2) *
		      DirectSum(C[1], C[2] * _j(n/2)) *
		      RC(L_or_OS(n/2+1, 2))) *
	    self.raderMid(N, k, root) *
	    DirectSum(I(1), C[3]) *
	    Gath(RR(N, 1, root))
	)
   )
));

RulesFor(IPRDFT, rec(

   # IPRDFT_PD : Projection of complex DFT partial diagonalization rule to inverse real DFT
   # See also : IPRDFT_Rader
   #
   IPRDFT_PD := rec(
	forTransposition := true,
	maxSize          := 13,
	isApplicable     := (self, P) >> P[1] > 2 and P[1] <= self.maxSize and IsPrime(P[1]),
	rule := (self,P,C) >> let(N:=P[1], n:=N-1, k:=P[2], root:=PrimitiveRootMod(N),
	    BB(Scat(RR(N, 1, root)) *
	    DirectSum(I(1), OS(n, -1)) *
	    DirectSum(I(1), Tensor(F(2), I(n/2))) *
	    Mat(MatSPL(TransposedSPL(DFT_PD.core(N, -k, root, true) * DFT_PD.A(N)) * DirectSum(I(1), 2*I(n)))) *
	    DirectSum(Mat([[1,0]]), L(n, 2)) *
	    RealRR_Out(N, root).transpose())
	)
   ),

   # IPRDFT_Rader : Projection of complex DFT Rader rule to inverse real DFT
   #
   #   Note: IPRDFT of types 2--4 of odd size (which includes all primes > 2)
   #         can be converted without arithmetic cost to IPRDFT1,
   #         which means that this rule enables implementation of a prime
   #         size IPRDFT of any type.
   IPRDFT_Rader := CopyFields(PRDFT_Rader, rec(
	# 3rd col with 0's is for padding, we also scale everything but 1st elt by 2,
	# as IPRDFT requires.
	raderMid := (self, N, k, root) >> let(n:=N-1,
	    DirectSum(Mat([[1, 2, 0], [1, -2/n, 0], [0,0,0]]),
		      RCDiag(RCData(FConj(FData(2*self.diag(N, -k, root))))))),

	allChildren := P -> let(n:=P[1]-1,
	    [[ PRDFT(n/2), PRDFT3(n/2), PRDFT(n,-1).transpose() ]]),

	rule := (self,P,C) >> let(N:=P[1], n:=N-1, k:=P[2], root:=PrimitiveRootMod(N),
	    Scat(RR(N, 1, root)) *
	    DirectSum(I(1), C[3]) *
	    self.raderMid(N, k, root) *
	    DirectSum(Mat([[1,0]]), ##
		      RC(L_or_OS(n/2+1, 2).transpose()) *
		      DirectSum(C[1], _j(n/2).transpose() * C[2]) *
		      L(n, 2)) *
	    RealRR_Out(N, root).transpose()
	)
   ))
));


text:
#############################################################################
####
##
#W  streams.gi                 ACE Package                        Greg Gamble
##
##  This file installs non-user functions used in interactions with streams.
##
#Y  Copyright (C) 2000  Centre for Discrete Mathematics and Computing
#Y                      Department of Information Technology & Electrical Eng.
#Y                      University of Queensland, Australia.
##

#############################################################################
####
##
#F  ACE_PRINT_AND_EVAL( <varname>, <expr> ) . . . print and evaluate a string
##
##  emulates a user typing at the `gap> ' prompt: `<varname> := <expr>;'  and
##  prints and returns the evaluation of <expr>; <varname> and <expr>  should
##  be strings.
##
InstallGlobalFunction(ACE_PRINT_AND_EVAL, function(varname, expr)

  Print("gap> ", varname, " := ", ReplacedString(expr, "\n ", "\n>"), ";\n");
  expr := EvalString(expr);
  Print(expr, "\n");
  return expr;
end);

#############################################################################
####
##
#F  ACE_READ_NEXT_LINE(<iostream>) . read complete line but never return fail
##
##  We know there is a complete line to be got; so we  wait  for  it,  before
##  returning.
##
InstallGlobalFunction(ACE_READ_NEXT_LINE, function(iostream)
  return ReadAllLine(iostream, true);
end);

#############################################################################
####
##
#F  FLUSH_ACE_STREAM_UNTIL(<iostream>, <infoLevelFlushed>, <infoLevelMyLine>,
##    <readline>, <IsMyLine>) . . . . . . flush a stream until a desired line
##
##  reads lines in iostream <iostream> via function  <readline>  and  `Info's
##  those lines at `InfoACELevel' <infoLevelFlushed> until a line <line>  for
##  which `<IsMyLine>(<line>) is `true'. The line <line> is then `Info'-ed at
##  `InfoACELevel' <infoLevelMyLine> and returned.
##
InstallGlobalFunction(FLUSH_ACE_STREAM_UNTIL,
function(iostream, infoLevelFlushed, infoLevelMyLine, readline, IsMyLine)
local line;

  line := readline(iostream);
  while not IsMyLine(line) do
    Info(InfoACE, infoLevelFlushed, Chomp(line));
    line := readline(iostream);
  od;
  if line <> fail and infoLevelMyLine < 10 then
    Info(InfoACE, infoLevelMyLine, Chomp(line));
  fi;
  return line;
end);

#############################################################################
####
##
#F  WRITE_LIST_TO_ACE_STREAM( <stream>, <list> ) . . . write to an ACE stream
##
##  writes the list <list> to the iostream <stream>, `Info's <list> following
##  a `ToACE> ' ``prompt'' at `InfoACE' level 4, returns `true' if successful
##  or `fail' otherwise.
##
InstallGlobalFunction(WRITE_LIST_TO_ACE_STREAM, function(stream, list)
local string;

  if not IsOutputTextStream(stream) and IsEndOfStream(stream) then
    Info(InfoACE + InfoWarning, 1, "Sorry. Process stream has died!");
    Info(InfoACE + InfoWarning, 1,
         "You might like to try using 'ACEResurrectProcess(<i>);'");
    return fail;
  fi;
  string := Concatenation( List(list, String) );
  Info(InfoACE, 4, "ToACE> ", string);
  return WriteLine(stream, string);
end);

#E  streams.gi  . . . . . . . . . . . . . . . . . . . . . . . . . . ends here

max_stars_repo_name: wilfwilson/ace

max_issues_repo_name: wilfwilson/ace

max_forks_repo_name: wilfwilson/ace


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

Class(PrunedMDDFT, TaggedNonTerminal, rec(
    abbrevs := [
        (n,k,blk,pat) -> Checked(ForAll(n, IsPosIntSym), IsIntSym(k), IsPosIntSym(blk), ForAll(pat, IsList),
            [_unwrap(n), _unwrap(k), _unwrap(blk), pat, ]),
        ],
    dims      := self >> [Product(self.params[1]), self.params[3]*Product(self.params[4], i->Length(i))],
    isReal    := self >> false,
    normalizedArithCost := self >> let(n := self.params[1], IntDouble(5 * n * d_log(n) / d_log(2))),
    TType := TComplex,
    terminate := self >> let(nlist := self.params[1],
                                blk := self.params[3], pat_md := self.params[4],
                                scat3d := Tensor(List(Zip2(pat_md, nlist), j->let(pat := j[1], size := j[2],
                                    Tensor(Mat(List(pat, i->BasisVec(size/blk, i))).transpose(), I(blk)).terminate()))),
                                dft3d := MDDFT(nlist, self.params[2]),
                                t := dft3d * scat3d,
                                t.terminate()
                            )

));

Class(PrunedIMDDFT, TaggedNonTerminal, rec(
    abbrevs := [
        (n,k,blk,pat) -> Checked(ForAll(n, IsPosIntSym), IsIntSym(k), IsPosIntSym(blk), ForAll(pat, IsList),
            [_unwrap(n), _unwrap(k), _unwrap(blk), pat, ]),
        ],
    dims      := self >> [ self.params[3]*Product(self.params[4], i->Length(i)), Product(self.params[1]) ],
    isReal    := self >> false,
    normalizedArithCost := self >> let(n := self.params[1], IntDouble(5 * n * d_log(n) / d_log(2))),
    TType := TComplex,
    terminate := self >> let(nlist := self.params[1],
                                blk := self.params[3], pat_md := self.params[4],
                                gath3d := Tensor(List(Zip2(pat_md, nlist), j->let(pat := j[1], size := j[2],
                                    Tensor(Mat(List(pat, i->BasisVec(size/blk, i))), I(blk)).terminate()))),
                                dft3d := MDDFT(nlist, self.params[2]),
                                t := gath3d * dft3d,
                                t.terminate()
                            )

));

NewRulesFor(PrunedMDDFT, rec(
    PrunedMDDFT_Base := rec(
        info := "PrunedMDDFT -> PrunedDFT",
        applicable     := nt -> Length(nt.params[1])=1,
        children       := nt -> let(P := nt.params, tags := nt.getTags(), [[ PrunedDFT(P[1][1], P[2], P[3], P[4][1]).withTags(tags) ]]),
        apply          := (nt, C, Nonterms) -> C[1]
    ),
    PrunedMDDFT_RowCol := rec (
        info := "PrunedMDDFT_n -> PrunedMDDFT_n/d, PrunedMDDFT_d",
        applicable := nt -> Length(nt.params[1]) > 1 and not nt.hasTags(),

        children := nt -> let(
            dims := nt.params[1],
            len := Length(dims),
            pats := nt.params[4],
            List([1..len-1],
            i -> [ PrunedMDDFT(dims{[1..i]}, nt.params[2], nt.params[3], pats{[1..i]}),
                   PrunedMDDFT(dims{[i+1..len]}, nt.params[2], nt.params[3], pats{[i+1..len]}) ])),

        apply := (nt, C, Nonterms) -> let(
            n1 := Cols(Nonterms[1]),
            n2 := Rows(Nonterms[2]),
            Tensor(C[1], I(n2)) *
            Tensor(I(n1), C[2])
        )
    )
));

NewRulesFor(PrunedIMDDFT, rec(
    PrunedIMDDFT_Base := rec(
        info := "PrunedIMDDFT -> PrunedIDFT",
        applicable     := nt -> Length(nt.params[1])=1,
        children       := nt -> let(P := nt.params, tags := nt.getTags(), [[ PrunedIDFT(P[1][1], P[2], P[3], P[4][1]).withTags(tags) ]]),
        apply          := (nt, C, Nonterms) -> C[1]
    ),
    PrunedIMDDFT_RowCol := rec (
        info := "PrunedIMDDFT_n -> PrunedIMDDFT_n/d, PrunedIMDDFT_d",
        applicable := nt -> Length(nt.params[1]) > 1 and not nt.hasTags(),

        children := nt -> let(
            dims := nt.params[1],
            len := Length(dims),
            pats := nt.params[4],
            List([1..len-1],
            i -> [ PrunedIMDDFT(dims{[1..i]}, nt.params[2], nt.params[3], pats{[1..i]}),
                   PrunedIMDDFT(dims{[i+1..len]}, nt.params[2], nt.params[3], pats{[i+1..len]}) ])),

        apply := (nt, C, Nonterms) -> let(
            n1 := Cols(Nonterms[1]),
            n2 := Rows(Nonterms[2]),
            Tensor(C[1], I(n2)) *
            Tensor(I(n1), C[2])
        )
    )
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# ==========================================================================
# IDirSum(<var>, <range>, <spl>) - Iterative direct sum.
#    Dimensions of <spl> are assumed to not depend on <var>.
# ==========================================================================
Class(IDirSum, BaseIterative, rec(
    directOper := DirectSum,
    #-----------------------------------------------------------------------
    dims := self >> let(d:=self._children[1].dimensions,
        [d[1]* self.domain, d[2]*self.domain]),
#    dims := self >> _evInt(self.unroll().dims()),
    #-----------------------------------------------------------------------
    unroll := self >> DirectSum(self.unrolledChildren()),
    #-----------------------------------------------------------------------
    transpose := self >> CopyFields(self, rec(
        _children := [self._children[1].transpose()],
        dimensions := Reversed(self.dimensions))),
    #-----------------------------------------------------------------------
    conjTranspose := self >> CopyFields(self, rec(
        _children := [self._children[1].conjTranspose()],
        dimensions := Reversed(self.dimensions))),
    #-----------------------------------------------------------------------
    inverse := self >> CopyFields(self, rec(
        _children := [self._children[1].inverse()],
        dimensions := Reversed(self.dimensions)))
));

Declare(IColDirSum, IRowDirSum);

# ==========================================================================
# IRowDirSum(<var>, <range>, <overlap>, <spl>) - Iterative direct sum.
#    Dimensions of <spl> are assumed to not depend on <var>.
# ==========================================================================
Class(IRowDirSum, BaseIterative, rec(
    directOper := RowDirectSum,
    transposeOper := self >> IColDirSum,
    abbrevs := [ (v, expr) -> [v, v.range, 0, expr] ],

    rChildren := self >> Concat([self.var, self.overlap, self._children], When(IsBound(self._setDims), [self._setDims],[])),
    rSetChild := rSetChildFields("var", "overlap", "_children", "_setDims"),

    new := meth(self, var, domain, overlap, expr)
        local res;
        Constraint(IsSPL(expr));
        Constraint(not IsInt(domain) or domain > 0);
        var.isLoopIndex := true;
        res := SPL(WithBases(self, rec(_children := [expr], var := var, domain := domain, overlap := overlap)));
        res.dimensions := res.dims();
        return res;
    end,
    #-----------------------------------------------------------------------
    print := meth(self, indent, indentStep)
        Print(self.name, "(", self.var, ", ", self.domain, ", ", self.overlap, ",");
        self._newline(indent + indentStep);
        SPLOps.Print(self._children[1], indent+indentStep, indentStep); #, ", ", self.nt_maps);
        self._newline(indent);
        Print(")");
        if IsBound(self._setDims) then
            Print(".overrideDims(", self._setDims, ")");
        fi;
    end,
    #-----------------------------------------------------------------------
    _dims := self >> self.unroll().dims(),
    dims := self >> When(IsBound(self._setDims), self._setDims, let(d := Try(self._dims()), When(d[1], d[2], [errExp(), errExp()]))),
    #-----------------------------------------------------------------------
    unroll := self >> ApplyFunc(self.directOper, [self.overlap, self.unrolledChildren()]),
    #-----------------------------------------------------------------------
    transpose := self >> ApplyFunc(self.transposeOper(), [self.var, self.domain, self.overlap, self.child(1).transpose()]),
    #-----------------------------------------------------------------------
    conjTranspose := self >> ApplyFunc(self.transposeOper(), [self.var, self.domain, self.overlap, self.child(1).conjTranspose()])
));

# ==========================================================================
# IColDirSum(<var>, <range>, <overlap>, <spl>) - Iterative direct sum.
#    Dimensions of <spl> are assumed to not depend on <var>.
# ==========================================================================
Class(IColDirSum, IRowDirSum, rec(
    directOper := ColDirectSum,
    transposeOper := self >> IRowDirSum
));

# ==========================================================================
# IterCompose(<var>, <domain>, <spl>) - iterative compose
#     <spl> must be square
# ==========================================================================
Class(IterCompose, BaseIterative, rec(
    directOper := Compose,
    #-----------------------------------------------------------------------
    dims := self >> self._children[1].dimensions,
    #-----------------------------------------------------------------------
    unroll := self >> Compose(self.unrolledChildren()),
    #-----------------------------------------------------------------------
    # NOTE: this is incorrect, one has to reverse the order
    transpose := self >> CopyFields(self, rec(
        _children := [self._children[1].transpose()],
        domain := self.domain,
        dimensions := self.dimensions))
    # NOTE: conjTranspose() is missing
));

Declare(IterVStack);

# ==========================================================================
# IterHStack(<var>, <domain>, <spl>)
#    Dimensions of <spl> are assumed to not depend on <var>.
# ==========================================================================
Class(IterHStack, BaseIterative, rec(
    directOper := HStack,
    #-----------------------------------------------------------------------
    unroll := self >> HStack(self.unrolledChildren()),
    #-----------------------------------------------------------------------
    dims := self >> [ self.child(1).dimensions[1],
                  self.child(1).dimensions[2] * self.domain ],
    #-----------------------------------------------------------------------
    transpose := self >> IterVStack(self.var, self.domain, self.child(1).transpose()),
    conjTranspose := self >> IterVStack(self.var, self.domain, self.child(1).conjTranspose())
));

# this is a HStack that is guaranteed not to perform any ops, and doesnt need ScatAcc in SumsGen
Class(IterHStack1, IterHStack);
# ==========================================================================
# IterVStack(<var>, <domain>, <spl>)
#    Dimensions of <spl> are assumed to not depend on <var>.
# ==========================================================================
Class(IterVStack, BaseIterative, rec(
    directOper := VStack,
    #-----------------------------------------------------------------------
    unroll := self >> VStack(self.unrolledChildren()),
    #-----------------------------------------------------------------------
    dims := self >> [ self.child(1).dimensions[1] * self.domain,
                  self.child(1).dimensions[2] ],
     #-----------------------------------------------------------------------
    transpose := self >> IterHStack(self.var, self.domain, self.child(1).transpose()),
    conjTranspose := self >> IterHStack(self.var, self.domain, self.child(1).conjTranspose())
));

#IterDirectSum := IDirSum;
# ==========================================================================
# IterDirectSum(<var>, <domain>, <spl>)
#    Dimensions of <spl> are assumed to not depend on <var>.
# ==========================================================================
Class(IterDirectSum, BaseIterative, rec(
    directOper := DirectSum,
    #-----------------------------------------------------------------------
    unroll := self >> DirectSum(self.unrolledChildren()),
    #-----------------------------------------------------------------------
    dims := self >> [self.child(1).dimensions[1] * self.domain, self.child(1).dimensions[2]*self.domain],
    #-----------------------------------------------------------------------
    transpose := self >> IterHStack(self.var, self.domain, self.child(1).transpose()),
    conjTranspose := self >> IterHStack(self.var, self.domain, self.child(1).conjTranspose())
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

#
# Frontier
#

#F _DFUnion(<list_frontiers>) merges frontiers.
#F     Multiple frontiers result from multiple outgoing paths.
#F
#F     For example t3 = add(t1,t2) will have the frontier
#F       [ [t3], _DFUnion([DefFrontier(t1), DefFrontier(t2)]) ]
#F
#F     The parameter is a list of frontiers, where each frontier
#F     is a list of sets of variables.
#F
_DFUnion := function(list_frontiers)
    local depths, maxdepth, curset, res, numfrontiers, d, j;
    numfrontiers := Length(list_frontiers);
    depths := List(list_frontiers, Length);
    maxdepth := Maximum0(depths);
    res := [];
    for d in [1..maxdepth] do
        curset := Set([]);
	for j in [1..numfrontiers] do
	    if d <= depths[j] then
		curset := UnionSet(curset, list_frontiers[j][d]);
	    else
		# if frontier is shorter than the longest, we carry over its last terms.
		# For instance, the frontier of t5 in { t3=add(t1,t2); t5=add(t3, t4) }
		# is [[t5], [t3, t4], [t1, t2, t3]].
		curset := UnionSet(curset, list_frontiers[j][depths[j]]);
	    fi;
	od;
	Add(res, curset);
    od;
    return res;
end;

#F DefFrontier(<cmd>, <depth>) - computes the so-called def-frontier for a command.
#F    The function can be defined inductively as:
#F       DF(t, d) == DF(t.def, d), where t.def is the 'assign' defining t
#F       DF(assign(t,      ...    ), 0)  == [ [t] ]
#F       DF(assign(t, f(a1,a2,...)), 1)  == [ [t], [a1,a2,...] ]
#F       DF(assign(t, f(a1,a2,...)), n)  == [ [t], [a1,a2,...] ] concat
#F                                                 _DFUnion(DF(a1,n-1), DF(a2,n-1), ...)
#F
#F    In plain words it returns the minimal set of variables that fully define a given
#F    location (or cmd.loc).
#F
#F    For instance, the frontier of t5 in { t3=add(t1,t2); t5=add(t3, t4) }
#F    is [[t5], [t3, t4], [t1, t2, t4]].
#F
#F    Note (!!!): MarkDefUse(code) must be called on the corresponding code object,
#F                so that locations can be connected with their definitions
#F
#F    If <depth> is negative, then the maximally deep frontier is computed.
#F
DefFrontier := (cmd, depth) -> Cond(
    IsLoc(cmd), let(def := DefLoc(cmd), When(def=false, [[cmd]], DefFrontier(def, depth))),
    depth = 0,      [Set([cmd.loc])],
#    IsLoc(cmd.exp), [Set([cmd.loc])],
    let(args := ArgsExp(cmd.exp),
	Concatenation([Set([cmd.loc])],
	               _DFUnion(
			   List(args, a -> DefFrontier(a, depth-1))))));

DefCollect := (cmd, depth) -> Cond(
    depth = 0,      cmd.loc,
    IsLoc(cmd.exp), cmd.loc,
    depth = 1,      cmd.exp,
    SubstLeaves(Copy(cmd.exp), var,
	v -> let(def := DefLoc(v), When(def=false, v, DefCollect(def, depth-1)))));

AddFrontier := x -> Cond(
    IsLoc(x), let(def := DefLoc(x),
	Cond(def = false, x, AddFrontier(def.exp))),
    ObjId(x) in [add,sub],
        ApplyFunc(ObjId(x), List(x.args, AddFrontier)),
    x);

AddFrontierD := (x,d) -> Cond(
    d = 0,    x,
    IsLoc(x), let(def := DefLoc(x),
	Cond(def = false, x, AddFrontierD(def.exp, d))),
    ObjId(x) in [add,sub],
        ApplyFunc(ObjId(x), List(x.args, a -> AddFrontierD(a, d-1))),
    x);

AddFrontierDM := (x,d) -> Cond(
    d = 0,
        [x,false],
    IsLoc(x), let(def := DefLoc(x),
	Cond(def = false, [x,false], AddFrontierDM(def.exp, d))),
    d = 1,
        [x,ObjId(x)=mul],
    ObjId(x) in [add,sub],
        let(args := List(x.args, a -> AddFrontierDM(a, d-1)),
	    Cond(ForAll(args, a->a[2]=false), [x,false],
		 [ApplyFunc(ObjId(x), List([1..Length(args)], i->Cond(args[i][2], args[i][1], x.args[i]))), true])),
    [x,ObjId(x)=mul]);

# NOTE: memoization
#
Class(madd, add, rec(
    redundancy := self >> self.constantRedundancy(), # or self.termRedundancy(),

    terms               := self >> Map(self.args, a->a.args[2]),
    constants           := self >> Map(self.args, a->a.args[1].v),
    nonTrivialConstants := self >> Filtered(Map(self.args, a->AbsFloat(a.args[1].v)), c->c<>1),

    constantRedundancy := self >> let(
	constants := self.nonTrivialConstants(),
	constants <> [] and Length(constants)<>Length(Set(constants))),

    termRedundancy := self >> let(
	locs := Filtered(self.terms(), IsLoc),
	locs <> [] and Length(locs) <> Length(Set(locs))),

    factorConstants := meth(self)
        local constants, res, t, c, a, i, fac_indices, l1, l2;
	res := []; constants := []; l1:=[]; fac_indices := Set([]);
	for a in self.args do
	    a := Copy(a);
	    c := a.args[1].v; t := a.args[2];

	    if c in [1,-1] then
		Add(constants, c); Add(res, a);
	    elif c in constants then
		i := Position(constants, c);
		res[i].args[2] := add(res[i].args[2], t); AddSet(fac_indices,i);
	    elif -c in constants then
		i := Position(constants, -c);
		res[i].args[2] := sub(res[i].args[2], t); AddSet(fac_indices,i);
	    else
		Add(constants, c); Add(res, a);
	    fi;
	od;

	l1 := res{fac_indices};
	l2 := res{Difference([1..Length(res)], fac_indices)};

	if l1=[] then return FoldL1(l2,add); fi;
	l1 := FoldL1(l1,add);

	if l2=[] then return l1; fi;
	l2 := FoldL1(l2,add);
	return add(l1, l2);
    end,

    factorTerms := meth(self)
        local terms, res, t, c, a, i, fac_indices, l1, l2;
	res := []; terms := []; fac_indices := Set([]);
	for a in self.args do
	    a := Copy(a);
	    c := a.args[1].v; t := a.args[2];

	    if IsLoc(t) and t in terms then
		i := Position(terms, t);
		res[i].args[1].v := res[i].args[1].v + c; AddSet(fac_indices,i);
	    else
		Add(terms, t); Add(res, a);
	    fi;
	od;

	l1 := res{fac_indices};
	l2 := res{Difference([1..Length(res)], fac_indices)};
	l1 := Filtered(l1, a->a.args[1].v <> 0);
	l2 := Filtered(l2, a->a.args[1].v <> 0);

	if l1=[] and l2=[] then return V(0); fi;

	if l1=[] then return FoldL1(l2,add); fi;
	l1 := FoldL1(l1,add);

	if l2=[] then return l1; fi;
	l2 := FoldL1(l2,add);
	return add(l1, l2);
    end
));

# "MultiAdd" is a normal form for linear expressions
#  MultiAdd = madd(mul(c1,e1), mul(c2,e2), ...)
#
Class(ToMultiAdd, RuleSet, rec(
    __call__ := (self, e) >> TDA(madd(mul(1,e)), self, SpiralDefaults)));

RewriteRules(ToMultiAdd, rec(
    EliminateAdd := Rule(add, e->ApplyFunc(madd, List(e.args, a->mul(1,a)))),

    EliminateSub := Rule(sub, e->madd(mul(1,e.args[1]), mul(-1, e.args[2]))),

    MulMul := Rule([mul, @(1,Value), [mul, @(2,Value), @(3)]],
	e -> mul(@(1).val.v * @(2).val.v, @(3).val)),

    MaddSinkMul := ARule(madd, [[mul, @(1,Value), @(2,madd)]],
	e -> List(@(2).val.args, a->mul(@(1).val*a.args[1], a.args[2]))),

    FlattenMaddMadd := ARule(madd, [@(1,madd)], e->@(1).val.args)
));

NODE := x -> RCSE.node(TDouble, x);
REMOVE_NODE := x -> RCSE.remove_node(x);

deepCheck := function(c, d)
    local frontier, linexp;
    frontier := AddFrontierD(c.exp, d);
    linexp := ToMultiAdd(frontier);
    if not ObjId(linexp)=madd then return [c.loc,c.loc,"none"]; fi;
    if linexp.constantRedundancy() then	return [c.loc, linexp, "constant"];
    elif linexp.termRedundancy()   then	return [c.loc, linexp, "term"];
    else	                        return [c.loc, c.loc, "none"];
    fi;
end;

deepCheckM := function(c, d)
    local frontier, linexp;
    frontier := AddFrontierDM(c.exp, d)[1];
    linexp := ToMultiAdd(frontier);
    if not ObjId(linexp)=madd then return [c.loc,c.loc,"none"]; fi;
    if linexp.constantRedundancy() then	return [c.loc, linexp, "constant"];
    elif linexp.termRedundancy()   then	return [c.loc, linexp, "term"];
    else	                        return [c.loc, c.loc, "none"];
    fi;
end;

_DeepSimplifyCmd := function(c, d, frontier_func)
    local node, frontier, linexp;

    frontier := frontier_func(c.exp, d);
    linexp := ToMultiAdd(frontier);

    if not ObjId(linexp)=madd then return c; fi;

    if linexp.constantRedundancy() then
	linexp := linexp.factorConstants();
	if IsValue(linexp) then node := linexp;
	else node := ApplyFunc(ObjId(linexp), List(linexp.args, NODE));
	fi;
	c.exp := node;
    elif linexp.termRedundancy() then
	linexp := linexp.factorTerms();
	if IsValue(linexp) then node := linexp;
	else node := ApplyFunc(ObjId(linexp), List(linexp.args, NODE));
	fi;
	c.exp := node;
    fi;
    return c;
end;

DeepSimplifyCmd := function(c, d1, d2)
    if PatternMatch(c.exp, [mul, @(1,Value), @(2,var,v->DefLoc(v)<>false)], empty_cx()) and
	PatternMatch(DefLoc(@(2).val).exp, [mul, @(3,Value), @(4)], empty_cx()) then
	c.exp := mul(@(1).val.v * @(3).val.v, @(4).val);
    fi;
    c := _DeepSimplifyCmd(c, d1, AddFrontierD);
    c := _DeepSimplifyCmd(c, d2, (x,d)->AddFrontierDM(x,d)[1]);
    return c;
end;

Declare(DeepSimplifyChain);

DEPTH1 := 2; # AddFrontierD
DEPTH2 := 3; # AddFrontierDM

DefUnbound := function(e, bound)
    local unbound, defs;
    unbound := Difference(e.free(), bound);
    defs := Filtered(List(unbound, DefLoc), d->d<>false and not Same(d,e));
    return Concatenation(Concatenation(List(defs, d -> DefUnbound(d, bound))), defs);
end;

_DeepSimplifyChain := function(code, bound)
   local orig, c, res, cmds, args, supp, supplocs;
   res := chain();

   for c in code.cmds do
       if ObjId(c) <> assign then Error("Can't handle 'c' of type '", ObjId(c), "'"); fi;
       orig := c.exp;

       DeepSimplifyCmd(c,DEPTH1,DEPTH2);
       if IsVar(c.loc) then AddSet(bound, c.loc); fi;

       supp := chain(DefUnbound(c.exp, bound));
       supplocs := List(supp.cmds, cmd->cmd.loc);
       DoForAll(supplocs, REMOVE_NODE);
       UniteSet(bound, supplocs);

       supp := FlattenCode(_DeepSimplifyChain(supp, bound));
       Add(supp.cmds, c);
       supp := RCSE(supp);

       Append(res.cmds, supp.cmds);
   od;

   return res;
end;

DeepSimplifyChain := code -> _DeepSimplifyChain(code, code.free());

DeepSimplify := function(code)
   local c, frontier, linexp, free, undefined;
   code := BinSplit(code);
   RCSE.flush();
   MarkDefUse(code);
   return SubstBottomUp(code, chain, DeepSimplifyChain);
end;

_CheckUninitializedChain := function(code, def, uninit)
    local def1, def2, c, use;
    for c in code.cmds do
        if ObjId(c)=assign then
	    use := VarArgsExp(c.exp);
	    UniteSet(uninit, Filtered(use, x->not x in def));
	    AddSet(def, c.loc);

        elif ObjId(c)=chain then
            [def, uninit] := _CheckUninitializedChain(c, def, uninit);

        elif ObjId(c)=IF then
            [def1, uninit] := _CheckUninitializedChain(c.then_cmd, ShallowCopy(def), uninit);
            [def2, uninit] := _CheckUninitializedChain(c.else_cmd, ShallowCopy(def), uninit);
            def := Union(def1, def2);
	fi;
    od;
    return [def, uninit];
end;

CheckUninitializedChain := function(code)
    local def, uninit;
    Constraint(ObjId(code)=chain);
    def := Set([]);
    uninit := Set([]);
    [def, uninit] := _CheckUninitializedChain(code, def, uninit);
    return uninit;
end;

reds := chain -> Filtered(chain.cmds, c -> deepCheck(c,DEPTH1)[3] <>"none" or
    deepCheckM(c, DEPTH2)[3] <>"none");

DoDeepSimplify := function(code, num_iterations)
   local c, frontier, linexp, free, undefined, i;
   Print("Orig cost : ", ArithCostCode(code), "\n");
   for i in [1..num_iterations] do
       code := DeepSimplify(code);  Print("DS : ", ArithCostCode(code), "\n");
       code := CopyPropagate(code); Print("CP : ", ArithCostCode(code), "\n");
       code := CopyPropagate(code); Print("CP : ", ArithCostCode(code), "\n");
       code := CopyPropagate(code); Print("CP : ", ArithCostCode(code), "\n");
       code := BinSplit(code);
       code := RCSE(code); Print("RCSE : ", ArithCostCode(code), "\n");
   od;
   return code;
end;

# err := [];

# LIMIT := 1; ww:=DeepSimplify(Copy(w));; cm := CMatrix(pp(ww));
# if inf_norm(cm-dm) > 1e-10 then Print("ERROR\n"); Add(err, [Copy(ww), Copy(w), inf_norm(cm-dm)]); else Print("OK\n"); fi;

# LIMIT := 1; w:=DeepSimplify(Copy(ww));; cm := CMatrix(pp(w));
# if inf_norm(cm-dm) > 1e-10 then Print("ERROR\n"); err := Add(err, [Copy(w), Copy(ww), inf_norm(cm-dm)]); else Print("OK\n"); fi;


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

#   FF: needed to merge integer tables due to SAR grds. not sure where to put yet...
MergeIntData := function(s, opts)
    local datas, first, eqdata, subst;
    datas := Filtered(Set(Collect(s, @(1, var, e->IsBound(e.value) and not IsLoopIndex(e)))), i->i.t.t=TInt);

    while datas <> [] do
        first := datas[1];
        datas := Drop(datas, 1);
        eqdata := Filtered(datas, i->i.value=first.value);
        if Length(eqdata) > 0 then
            SubtractSet(datas, Set(eqdata));
            for subst in eqdata do
                SubstVars(s, rec((subst.id) := first));
            od;
        fi;
    od;
    return s;
end;


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

_RDFT_CONST := 2.5;

#F TRDFT2D([<m>, <n>], <k>)
Class(TRDFT2D, TaggedNonTerminal, rec(
    abbrevs := [
        P     -> Checked(IsList(P), Length(P) = 2, ForAll(P,i->IsPosInt(i) and IsEvenInt(i)), Product(P) > 1,
                [ RemoveOnes(P), 1]),
        (P,k) -> Checked(IsList(P), Length(P) = 2, ForAll(P,IsPosInt), IsInt(k), Product(P) > 1,
                        Gcd(Product(P), k)=1,
                [ RemoveOnes(P), k mod Product(P)])
    ],
    dims := self >> let(m := self.params[1][1], n := self.params[1][2], d := [n*(m+2), m*n], When(self.transposed, Reversed(d), d)),
    isReal := True,
    terminate := self >>
            Gath(fTensor(fAdd(self.params[1][1], (self.params[1][1]+2)/2, 0), fId(2*self.params[1][2]))) *
            RC(MDDFT(self.params[1], self.params[2]).terminate()) *
            Scat(fTensor(fId(Product(self.params[1])), fBase(2, 0))),
    normalizedArithCost := (self) >> let(n := Product(self.params[1]), IntDouble(_RDFT_CONST * n * d_log(n) / d_log(2))),
    compute := meth(self, data)
        local rows, cols, cxrows, m1, m2;

        rows := self.params[1][1];
        cols := self.params[1][2];
        cxrows := Rows(self)/cols;

        m1 := List(TransposedMat(List(TransposedMat(data), i->ComplexFFT(i){[1..cxrows/2]})), ComplexFFT);
        m2 := Flat(List(Flat(m1), i->[ReComplex(i), ImComplex(i)]));

        return List([0..cxrows-1], i->m2{[cols*i+1..cols*(i+1)]});
    end
));

#F TIRDFT2D([<m>, <n>], <k>)
Class(TIRDFT2D, TaggedNonTerminal, rec(
    abbrevs := [
        P     -> Checked(IsList(P), Length(P) = 2, ForAll(P,i->IsPosInt(i) and IsEvenInt(i)), Product(P) > 1,
                [ RemoveOnes(P), 1]),
        (P,k) -> Checked(IsList(P), Length(P) = 2, ForAll(P,IsPosInt), IsInt(k), Product(P) > 1,
                        Gcd(Product(P), k)=1,
                [ RemoveOnes(P), k mod Product(P)])
    ],
    dims := self >> let(m := self.params[1][1], n := self.params[1][2], d := [m*n, n*(m+2)], When(self.transposed, Reversed(d), d)),
    isReal := True,
    terminate := self >> let(cxrows := (self.params[1][1]+2)/2, rows := self.params[1][1], cols := self.params[1][2], k := self.params[2],
        Tensor(PRDFT(rows,k).inverse().terminate(), I(cols)) * Tensor(I(cxrows), L(2*cols, 2)*RC(DFT(cols, -k)))),
    normalizedArithCost := (self) >> let(n := Product(self.params[1]), IntDouble(_RDFT_CONST * n * d_log(n) / d_log(2)))
));

#F 2D RDFT Rule
NewRulesFor(TRDFT2D, rec(
    TRDFT2D_ColRow_tSPL := rec(
        switch := true,
        applicable := (self, t) >> true,
        children := (self, t) >> let(m := t.params[1][1], n:=t.params[1][2], k:= t.params[2], tags := t.getTags(),
            [[
                TCompose([
                    TTensorI(TCompose([TRC(DFT(n, k)), TPrm(L(2*n, n))]), (m+2)/2, APar, APar),
                    TTensorI(PRDFT1(m, k), n, AVec, AVec)
                ]).withTags(t.getTags())
            ]]),
        apply := (self, t, C, Nonterms) >> C[1]
    )
));

#F 2D IRDFT Rule
NewRulesFor(TIRDFT2D, rec(
    TIRDFT2D_RowCol_tSPL := rec(
        switch := true,
        applicable := (self, t) >> true,
        children := (self, t) >> let(m := t.params[1][1], n:=t.params[1][2], k:= t.params[2], tags := t.getTags(),
            [[
                TCompose([
                    TTensorI(PRDFT1(m, k).inverse(), n, AVec, AVec),
                    TTensorI(TCompose([TPrm(L(2*n, 2)), TRC(DFT(n, -k))]), (m+2)/2, APar, APar)
                ]).withTags(t.getTags())
            ]]),
        apply := (self, t, C, Nonterms) >> C[1]
    )
));


text:
# Using built-in functions
Incr := s -> String(Int(s) + 1);

# Implementing addition
# (but here 9...9 + 1 = 0...0 since the string length is fixed)
Increment := function(s)
  local c, n, carry, digits;
  digits := "0123456789";
  n := Length(s);
  carry := true;
  while n > 0 and carry do
    c := Position(digits, s[n]) - 1;
    if carry then
      c := c + 1;
    fi;
    if c > 9 then
      carry := true;
      c := c - 10;
    else
      carry := false;
    fi;
    s[n] := digits[c + 1];
    n := n - 1;
  od;
end;

s := "2399";
Increment(s);
s;
# "2400"

ext: gap

max_stars_repo_name: mullikine/RosettaCodeData

max_issues_repo_name: seanwallawalla-forks/RosettaCodeData

max_forks_repo_name: seanwallawalla-forks/RosettaCodeData


text:
%Terminals
    DollarSign ::= '$'
    Percent ::= '%'
    _
    a b c d e f g h i j k l m n o p q r s t u v w x y z
    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
%End

%Headers
    /.
        static readonly int[] tokenKind = new int[128];
        static bool __b_init = init_block();
        static bool init_block()
        {
            tokenKind['$'] = $sym_type.$prefix$DollarSign$suffix$;
            tokenKind['%'] = $sym_type.$prefix$Percent$suffix$;
            tokenKind['_'] = $sym_type.$prefix$_$suffix$;

            tokenKind['a'] = $sym_type.$prefix$a$suffix$;
            tokenKind['b'] = $sym_type.$prefix$b$suffix$;
            tokenKind['c'] = $sym_type.$prefix$c$suffix$;
            tokenKind['d'] = $sym_type.$prefix$d$suffix$;
            tokenKind['e'] = $sym_type.$prefix$e$suffix$;
            tokenKind['f'] = $sym_type.$prefix$f$suffix$;
            tokenKind['g'] = $sym_type.$prefix$g$suffix$;
            tokenKind['h'] = $sym_type.$prefix$h$suffix$;
            tokenKind['i'] = $sym_type.$prefix$i$suffix$;
            tokenKind['j'] = $sym_type.$prefix$j$suffix$;
            tokenKind['k'] = $sym_type.$prefix$k$suffix$;
            tokenKind['l'] = $sym_type.$prefix$l$suffix$;
            tokenKind['m'] = $sym_type.$prefix$m$suffix$;
            tokenKind['n'] = $sym_type.$prefix$n$suffix$;
            tokenKind['o'] = $sym_type.$prefix$o$suffix$;
            tokenKind['p'] = $sym_type.$prefix$p$suffix$;
            tokenKind['q'] = $sym_type.$prefix$q$suffix$;
            tokenKind['r'] = $sym_type.$prefix$r$suffix$;
            tokenKind['s'] = $sym_type.$prefix$s$suffix$;
            tokenKind['t'] = $sym_type.$prefix$t$suffix$;
            tokenKind['u'] = $sym_type.$prefix$u$suffix$;
            tokenKind['v'] = $sym_type.$prefix$v$suffix$;
            tokenKind['w'] = $sym_type.$prefix$w$suffix$;
            tokenKind['x'] = $sym_type.$prefix$x$suffix$;
            tokenKind['y'] = $sym_type.$prefix$y$suffix$;
            tokenKind['z'] = $sym_type.$prefix$z$suffix$;

            tokenKind['A'] = $sym_type.$prefix$A$suffix$;
            tokenKind['B'] = $sym_type.$prefix$B$suffix$;
            tokenKind['C'] = $sym_type.$prefix$C$suffix$;
            tokenKind['D'] = $sym_type.$prefix$D$suffix$;
            tokenKind['E'] = $sym_type.$prefix$E$suffix$;
            tokenKind['F'] = $sym_type.$prefix$F$suffix$;
            tokenKind['G'] = $sym_type.$prefix$G$suffix$;
            tokenKind['H'] = $sym_type.$prefix$H$suffix$;
            tokenKind['I'] = $sym_type.$prefix$I$suffix$;
            tokenKind['J'] = $sym_type.$prefix$J$suffix$;
            tokenKind['K'] = $sym_type.$prefix$K$suffix$;
            tokenKind['L'] = $sym_type.$prefix$L$suffix$;
            tokenKind['M'] = $sym_type.$prefix$M$suffix$;
            tokenKind['N'] = $sym_type.$prefix$N$suffix$;
            tokenKind['O'] = $sym_type.$prefix$O$suffix$;
            tokenKind['P'] = $sym_type.$prefix$P$suffix$;
            tokenKind['Q'] = $sym_type.$prefix$Q$suffix$;
            tokenKind['R'] = $sym_type.$prefix$R$suffix$;
            tokenKind['S'] = $sym_type.$prefix$S$suffix$;
            tokenKind['T'] = $sym_type.$prefix$T$suffix$;
            tokenKind['U'] = $sym_type.$prefix$U$suffix$;
            tokenKind['V'] = $sym_type.$prefix$V$suffix$;
            tokenKind['W'] = $sym_type.$prefix$W$suffix$;
            tokenKind['X'] = $sym_type.$prefix$X$suffix$;
            tokenKind['Y'] = $sym_type.$prefix$Y$suffix$;
            tokenKind['Z'] = $sym_type.$prefix$Z$suffix$;
            return true;
        }

         public   static int getKind(char c)
        {
            return (((c & 0xFFFFFF80) == 0) /* 0 <= c < 128? */ ? tokenKind[c] : 0);
        }
    ./
%End


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# NOTE: a hack, because we essentially ignore doHashValues
_constHashPat := @@(1, Value, (e, cx) ->
    e.t.doHashValues and not IsIntT(e.t) and e.t<>TString and e.t<>TBool
    and not Last(cx.parents) _is data
    and not ForAny(cx.parents, p -> p _is Value)
);

# ^^ NOTE: strings remapped to vars cause trouble in make_env

# Below could be done automatically in Value constructor (Value.new),
# but HashTable object is not implemented efficiently, leading
# to long runtimes when huge data(..) blocks were used (e.g., SAR)
#
HashConstantsCode := (code, hashtab, hashadd_func, pat) -> SubstTopDownRulesNR(code, rec(
    hash_constant := Rule(pat, e -> hashadd_func(hashtab, e)
)));

#
# Hash for constants
#
NewConstantHash := () -> HashTable( (key,size) -> key[1].t.hash(key[1].v, size) );
GlobalConstantHash := NewConstantHash();

HashedValue := function(conhash, val)
    local hashed, h;
    if not val.t.doHashValues then return val; fi;
    hashed := HashLookup(conhash, [val, val.t]);
    if hashed = false then
        h := val;
        HashAdd(conhash, [val,val.t], h);
        return h;
    else
      return hashed;
    fi;
end;

#
# Hash for constants remapped to variables
#
NewConstantVarHash := () -> HashTable( (key,size) -> key[1].t.hash(key[1].v, size) );
GlobalConstantVarHash := NewConstantVarHash();

VHashedValue := function(conhash, val)
    local hashed, h;
    if not val.t.doHashValues then return val; fi;
    hashed := HashLookup(conhash, [val, val.t]);
    if hashed = false then
        h := var.fresh_t("C", val.t);
        h.value := val;
        HashAdd(conhash, [val, val.t], h);
        return h;
    else
      return hashed;
    fi;
end;

#
# Compiler interface
#
FlushConsts := function()
    GlobalConstantHash    := NewConstantHash();
    GlobalConstantVarHash := NewConstantVarHash();
end;

HashConsts := function (c, opts)
    if IsBound(opts.declareConstants) and opts.declareConstants then
        c := HashConstantsCode(c, GlobalConstantVarHash, VHashedValue, _constHashPat);
    else
        c := HashConstantsCode(c, GlobalConstantHash, HashedValue, _constHashPat);
    fi;
    return c;
end;

#F DeclareConstantsHash(<c>, <htab>)
#F
_declareConstantsHash := function(c, htab)
    local hh, h;
    for hh in htab.entries do
        for h in hh do
	    c := data(h.data, h.key[1], c);
	od;
    od;
    return c;
end;

#F DeclareConstantsCode(<c>, <opts>)
#F
#F Declares constants in the code as variables, without polluting the global hash.
#F Constants are declared at the top level, without regard of placement.
#F
#F To better localize use DeclareConstantsCodeLocally(c, [func], opts)
#F
DeclareConstantsCode := function(c, opts)
    local htab, hh, h;
    htab := NewConstantVarHash();
    c := HashConstantsCode(c, htab, VHashedValue, _constHashPat);
    return _declareConstantsHash(c, htab);
end;

_localDeclareConstants := function(x, opts)
    local ch, c;
    ch := x.rChildren();
    ch := List(ch, c -> Cond(not IsCommand(c), c, DeclareConstantsCode(c, opts)));
    return x.from_rChildren(ch);
end;

#F DeclareConstantsCode(<c>, <patterns>, <opts>)
#F
#F Applies DeclareConstantsCode locally to each of the patterns.
#F This function is non-recursive, i.e. if one of the patterns is matched, it won't
#F go inside the body. So for best results all patterns should be mutually exclusive.
#F
DeclareConstantsCodeLocally := (c, patterns, opts) -> SubstTopDownRulesNR(
    c, List(patterns, p -> Rule(p, _localDeclareConstants))
);


text:
%Options fp=LPGKWLexer
%options single-productions
%options template=KeywordTemplateF.gi

%Include
    --
    -- Each upper case letter is mapped into is corresponding
    -- lower case counterpart. For example, if an 'A' appears
    -- in the input, it is mapped into Char_a just like 'a'.
    --
    KWLexerFoldedCaseMapF.gi
%End

%Export
   ALIAS_KEY
   AST_KEY
   DEFINE_KEY
   DISJOINTPREDECESSORSETS_KEY
   DROPRULES_KEY
   DROPSYMBOLS_KEY
   EMPTY_KEY
   END_KEY
   ERROR_KEY
   EOL_KEY
   EOF_KEY
   EXPORT_KEY
   GLOBALS_KEY
   HEADERS_KEY
   IDENTIFIER_KEY
   IMPORT_KEY
   INCLUDE_KEY
   KEYWORDS_KEY
   NAMES_KEY
   NOTICE_KEY
   OPTIONS_KEY
   RECOVER_KEY
   RULES_KEY
   SOFT_KEYWORDS_KEY
   START_KEY
   TERMINALS_KEY
   TRAILERS_KEY
   TYPES_KEY
%End
%Globals
    /.
#pragma once
#include "LPGLexerprs.h"
#include "tuple.h"
#include "LPGKWLexerprs.h"
#include "LPGParsersym.h"
    ./
%End
%Start
    Keyword
%End

%Notice
/.
////////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2007 IBM Corporation.
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// which accompanies this distribution, and is available at
// http://www.eclipse.org/legal/epl-v10.html
//
//Contributors:
//    Philippe Charles (pcharles@us.ibm.com) - initial API and implementation

////////////////////////////////////////////////////////////////////////////////
./
%End

%Rules
    Keyword ::= KeyPrefix a l i a s
        /.$BeginJava
            $setResult($_ALIAS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix a s t
        /.$BeginJava
            $setResult($_AST_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix d e f i n e
        /.$BeginJava
            $setResult($_DEFINE_KEY);
          $EndJava
        ./
     Keyword ::= KeyPrefix d i s j o i n t p r e d e c e s s o r s e t s
        /.$BeginJava
            $setResult($_DISJOINTPREDECESSORSETS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix d r o p r u l e s
        /.$BeginJava
            $setResult($_DROPRULES_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix d r o p s y m b o l s
        /.$BeginJava
            $setResult($_DROPSYMBOLS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix e m p t y
        /.$BeginJava
            $setResult($_EMPTY_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix e n d
        /.$BeginJava
            $setResult($_END_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix e r r o r
        /.$BeginJava
            $setResult($_ERROR_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix e o l
        /.$BeginJava
            $setResult($_EOL_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix e o f
        /.$BeginJava
            $setResult($_EOF_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix e x p o r t
        /.$BeginJava
            $setResult($_EXPORT_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix g l o b a l s
        /.$BeginJava
            $setResult($_GLOBALS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix h e a d e r s
        /.$BeginJava
            $setResult($_HEADERS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix i d e n t i f i e r
        /.$BeginJava
            $setResult($_IDENTIFIER_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix i m p o r t
        /.$BeginJava
            $setResult($_IMPORT_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix i n c l u d e
        /.$BeginJava
            $setResult($_INCLUDE_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix k e y w o r d s
        /.$BeginJava
            $setResult($_KEYWORDS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix s o f t k e y w o r d s
        /.$BeginJava
            $setResult($_SOFT_KEYWORDS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix n a m e s
        /.$BeginJava
            $setResult($_NAMES_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix n o t i c e
        /.$BeginJava
            $setResult($_NOTICE_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix t e r m i n a l s
        /.$BeginJava
            $setResult($_TERMINALS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix r e c o v e r
        /.$BeginJava
            $setResult($_RECOVER_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix r u l e s
        /.$BeginJava
            $setResult($_RULES_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix s t a r t
        /.$BeginJava
            $setResult($_START_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix t r a i l e r s
        /.$BeginJava
            $setResult($_TRAILERS_KEY);
          $EndJava
        ./
    Keyword ::= KeyPrefix t y p e s
        /.$BeginJava
            $setResult($_TYPES_KEY);
          $EndJava
        ./

    KeyPrefix -> '$' | '%'
%End


text:
# Copyright (c) 2018-2020, Carnegie Mellon University
# See LICENSE for details

max_stars_repo_name: franzfranchetti/spiral-software

max_issues_repo_name: franzfranchetti/spiral-software

max_forks_repo_name: franzfranchetti/spiral-software


text:
local reps,tori,labels,I,II,ords,mizuno,blocks;

mizuno:=[[1,2,3,4,5,6,7,
          9,10,11,12,
          13,14,16,17,
          19,18,20,21,
          23,24,25,27,
          26,28,30,31,
          32,33,35,34,
          37,38,39,40,
          41,44,45,46,
          48,49,51,52,
          53,55,57,58,
          59,61,63,64,
          66,69,70,71,
          75,76,80,82,
          85,89,93,97],
         [8,
          15,22,29,36,
          43,42,47,50,
          54,56,60,62,
          65,67,68,72,
          73,74,77,78,
          79,81,83,84,
          86,87,88,90,
          91,92,94,95,
          96,98,99,100,
          101,102,103,104,
          105,106,107,108,
          109,110,111,112,
          114,113,115,116,
          117,118,119,120]];

reps:=[[[1,1],[2,1],[3,1],[4,1],[5,1],[6,1],[7,1],[101,1]],          # E_8
       [[1,1],[2,1],[9,1],[10,1],[5,1],[6,1],[7,1],[101,1]],         # E_8(a_1)
       [[1,1],[3,1],[2,1],[9,1],[11,1],[12,1],[13,1],[101,1]],       # E_8(a_2)
       [[8,1],[9,1],[10,1],[11,1],[16,1],[12,1],[7,1],[101,1]],      # E_7+A_1
       [[1,1],[15,1],[16,1],[17,1],[6,1],[7,1],[101,1]],             # E_7
       [[8,1],[9,1],[10,1],[11,1],[16,1],[12,1],[13,1],[102,1]],     # D_8
       [[8,1],[15,1],[16,1],[17,1],[18,1],[19,1],[7,1],[101,1]],     # E_7(a_1)+A_1
       [[1,1],[15,1],[16,1],[17,1],[24,1],[13,1],[101,1]],           # E_7(a_1)
       [[1,1],[15,1],[16,1],[17,1],[18,1],[24,1],[13,1],[102,1]],    # D_8(a_1)       ?
       [[1,1],[15,1],[16,1],[17,1],[18,1],[19,1],[103,1]],           # D_7
       [[14,1],[15,1],[21,1],[17,1],[18,1],[29,1],[19,1],[101,1]],   # E_7(a_2)+A_1
       [[20,1],[21,1],[17,1],[23,1],[24,1],[7,1],[101,1]],           # E_7(a_2)
       [[14,1],[20,1],[21,1],[22,1],[18,1],[33,1],[13,1],[102,1]],   # A_8
       [[20,1],[21,1],[28,1],[23,1],[24,1],[7,1],[101,1]],           # E_6+A_1
       [[14,1],[22,1],[23,1],[24,1],[19,1],[25,1],[35,1],[102,1]],   # D_7(a_1)
       [[14,1],[22,1],[23,1],[24,1],[19,1],[25,1],[102,1]],          # (D_7(a_1))_2
       [[20,1],[21,1],[23,1],[24,1],[7,1],[101,1]],                  # E_6
       [[20,1],[21,1],[22,1],[23,1],[24,1],[25,1],[102,1],[103,1]],  # D_8(a_2)
       [[8,1],[28,1],[23,1],[24,1],[25,1],[30,1],[102,1]],           # D_6+A_1
       [[20,1],[21,1],[28,1],[23,1],[24,1],[10,1],[40,1],[103,1]],   # A_7
#       [[20,1],[21,1],[28,1],[23,1],[24,1],[19,1],[103,1]],          # (A_7)_3
       [[20,1],[21,1],[28,1],[23,1],[31,1],[101,1],[102,1]],         # E_6(a_1)+A_1
       [[1,1],[28,1],[29,1],[30,1],[31,1],[101,1]],                  # D_6
       [[20,1],[21,1],[28,1],[29,1],[25,1],[31,1],[103,1]],          # D_7(a_2)
       [[20,1],[21,1],[23,1],[31,1],[101,1],[102,1]],                # E_6(a_1)
       [[26,1],[28,1],[27,1],[29,1],[30,1],[31,1],[102,1],[103,1]],  # D_5+A_2
       [[26,1],[28,1],[27,1],[29,1],[30,1],[31,1],[102,1]],          # (D_5+A_2)_2
       [[20,1],[21,1],[28,1],[29,1],[30,1],[31,1],[105,1]],          # A_6+A_1
       [[28,1],[27,1],[29,1],[30,1],[31,1],[39,1],[102,1]],          # D_6(a_1)+A_1
       [[28,1],[29,1],[33,1],[31,1],[34,1],[101,1]],                 # D_6(a_1)
       [[29,1],[21,1],[20,1],[30,1],[31,1],[105,1]],                 # A_6
#       [[32,1],[33,1],[30,1],[32,1],[40,1],[101,1]],                 # D_5+A_1        ??? two times 32
       [[26,1],[29,1],[35,1],[38,1],[30,1],[44,1],[47,1],[105,1]],   # 2A_4           ? 26
       [[32,1],[37,1],[29,1],[31,1],[34,1],[105,1],[107,1]],         # A_5+A_2
       [[32,1],[37,1],[27,1],[33,1],[40,1],[36,1],[105,1]],          # A_5+2A_1
       [[32,1],[29,1],[31,1],[34,1],[106,1],[108,1]],                # D_6(a_2)
       [[30,1],[31,1],[32,1],[33,1],[101,1]],                        # D_5
       [[37,1],[33,1],[40,1],[34,1],[36,1],[41,1],[105,1]],          # D_5(a_1)+A_2   ? 26/20
       [[26,1],[27,1],[40,1],[41,1],[106,1],[107,1]],                # (A_5+A_1)'
       [[32,1],[27,1],[37,1],[33,1],[36,1],[105,1]],                 # (A_5+A_1)''
       [[37,1],[38,1],[40,1],[49,1],[41,1],[104,1],[108,1]],         # D_4+A_2
       [[37,1],[38,1],[40,1],[49,1],[41,1],[104,1]],                 # (D_4+A_2)_2
       [[37,1],[38,1],[40,1],[34,1],[36,1],[106,1],[107,1]],         # A_4+A_3
       [[20,1],[21,1],[49,1],[106,1],[107,1]],                       # A_5
       [[37,1],[42,1],[43,1],[44,1],[45,1],[103,1]],                 # D_5(a_1)+A_1
       [[37,1],[38,1],[39,1],[40,1],[41,1],[108,1],[109,1]],         # A_4+A_2+A_1

       [[38,1],[40,1],[39,1],[41,1],[108,1],[109,1]],       # A_4+A_2
       [[42,1],[43,1],[48,1],[49,1],[102,1]],               # D_5(a_1)
       [[47,1],[48,1],[49,1],[53,1],[101,1]],               # D_4+A_1
       [[42,1],[43,1],[44,1],[45,1],[107,1],[108,1]],       # A_4+2A_1
       [[47,1],[48,1],[49,1],[101,1]],                      # D_4
       [[42,1],[48,1],[49,1],[106,1],[107,1]],              # A_4+A_1
       [[37,1],[38,1],[39,1],[49,1],[108,1],[113,1]],       # 2A_3
       [[42,1],[48,1],[106,1],[107,1]],                     # A_4
       [[42,1],[44,1],[48,1],[49,1],[110,1],[113,1]],       # D_4(a_1)+A_2
       [[46,1],[47,1],[48,1],[49,1],[112,1],[113,1]],       # A_3+A_2+A_1
       [[46,1],[47,1],[48,1],[112,1],[116,1],[119,1]],      # A_3+A_2
       [[46,1],[47,1],[48,1],[112,1],[116,1]],              # (A_3+A_2)_2
       [[53,1],[47,1],[48,1],[115,1],[116,1]],              # D_4(a_1)+A_1
       [[53,1],[54,1],[55,1],[112,1],[113,1]],              # A_3+2A_1
       [[47,1],[48,1],[115,1],[116,1]],                     # D_4(a_1)
       [[53,1],[54,1],[55,1],[117,1],[118,1],[119,1]],      # 2A_2+2A_1
       [[55,1],[56,1],[112,1],[113,1]],                     # A_3+A_1
       [[56,1],[57,1],[117,1],[118,1],[119,1]],             # 2A_2+A_1
       [[63,1],[106,1],[107,1]],                            # A_3
       [[56,1],[57,1],[117,1],[118,1]],                     # 2A_2
       [[60,1],[126,1],[127,1],[128,1]],                    # A_2+2A_1
       [[58,1],[59,1],[123,1],[124,1],[125,1]],             # A_2+3A_1
       [[63,1],[128,1],[129,1]],                            # A_2+A_1
       [[127,1],[130,1]],                                   # A_2
       [[63,1],[135,1],[136,1],[137,1]],                    # 4A_1
       [[141,1],[142,1],[143,1]],                           # 3A_1
       [[150,1],[151,1]],                                   # 2A_1
       [[157,1]]                                            # A_1
       ];

labels:=["E_8",
         "E_8(a_1)",
         "E_8(a_2)",
         "E_7+A_1",
         "E_7",
         "D_8",
         "E_7(a_1)+A_1",
         "E_7(a_1)",
         "D_8(a_1)",
         "D_7",
         "E_7(a_2)+A_1",
         "E_7(a_2)",
         "A_8",
         "E_6+A_1",
         "D_7(a_1)",
         "(D_7(a_1))_2",
         "E_6",
         "D_8(a_2)",
         "D_6+A_1",
         "A_7",
#         "(A_7)_3",
         "E_6(a_1)+A_1",
         "D_6",
         "D_7(a_2)",
         "E_6(a_1)",
         "D_5+A_2",
         "(D_5+A_2)_2",
         "A_6+A_1",
         "D_6(a_1)+A_1",
         "D_6(a_1)",
         "A_6",
#         "D_5+A_1",
         "2A_4",
         "A_5+A_2",
         "A_5+2A_1",
         "D_6(a_2)",
         "D_5",
         "D_5(a_1)+A_2",
         "(A_5+A_1)'",
         "(A_5+A_1)''",
         "D_4+A_2",
         "(D_4+A_2)_2",
         "A_4+A_3",
         "A_5",
         "D_5(a_1)+A_1",
         "A_4+A_2+A_1",

         "A_4+A_2",
         "D_5(a_1)",
         "D_4+A_1",
         "A_4+2A_1",
         "D_4",
         "A_4+A_1",
         "2A_3",
         "A_4",
         "D_4(a_1)+A_2",
         "A_3+A_2+A_1",
         "A_3+A_2",
         "(A_3+A_2)_2",
         "D_4(a_1)+A_1",
         "A_3+2A_1",
         "D_4(a_1)",
         "2A_2+2A_1",
         "A_3+A_1",
         "2A_2+A_1",
         "A_3",
         "2A_2",
         "A_2+2A_1",
         "A_2+3A_1",
         "A_2+A_1",
         "A_2",
         "4A_1",
         "3A_1",
         "2A_1",
         "A_1",
         ];

I:=[ [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ] ];#, [  ], [  ] ];

II:=[ [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ] ];#, [  ], [  ] ];

tori:=[ [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ], [  ] ];#, [  ], [  ] ];

#blocks:=[];
blocks:=[[[32, 7], [24, 1]], [[32, 5], [28, 1], [16, 3], [12, 1]], [[32, 3], [26, 1], [16, 7], [14, 1]], [[32, 1], [30, 1], [24, 2], [22, 2], [16, 3], [14, 1], [8, 4]], [[32, 1], [26, 3], [22, 1], [18, 3], [16, 1], [10, 3], [8, 1], [2, 3], [1, 2]], [[16, 14], [12, 2]], [[16, 11], [14, 3], [10, 2], [6, 1], [2, 1], [1, 2]], [[16, 11], [14, 3], [10, 2], [6, 1], [2, 1], [1, 2]], [[16, 10], [10, 6], [8, 1], [6, 1], [2, 6], [1, 2]], [[16, 7], [12, 9], [4, 6], [2, 2]], [[16, 10], [12, 2], [10, 2], [8, 3], [6, 1], [4, 2], [3, 2]], [[16, 10], [10, 6], [8, 1], [6, 1], [2, 6], [1, 2]], [[16, 6], [13, 2], [8, 14], [7, 2]], [[16, 10], [10, 6], [8, 1], [6, 1], [2, 6], [1, 2]], [[16, 3], [14, 5], [10, 2], [8, 10], [6, 4], [2, 2], [1, 2]], [[16, 3], [14, 1], [12, 6], [10, 2], [8, 7], [6, 1], [4, 8]], [[16, 10], [10, 6], [8, 1], [6, 1], [1, 14]], [[16, 2], [15, 2], [12, 4], [11, 4], [8, 6], [7, 2], [4, 8]], [[16, 3], [14, 5], [10, 2], [8, 10], [6, 4], [2, 2], [1, 2]], [[8, 4], [7, 6], [6, 8], [5, 8], [4, 10], [3, 6], [2, 10], [1, 8]], [[16, 2], [14, 2], [13, 2], [12, 2], [11, 2], [10, 2], [9, 2], [8, 4], [6, 2], [5, 2], [4, 4], [2, 4]], [[16, 1], [14, 5], [10, 10], [8, 1], [6, 5], [2, 10], [1, 4]], [[8, 28], [6, 4]], [[16, 2], [13, 6], [11, 2], [9, 6], [8, 2], [5, 6], [4, 2], [1, 8]], [[8, 27], [6, 1], [4, 5], [2, 3]], [[8, 27], [6, 1], [4, 4], [3, 2], [2, 2]], [[8, 24], [7, 2], [6, 4], [4, 2], [3, 2], [2, 2]], [[8, 27], [6, 1], [4, 5], [2, 1], [1, 4]], [[8, 27], [6, 1], [4, 5], [2, 1], [1, 4]], [[8, 22], [7, 6], [5, 4], [3, 2], [1, 4]], [[8, 20], [7, 4], [4, 12], [3, 4]], [[8, 20], [6, 6], [4, 8], [3, 2], [2, 6], [1, 2]], [[8, 20], [6, 4], [5, 4], [4, 6], [3, 2], [2, 6], [1, 2]], [[8, 14], [6, 18], [2, 12], [1, 4]], [[8, 27], [6, 1], [2, 6], [1, 14]], [[8, 13], [6, 3], [4, 30], [3, 2]], [[8, 14], [6, 18], [2, 12], [1, 4]], [[8, 20], [5, 12], [4, 2], [3, 2], [1, 14]], [[8, 11], [6, 7], [4, 26], [1, 14]], [[8, 11], [6, 7], [4, 26], [1, 14]], [[8, 12], [7, 2], [6, 2], [4, 30], [3, 2]], [[8, 14], [6, 18], [2, 6], [1, 16]], [[8, 11], [6, 7], [4, 26], [2, 6], [1, 2]], [[8, 10], [7, 2], [6, 4], [5, 4], [4, 24], [2, 6], [1, 2]], [[8, 6], [7, 10], [5, 4], [4, 20], [3, 8], [1, 6]], [[8, 11], [6, 7], [4, 26], [1, 14]], [[8, 1], [6, 27], [2, 36], [1, 6]], [[8, 6], [7, 2], [6, 12], [5, 4], [4, 14], [3, 2], [2, 16]], [[8, 1], [6, 27], [2, 26], [1, 26]], [[8, 4], [7, 6], [6, 8], [5, 8], [4, 10], [3, 6], [2, 10], [1, 8]], [[4, 60], [2, 4]], [[8, 2], [7, 10], [5, 20], [4, 2], [3, 10], [1, 24]], [[4, 56], [3, 8]], [[4, 54], [3, 2], [2, 12], [1, 2]], [[4, 54], [3, 2], [2, 10], [1, 6]], [[4, 50], [3, 10], [2, 6], [1, 6]], [[4, 54], [3, 2], [2, 10], [1, 6]], [[4, 46], [2, 30], [1, 4]], [[4, 54], [3, 2], [1, 26]], [[4, 44], [3, 4], [2, 28], [1, 4]], [[4, 46], [2, 24], [1, 16]], [[4, 40], [3, 12], [2, 18], [1, 16]], [[4, 46], [2, 10], [1, 44]], [[4, 28], [3, 36], [1, 28]], [[4, 22], [3, 14], [2, 52], [1, 14]], [[4, 26], [3, 6], [2, 62], [1, 2]], [[4, 14], [3, 30], [2, 34], [1, 34]], [[4, 2], [3, 54], [1, 78]], [[2, 120], [1, 8]], [[2, 110], [1, 28]], [[2, 92], [1, 64]], [[2, 58], [1, 132]]];

#ords:=[];
ords:=[ 32, 32, 32, 32, 32, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 8, 16, 16, 8, 16, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 4, 8, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2 ];

return [reps,tori,labels,I,II,ords,blocks,mizuno];


text:
MPICommunicator := grd -> AParMPI(grd);

Class(TArrayND, TArrayBase, rec(
    isArrayT := true,
    toPtrType := self >> TPtr(self.t),
    doHashValues := true,

     __call__ := (self, t, sizes, linearization) >>
        WithBases(self, rec(
        t    := Checked(IsType(t), t),
        sizes := sizes,
        linearization := linearization,
        operations := TypOps)),
    print := self >> Print(self.__name__, "(", self.t, ", ", self.sizes, ", ", self.linearization, ")"),

    rChildren := self >> [self.t, self.sizes, self.linearization],
    rSetChild := rSetChildFields("t", "sizes", "linearization"),
    free := self >> []
));

Class(TGlobalArrayND, TArrayBase, rec(
    isArrayT := true,
    toPtrType := self >> TPtr(self.t),
    doHashValues := true,

     __call__ := (self, pgrid, localArray) >>
        WithBases(self, rec(
        t    := localArray.t,
        pgrid := pgrid,
        localArray := localArray,
        operations := TypOps)),
    print := self >> Print(self.__name__, "(", self.pgrid, ", ", self.localArray, ")"),

    rChildren := self >> [self.t, self.pgrid, self.localArray],
    rSetChild := rSetChildFields("t", "pgrid", "localArray"),
    free := self >> []
));

Class(TPtrGlobalArrayND, TPtr, rec(
    doHashValues := true,

     __call__ := (self, pgrid, localArray) >>
        WithBases(self, rec(
        t    := localArray.t,
        pgrid := pgrid,
        localArray := localArray,
        operations := TypOps)),
    print := self >> Print(self.__name__, "(", self.pgrid, ", ", self.localArray, ")"),

    rChildren := self >> [self.t, self.pgrid, self.localArray],
    rSetChild := rSetChildFields("t", "pgrid", "localArray"),
    free := self >> []
));

max_stars_repo_name: spiral-software/spiral-package-mpi

max_issues_repo_name: spiral-software/spiral-package-mpi

max_forks_repo_name: spiral-software/spiral-package-mpi


text:
# Here an implementation with no optimization (O(n^2)).
# In GAP, E(n) = exp(2*i*pi/n), a primitive root of the unity.

Fourier := function(a)
	local n, z;
	n := Size(a);
	z := E(n);
	return List([0 .. n - 1], k -> Sum([0 .. n - 1], j -> a[j + 1]*z^(-k*j)));
end;

InverseFourier := function(a)
	local n, z;
	n := Size(a);
	z := E(n);
	return List([0 .. n - 1], k -> Sum([0 .. n - 1], j -> a[j + 1]*z^(k*j)))/n;
end;

Fourier([1, 1, 1, 1, 0, 0, 0, 0]);
# [ 4, 1-E(8)-E(8)^2-E(8)^3, 0, 1-E(8)+E(8)^2-E(8)^3,
#   0, 1+E(8)-E(8)^2+E(8)^3, 0, 1+E(8)+E(8)^2+E(8)^3 ]

InverseFourier(last);
# [ 1, 1, 1, 1, 0, 0, 0, 0 ]


text:
SetRecursionTrapInterval(100000);
# No limit (may crash GAP if recursion is not controlled) :
SetRecursionTrapInterval(0);


text:
"GameInfo"
{
	game 		"Dota 2"
	title 		"Dota 2"

	gamelogo 1
	type		multiplayer_only

	nomodels 1
	nohimodel 1
	nocrosshair 0
	GameData	"dota.fgd"
	SupportsDX8	0
	nodegraph 0
	tonemapping 0 // Hide tonemapping ui in tools mode

	FileSystem
	{
		SteamAppId				570
		BreakpadAppId			373300	// Report crashes under beta DLC, not the S1 game.  Delete this when all clients are switched to S2
		BreakpadAppId_Tools		375360  // Use a separate bucket of buckets for "-tools" crashes so that they don't get drowned out by game crashes. Falls back to BreakpadAppId/SteamAppId if missing

		//
		// The code that loads this file automatically does a few things here:
		//
		// 1. For each "Game" search path, it adds a "GameBin" path, in <dir>\bin
		// 2. For each "Game" search path, it adds another "Game" path in front of it with _<langage> at the end.
		//    For example: c:\hl2\cstrike on a french machine would get a c:\hl2\cstrike_french path added to it.
		// 3. For the first "Game" search path, it adds a search path called "MOD".
		// 4. For the first "Game" search path, it adds a search path called "DEFAULT_WRITE_PATH".
		//

		//
		// Search paths are relative to the exe directory\..\
		//
		SearchPaths
		{
			// These are optional language paths. They must be mounted first, which is why there are first in the list.
			// *LANGUAGE* will be replaced with the actual language name. If not running a specific language, these paths will not be mounted
			Game_Language		dota_*LANGUAGE*

			// These are optional low-violence paths. They will only get mounted if you're in a low-violence mode.
			Game_LowViolence	dota_lv

			Game				dota
			Game				core

			Mod					dota

			AddonRoot			dota_addons

			// Note: addon content is included in publiccontent by default.
			PublicContent		dota_core
			PublicContent		core
		}

		AddonsChangeDefaultWritePath 0
	}

	MaterialSystem2
	{
		RenderModes
		{
			"game" "Default"
			"game" "DotaDeferred"
			"game" "DotaForward"
			"game" "Depth"

			"tools" "ToolsVis" // Visualization modes for all shaders (lighting only, normal maps only, etc.)
			"tools" "ToolsWireframe" // This should use the ToolsVis mode above instead of being its own mode
			"tools" "ToolsUtil" // Meant to be used to render tools sceneobjects that are mod-independent, like the origin grid
		}
	}

	Engine2
	{
		"HasModAppSystems" "1"
		"Capable64Bit" "1"
		"UsesVGui" "0"
		"UsesScaleform" "1"
		"UsesPanorama" "1"
		"PanoramaUIClientFromClient" "1" // IPanoramaUIClient is implemented by client.dll
		"HasGameUI" "1" // dota uses gameui
		"GameUIFromClient" "1"  // AND that gameui comes from client.dll
		"URLName" "dota2"
		"MsaaOverrideType" "0"
		"UsesBink" "0"
        "MaxNetworkableEntities" "10000"
        "MaxNonNetworkableEntities" "10000"
        "DefaultDXVersion" "9"
        // The shader binary cache on Linux can be over 100MB so
        // we have to allow very large allocations.
		"AllocWarnMB_linuxsteamrt64" "200"
		// Also currently demo files are loaded entirely into
		// memory for 64-bit binaries so they can use well
		// over 100MB at load time.  Zoid is looking at
		// converting that to streaming.
		"AllocWarnMB_osx64" "200"
		"AllocWarnMB_pc64" "200"
		"AllocWarnMB" "100"
		// There are some known large virtual reservations, such as the SBH, which
		// bypass this limit so we can be fairly conservative.
		"ReserveWarnMB" "64"

		"RenderingPipeline"
		{
			"SkipPostProcessing" "1"
			"SupportsMSAA" "0"
		}

		"BugBait"
		{
			// Used by 'bug:' in chat to normalize report settings during playtests
			"Owner" "triage*"
			"Severity" "high"
			"Priority" "none"
			"Category" "---"
			"Product" "dota"
			"Component" "dota"
		}
	}

	SceneFileCache
	{
		"ServerUsesSceneImageFile" "0"
	}

	SceneSystem
	{
		"NoSunLightManager" "1"
		"TransformTextureRowCount" "256"
		"CMTAtlasWidth" "512"
		"CMTAtlasHeight" "512"
		"CMTAtlasChunkSize" "128"
		"DrawParticleChildrenSeparateFromParents" "1"
	}

	SoundSystem
	{
		"DisableSteamAudio" "1"
		"DefaultWindowsXAudio" "1"
	}

	ToolsEnvironment
	{
		"Engine"	"Source 2"
		"ToolsDir"	"../sdktools"	// NOTE: Default Tools path. This is relative to the mod path.
		"DeveloperHelpURL" "https://developer.valvesoftware.com/wiki/Dota_2_Workshop_Tools"
		"ToolsProductName" "Dota2 Workshop Tools"
	}

	Hammer
	{
		"fgd"					"dota.fgd"	// NOTE: This is relative to the 'mod' path.
		"GameFeatureSet"		"Dota"
		"LoadScriptEntities"	"0"
		"DefaultTextureScale"	"0.250000"
		"DefaultSolidEntity"	"trigger_dota"
		"DefaultPointEntity"	"info_player_start_dota"
		"NavMarkupEntity"		"func_nav_markup"
		"EnableDotaTools"		"1"
		"DefaultGridTileSet"	"/maps/tilesets/radiant_basic.vmap"
		"DefaultGridTileSet2"	"/maps/tilesets/dire_basic.vmap"
		"DotaMaxTrees"			"8000"
		"AddonMapCommand"		"dota_launch_custom_game"
		"PostMapLoadCommands"	"jointeam good" // Commands sent to the console by hammer after it finishes building a map and loads it
		"RequiredGameEntities"	"info_player_start_goodguys|info_player_start_dota; info_player_start_badguys|info_player_start_dota; env_global_light; ent_dota_game_events"
		"UnitsFiles"			"scripts/npc/npc_units.txt; scripts/npc/npc_units_custom.txt; scripts/npc/npc_heroes.txt"
		"ItemsFiles"			"scripts/npc/items.txt; scripts/npc/npc_items_custom.txt"
		"OverlayBoxSize"		"16"
		"TileGridBlendOrderBGRA"	"1"
		"TileGridBlendDefaultColor"	"0 255 0"
	}

	MaterialEditor
	{
		"DefaultShader"			"global_lit_simple"
		"ExpressionHelpUrl"		"https://intranet.valvesoftware.com/index.php/Source_2.0/Shader_Format#Shader.2FMaterial_Expression_Syntax"
	}

	ResourceCompiler
	{
		// Overrides of the default builders as specified in code, this controls which map builder steps
		// will be run when resource compiler is run for a map without specifiying any specific map builder
		// steps. Additionally this controls which builders are displayed in the hammer build dialog.
		DefaultMapBuilders
		{
			"light"		"0"	// Dota does not use baked lighting
			"envmap"	"0"	// Dota doesn't generate environment maps from the map
			"gridnav"	"1"	// Dota generates its grid navigation data by default
		}
		"DotaTileGrid"	"1"
	}

	RenderPipelineAliases
	{
		"Tools"			"Dota:Forward"
		"EnvMapBake"	"Dota"
	}

	RenderSystem
	{
		// rendersystemvulkan setting that determines how many partitions scenesystem places
		// in each job. The higher the number, the more work per command buffer. Vulkan has higher
		// cost per command buffer than software contexts so settings this higher reduces
		// overall number of command buffers.
		"VulkanSceneSystemJobCost"		"2"
	}
}