I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700. I want to compute $f(x)$ and $g(x)$ simultaneously as efficiently as possible. I'm looking for an algorithms that say me how to do that.
For example, let $f(x) = ax^3 + bx^2 + x$ and $g(x) = x^3 + ax^2 + bx$. We have $f(x) = x^2(ax + b) + x$ and $g(x) = x(x^2) + x(ax+b)$. So we first compute $x^2$ and $ax+b$ and then use them to compute $f(x)$ and $g(x)$. Here, the optimization is evaluating $x^2$ and $ax+b$ one time for both $f$ and $g$.
Is there a algorithm that can show us how we should compute $f(x)$ and $g(x)$ in fewest computations (for a computer)? In other words, the algorithm should receive $f$ and $g$ as input and then return an algorithm for computing them.
I guess we can use algebra( some ring theory, ideal,...) or graph theory to model this problem.
Both $f$ and $g$ are of the form $af_a(x)+bf_b(x)+f_1(x) $ (and similarly for $g$) where the $f_c(x)$ are polynomials with all coefficients one (if I have interpreted you correctly).
If these polynomials have stretches where all the coefficients are one, you can use
$\begin{array}\\ \sum_{k=i}^j x^k &=x^i\sum_{k=i}^j x^{k-i}\\ &=x^i\sum_{k=0}^{j-i} x^{k}\\ &=x^i\frac{x^{j-i+1}-1}{x-1}\\ &=\frac{x^{j+1}-x^i}{x-1}\\ \end{array} $
to quickly sum these stretches. You can also precompute $x-1$ and divide the sum of these numerators by that.
Anything more depends on the detailed structure of the polynomials.