Consider the problem of computing a general numeric expression over integer variables, made of sums, products, products by a constant and powers. E.g. something like $(2xy^3 + 4y)(2z + 5)^3$.
However, the absolute value of each variable is bounded by a bound $B$ (i.e. $|x| \le B$), and you are interested in the value of the polynomial only if it does not itself go outside of the bound $B$ (i.e. $|f(\bar x)|\le B$).
Can I compute the value of the polynomial, or detecting that it overflows the bound, without ever storing intermediate results bigger than $B$?
The main problem is with something like $x^{100} - y^{99}$. The final value can be small, but the intermediate results can be exponentially larger. Can I, in some way, compute the result, or detect the overflow, without computing the large intermediate results?
For simplicity (if it helps), we can also assume $B=2^k$ for some $k$.