codegen - Maple Programming Help

Home : Support : Online Help : Programming : codegen Package : codegen/optimize

codegen

 optimize
 common subexpression optimization

 Calling Sequence optimize(expr)

Parameters

 expr - expression, array, list of equations, or a procedure

Description

 • The input to optimize must be either a single algebraic expression, an array of algebraic expressions (for example a matrix of formulae), a list of equations of the form  name = algebraic  (meaning a computation sequence''), or a Maple procedure.
 • If the input is not a Maple procedure, the output from optimize is a sequence of equations of the form  name = algebraic representing an optimized computation sequence'' for the input expression. Each equation in the sequence corresponds to an assignment. The global variables $\mathrm{t0},\mathrm{t1},\mathrm{t2},\dots$ are used for temporary (local) variables in the computation sequence.
 • If the input is a Maple procedure, the output is the optimized Maple procedure. Presently optimize can only optimize simple procedures which are computation sequences'' i.e. consist of a sequence of simple assignment statements -- they contain no if statements or for loops.
 • If the input is a computation sequence of the form

$\left[\mathrm{s1}=\mathrm{f1}\left(x\right),\mathrm{s2}=\mathrm{f2}\left(x,\mathrm{s1}\right),...,\mathrm{sn}=\mathrm{fn}\left(x,\mathrm{s1},...,\mathrm{sn}\right)\right]$

 then this understood to be equivalent to the Maple procedure

 proc(x) global s1,s2,...,sn; s1 := f1(x); s2 := f2(x,s1); ... sn := fn(x,s1,s2,...,sn); end proc

 So the names $\mathrm{s1},\mathrm{s2},...,\mathrm{sn}$ in the computation sequence are regarded as global variables which cannot be removed from the computation sequence. The optional arguments globals=[g1,g2,...,gm], parameters=[p1,p2,...,pm], and locals=[l1,l2,...,lm] may be used to specify otherwise.
 • The optimize function is designed to optimize only computation sequences

$\left[\mathrm{s1}=\mathrm{f1}\left(x\right),\mathrm{s2}=\mathrm{f2}\left(x,\mathrm{s1}\right),...,\mathrm{sn}=\mathrm{fn}\left(x,\mathrm{s1},...,\mathrm{sn}\right)\right]$

 where x does not include any of $\mathrm{s1},\mathrm{s2},...,\mathrm{sn}$.  It is advised that the optimize function be used only when this condition is true; otherwise, unexpected results may be produced.
 • The optimize function makes use of Maple's option remember facility to identify common subexpressions in linear time and space. This means, however, that only those subexpressions which Maple has simplified to be identical are found. For example, the expression $x+y$ is not recognized as being common to  $x+y+z$. That is, optimize performs mainly syntactic'' optimizations.
 • If tryhard is given as an optional argument, a different algorithm is used which will give a better optimized output but will consume more time and memory.
 • Procedures containing calls to sum, add or piecewise must first be prepared for translation by calling codegen[prep2trans] and running optimize on the output.
 • The routine codegen[makeproc] can be used to create a Maple procedure from a single formula, an array of formulae, or a computation sequence.
 • The routine codegen[cost] can be used to give an operation count for the unoptimized and optimized input.
 • The command with(codegen,optimize) allows the use of the abbreviated form of this command.

