# Theoretical precision needed to get $n$-bits of the evaluation of some sum

Let $P,Q$ two integral polynomials of height bounded by let say $H>0$ --- that is every coefficient of $p$ or $Q$ is bounded in absolute value by $H$ --- and degree at most $d$.

Let $A$ a set of $d$ reals.

I want to evaluate the sum: $$S = \sum_{\alpha \in A} P(\alpha)Q(\alpha),$$ and more precisely I want to get the $n$ first bits of this value.

I can assert that this sum is bounded by a constant $K'>0$.

What would be the minimal number of bits of precision on the elements $\alpha\in A$ I need to be able to compute the $n$ first bits of $S$?

NB: The representation of the reals of $A$ can be whatever (fixed point, floating point, ... ) I'm able to efficiently compute them at arbitrary precision.

• It might help to include a definition of the height of a polynomial in the question. – D.W. Oct 23 '17 at 5:56

I may be misunderstanding the question, but I don't think we have enough information to tell.

Consider, for example:

$$A = \left\{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \right\}$$

and:

$$P(x) = \left( x - \frac{1}{4} - \varepsilon \right) \left( x - \frac{1}{2} + \varepsilon \right) \left( x - \frac{3}{4} - \varepsilon \right)$$ $$Q(x) = 1$$

for some small $\varepsilon$.

Assuming that $\varepsilon$ is small enough, both polynomials are height-bounded by 1.

The sum is:

$$S = - \frac{5}{16}\varepsilon + \varepsilon^3$$

The question is how you would evaluate $P$.

$$P(x) = \left(-\frac{3}{32} - \frac{5}{16}\varepsilon + \frac{1}{2}\varepsilon^2 + \varepsilon^3\right) + \left( \frac{11}{16} + \varepsilon - \varepsilon^2\right) x + \left(-\frac{3}{2} - \varepsilon\right) x^2 + x^3$$

The number of bits of precision on the elements of $A$ are not relevant here; they are precisely representable with two significant bits. It seems to me that the precision you need to do the intermediate computation is more important.

For a small enough $\varepsilon$, you are going to get catastrophic cancellation whether you use the factorised form of $P$ or you use a method such as Horner's rule. At the very least, you need enough bits to represent $-\frac{3}{32} - \frac{5}{16}\varepsilon$ such that you have $n$ significant bits in the $\varepsilon$ term, so you can subtract $-\frac{3}{32}$ to get a good enough answer.

• I agree with you on the problem of "internal representation", but in your case, I have the impression that you consider that the coefficients of $P$ are approximated. Maybe I didn't make the point clear in the question, but $P$ and $Q$ are exactly known since they are integrals. – Sn0w Oct 23 '17 at 7:47
• OK, that is important information. In numeric analysis, details matter, and I still think we probably don't have enough detail. – Pseudonym Oct 23 '17 at 23:02
• It's the only pieces of information I have, unhopefully. – Sn0w Oct 24 '17 at 12:35