Search

Dynamic Programming

Standard Dynamic Programming

n := 15; k := -1;           # transform parameters
opts := SpiralDefaults;     # default options
opts.globalUnrolling := 16; # set smaller unrolling
t := DFT(n, k);             # transform
best := DP(t, rec(), opts); # run search
rt := best[1].ruletree;     # get best rule tree

Hashing and Custom Measure Functions

dpopts := rec(verbosity := 5, hashTable := HashTableDP());
dpopts.measureFunction := (rt, opts) ->
        let(c:= CodeRuleTree(rt, opts),    # generate code
                Length(Filtered(           # count flops in code
                        Collect(c, @(1,[add, sub, mul, neg])), i->i.t=TReal)));
best := DP(t, dpopts, opts);    # run search with flop minimization
#look what’s in the hash table
HashLookup(dpopts.hashTable, DFT(5, 1))[1].ruletree;
HashLookup(dpopts.hashTable, DFT(5,-1));

# now time the tree found through flop minimization
rt1 := HashLookup(dpopts.hashTable, DFT(15, 1))[1].ruletree;
DPMeasureRuleTree(rt1, opts);