Examples

 > $\mathrm{with}\left(\mathrm{codegen},\mathrm{optimize},\mathrm{makeproc},\mathrm{cost},\mathrm{prep2trans}\right):$
 > $f≔{x}^{4}-{x}^{3}$
 ${f}{≔}{{x}}^{{4}}{-}{{x}}^{{3}}$ (1)
 > $\mathrm{optimize}\left(f\right)$
 ${\mathrm{t1}}{=}{{x}}^{{2}}{,}{\mathrm{t2}}{=}{{\mathrm{t1}}}^{{2}}{,}{\mathrm{t4}}{=}{-}{\mathrm{t1}}{}{x}{+}{\mathrm{t2}}$ (2)
 > $f≔x\mathrm{ln}\left(x\right)+2{x}^{2}\mathrm{ln}\left(x\right)+3{x}^{3}\mathrm{ln}\left(x\right)$
 ${f}{≔}{x}{}{\mathrm{ln}}{}\left({x}\right){+}{2}{}{{x}}^{{2}}{}{\mathrm{ln}}{}\left({x}\right){+}{3}{}{{x}}^{{3}}{}{\mathrm{ln}}{}\left({x}\right)$ (3)
 > $\mathrm{optimize}\left(f\right)$
 ${\mathrm{t1}}{=}{\mathrm{ln}}{}\left({x}\right){,}{\mathrm{t3}}{=}{{x}}^{{2}}{,}{\mathrm{t9}}{=}{3}{}{\mathrm{t1}}{}{\mathrm{t3}}{}{x}{+}{2}{}{\mathrm{t1}}{}{\mathrm{t3}}{+}{\mathrm{t1}}{}{x}$ (4)
 > $\mathrm{cost}\left(f\right)$
 ${2}{}{\mathrm{additions}}{+}{8}{}{\mathrm{multiplications}}{+}{3}{}{\mathrm{functions}}$ (5)
 > $\mathrm{cost}\left(\mathrm{optimize}\left(f\right)\right)$
 ${\mathrm{functions}}{+}{3}{}{\mathrm{assignments}}{+}{7}{}{\mathrm{multiplications}}{+}{2}{}{\mathrm{additions}}$ (6)
 > $\mathrm{cost}\left(f\right)-\mathrm{cost}\left(\mathrm{optimize}\left(f\right)\right)$
 ${\mathrm{multiplications}}{+}{2}{}{\mathrm{functions}}{-}{3}{}{\mathrm{assignments}}$ (7)
 > F := makeproc(f,x);
 ${F}{≔}{\mathbf{proc}}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{x}{*}{\mathrm{ln}}{}\left({x}\right){+}{2}{*}{x}{^}{2}{*}{\mathrm{ln}}{}\left({x}\right){+}{3}{*}{x}{^}{3}{*}{\mathrm{ln}}{}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (8)
 > $\mathrm{optimize}\left(F\right)$
 ${\mathbf{proc}}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t1}}{,}{\mathrm{t3}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t1}}{≔}{\mathrm{ln}}{}\left({x}\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t3}}{≔}{x}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{3}{*}{\mathrm{t1}}{*}{\mathrm{t3}}{*}{x}{+}{2}{*}{\mathrm{t1}}{*}{\mathrm{t3}}{+}{\mathrm{t1}}{*}{x}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (9)
 > $\mathrm{cs}≔\left[t=x,{r}_{1}=t{\left(x-y\right)}^{2},{r}_{2}=2{\left(y-x\right)}^{2}\right]:$
 > $\mathrm{optimize}\left(\mathrm{cs}\right)$
 ${t}{=}{x}{,}{\mathrm{t1}}{=}{x}{-}{y}{,}{\mathrm{t2}}{=}{{\mathrm{t1}}}^{{2}}{,}{{r}}_{{1}}{=}{x}{}{\mathrm{t2}}{,}{\mathrm{t4}}{=}{{\mathrm{t1}}}^{{2}}{,}{{r}}_{{2}}{=}{2}{}{\mathrm{t4}}$ (10)
 > $\mathrm{optimize}\left(\mathrm{cs},\mathrm{locals}=\left[t\right]\right)$
 ${\mathrm{t1}}{=}{x}{-}{y}{,}{\mathrm{t2}}{=}{{\mathrm{t1}}}^{{2}}{,}{{r}}_{{1}}{=}{x}{}{\mathrm{t2}}{,}{\mathrm{t4}}{=}{{\mathrm{t1}}}^{{2}}{,}{{r}}_{{2}}{=}{2}{}{\mathrm{t4}}$ (11)
 > F := makeproc(cs,x);
 ${F}{≔}{\mathbf{proc}}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{t}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{t}{≔}{x}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{[}{1}{]}{≔}{t}{*}\left({x}{-}{y}\right){^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{[}{2}{]}{≔}{2}{*}\left({y}{-}{x}\right){^}{2}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (12)
 > $\mathrm{optimize}\left(F\right)$
 ${\mathbf{proc}}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t1}}{,}{\mathrm{t2}}{,}{\mathrm{t4}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t1}}{≔}{x}{-}{y}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t2}}{≔}{\mathrm{t1}}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{[}{1}{]}{≔}{x}{*}{\mathrm{t2}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t4}}{≔}{\mathrm{t1}}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{[}{2}{]}{≔}{2}{*}{\mathrm{t4}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (13)
 > $A≔\mathrm{array}\left(\left[\left[{x}^{3},{x}^{2}\right],\left[{x}^{2},{x}^{4}\right]\right]\right)$
 ${A}{≔}\left[\begin{array}{cc}{{x}}^{{3}}& {{x}}^{{2}}\\ {{x}}^{{2}}& {{x}}^{{4}}\end{array}\right]$ (14)
 > $\mathrm{optimize}\left(A\right)$
 ${\mathrm{t1}}{=}{{x}}^{{2}}{,}{\mathrm{t3}}{=}{{\mathrm{t1}}}^{{2}}{,}{{A}}_{{1}{,}{1}}{=}{\mathrm{t1}}{}{x}{,}{{A}}_{{1}{,}{2}}{=}{\mathrm{t1}}{,}{{A}}_{{2}{,}{1}}{=}{\mathrm{t1}}{,}{{A}}_{{2}{,}{2}}{=}{\mathrm{t3}}$ (15)
 > g := proc(x,A::array(1..2)) A[1] := y*sin(x); A[2] := x^2*sin(x); end proc;
 ${g}{≔}{\mathbf{proc}}\left({x}{,}{A}{::}\left({\mathrm{array}}{}\left({1}{..}{2}\right)\right)\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{1}{]}{≔}{y}{*}{\mathrm{sin}}{}\left({x}\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{2}{]}{≔}{x}{^}{2}{*}{\mathrm{sin}}{}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (16)
 > $\mathrm{optimize}\left(g\right)$
 ${\mathbf{proc}}\left({x}{,}{A}{::}\left({\mathrm{array}}{}\left({1}{..}{2}\right)\right)\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t1}}{,}{\mathrm{t2}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t1}}{≔}{\mathrm{sin}}{}\left({x}\right){;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{1}{]}{≔}{y}{*}{\mathrm{t1}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t2}}{≔}{x}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{2}{]}{≔}{\mathrm{t1}}{*}{\mathrm{t2}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (17)
 > h := proc(x) local s,t,r; s := 1; t := x; r := t^2; r*s end proc;
 ${h}{≔}{\mathbf{proc}}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{s}{,}{t}{,}{r}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{s}{≔}{1}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{t}{≔}{x}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{≔}{t}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{*}{s}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (18)
 > $\mathrm{optimize}\left(h\right)$
 ${\mathbf{proc}}\left({x}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{≔}{x}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (19)
 > s := proc(a,b,c) local r,s; r := a*b+a*c; s := b*c+c^2;r-s;end proc;
 ${s}{≔}{\mathbf{proc}}\left({a}{,}{b}{,}{c}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{,}{s}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{≔}{a}{*}{b}{+}{a}{*}{c}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{s}{≔}{b}{*}{c}{+}{c}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{r}{-}{s}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (20)
 > $\mathrm{optimize}\left(s\right)$
 ${\mathbf{proc}}\left({a}{,}{b}{,}{c}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t4}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t4}}{≔}{c}{^}{2}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{a}{*}{b}{+}{a}{*}{c}{-}{b}{*}{c}{-}{\mathrm{t4}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (21)
 > $\mathrm{optimize}\left(s,'\mathrm{tryhard}'\right)$
 ${\mathbf{proc}}\left({a}{,}{b}{,}{c}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{result}}{,}{\mathrm{t1}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{t1}}{≔}{b}{+}{c}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{result}}{≔}{a}{*}{\mathrm{t1}}{-}{c}{*}{\mathrm{t1}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (22)
 > p := proc(x,m,n)   local i;   add( i * f(x-i), i = m .. n ) / add( f(x-i), i = m .. n ) end proc:
 > $q≔\mathrm{prep2trans}\left(p\right)$
 ${q}{≔}{\mathbf{proc}}\left({x}{,}{m}{,}{n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{i}{,}{\mathrm{i1}}{,}{\mathrm{i2}}{,}{\mathrm{s1}}{,}{\mathrm{s2}}{,}{\mathrm{t1}}{,}{\mathrm{t2}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s1}}{≔}{0}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{m}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{n}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s1}}{≔}{\mathrm{s1}}{+}{\mathrm{i1}}{*}{f}{}\left({x}{-}{\mathrm{i1}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s2}}{≔}{0}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i2}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{m}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{n}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s2}}{≔}{\mathrm{s2}}{+}{f}{}\left({x}{-}{\mathrm{i2}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s1}}{/}{\mathrm{s2}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (23)
 > $\mathrm{optimize}\left(q,'\mathrm{tryhard}'\right)$
 ${\mathbf{proc}}\left({x}{,}{m}{,}{n}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{i}{,}{\mathrm{i1}}{,}{\mathrm{i2}}{,}{\mathrm{s1}}{,}{\mathrm{s2}}{,}{\mathrm{t1}}{,}{\mathrm{t2}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s1}}{≔}{0}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i1}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{m}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{n}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s1}}{≔}{\mathrm{s1}}{+}{\mathrm{i1}}{*}{f}{}\left({x}{-}{\mathrm{i1}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s2}}{≔}{0}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{i2}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{m}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{n}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s2}}{≔}{\mathrm{s2}}{+}{f}{}\left({x}{-}{\mathrm{i2}}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{s1}}{/}{\mathrm{s2}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (24)