1) Rather than
x = (a * (y + (1 - a) * x)
you want
x = (a * (y - x) + x)
so you shave off a superfluous mult for each assignment.
Right, good point! We should do that. Maybe a smart compiler could do
the necessary deductions automatically? So it would go from
x = a * y + (1 - a) * x
to
x = a * y + x - a * x
to
x = a * (y - x) + x
via knowledge about the distrubutive law and knowledge about the cost
of addition/subtraction versus multiplication. I guess this is where
the compiler guys get into the picture -- I'm Cc'in Janus, Michael
and
Sigurd in case they have any input on this.
I am not aware of any of-the-shelf technique for this, but it would
be a fun problem to solve.
Define a cost function:
Gamma(+) = 5
Gamma(-) = 5
Gamma(*) = 10
I have no clue if these costs reflect the relative cost among the
operators, please correct me.
Given the size of an expressions that naturally appear in programs
I think it is reasonable efficient to compute all permutations of
the expression under the distributive law and then pick any one of
those with the lowest cost under the Gamma cost function.
This is worstcase exponential, but given the size of expressions
programmers are inclined to write in a program, then I don't think
it will be a problem.
We need to combine this with elimination of common subexpressions.
I have made a limited(yet) implementation of this in SMCL which can
rewrite
x = a * y + (1 - a) * x
to
x = a * y + x - a * x
Rewriting this to
x = a * (y - x) + x
should be pretty straight forward. I'll look at that tomorrow.
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
