# Errors with many coefficients in EvalPoly?

**URL:** <https://openfhe.discourse.group/t/errors-with-many-coefficients-in-evalpoly/443>\
**Category:** Library Questions\
**Created:** [March 31, 2023, 4:12pm UTC](https://openfhe.discourse.group/t/errors-with-many-coefficients-in-evalpoly/443 "2023-03-31T16:12:56Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\
**Post date:** [March 31, 2023, 4:12pm UTC](https://openfhe.discourse.group/t/errors-with-many-coefficients-in-evalpoly/443/1 "2023-03-31T16:12:56Z")

</div>

Hello! I am trying to evaluate the square root of two using CKKS.

I wrote a function to calculate Taylor’s coefficients, and then I evaluate the polynomial using EvalPoly. The program work when I use degree = 8, but when I try degree = 16, the output is totally incorrect.

This is the code: [https://pastebin.com/1e3XcuEw](https://pastebin.com/1e3XcuEw)

Output:  
Coefficients: [0.707107 0.707107 -0.353553 0.353553 -0.441942 0.618718 -0.928078 1.45841]  
Result: (0.321228, 0.44753, 0.547732, 0.632456, 0.707107, …)

Output as expected!

However, when I change on line 70 degree to 16, this is the incorrect output:

Coefficients: [0.707107 0.707107 -0.353553 0.353553 -0.441942 0.618718 -0.928078 1.45841 -2.36991 3.94985 -6.71475 11.5982 -20.2969 35.9098 -64.1247 115.424]  
Result: (-3227.72, -2165.06, -1290.68, -594.332, -62.1743, … )

The coefficients are not that big, so I’m surprised it fails! Am I missing something?

---

<div class="post-metadata">

**Author:** ![iquah](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/iquah/32/8_2.png) [@iquah](https://openfhe.discourse.group/u/iquah)\
**Post date:** [March 31, 2023, 5:02pm UTC](https://openfhe.discourse.group/t/errors-with-many-coefficients-in-evalpoly/443/2 "2023-03-31T17:02:12Z")

</div>

In the following example, [openfhe-development/function-evaluation.cpp at main · openfheorg/openfhe-development · GitHub](https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/function-evaluation.cpp), we do a square root evaluation using CKKS with a utility function we provide, `EvalChebyshevFunction`. Is there a reason you’re using Taylor coefficients?

Also, check out [openfhe-development/FUNCTION\_EVALUATION.md at main · openfheorg/openfhe-development · GitHub](https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/FUNCTION_EVALUATION.md) which is a useful companion read for the code

---

<div class="post-metadata">

**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\
**Post date:** [March 31, 2023, 8:30pm UTC](https://openfhe.discourse.group/t/errors-with-many-coefficients-in-evalpoly/443/3 "2023-03-31T20:30:03Z")

</div>

No particular reason for Taylor, just playing around with the library, but I thought there was a issue so I reported it! Thanks for the tip though 🙂

---

<div class="post-metadata">

**Author:** ![Pro7ech](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/pro7ech/32/301_2.png) [@Pro7ech](https://openfhe.discourse.group/u/Pro7ech)\
**Post date:** [April 1, 2023, 1:05pm UTC](https://openfhe.discourse.group/t/errors-with-many-coefficients-in-evalpoly/443/4 "2023-04-01T13:05:43Z")

</div>

@narger I highly suspect this is a plaintext overlfow issue. This means that at some point during computation the norm of at least one of the plaintext coefficients (not slots) became larger than half the current modulus, corrupting the plaintext. Using the standard power basis is not numerically stable with the CKKS scheme. If you keep increasing the degree of the polynomial, a value greater than 1 will eventually blow up, and inversely, a value smaller than 1 will eventually vanish. This is what happened to this work [BLEACH: Cleaning Errors in Discrete Computations over CKKS](https://eprint.iacr.org/2022/1298), which didn’t use the Chebyshev basis (see Appendix A).

Using the Chebyshev basis solves this numerical instability issue because it has a natural change of basis x’ = (2x-a-b)/(b-a) for a given interval [a, b], which ensures that -1\<=x’\<=1, but also that with higher power the value doesn’t vanish. This not only avoids plaintext overflow issues, but it also drastically reduces the variances of the power basis, which reduces the added error (CKKS works a little bit like floating point numbers, it has a fixed precision, and a small value added to a large value gets flooded by noise).

For example, if you take TableA1 of the work I referenced and compute the standard deviation of the coefficients, you get 59718 = 2^{15.86} which means that they will lose, just because of the distribution of the coefficients of the polynomial, close to 16 bits of precision. On top of this, you can add the numerical instability of computing x^{i} for large i.

If instead you use the Chebyshev basis for the same polynomial, you get a standard deviation of about 0.25.

---

<div class="post-metadata">

**Author:** ![narger](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/narger/32/420_2.png) [@narger](https://openfhe.discourse.group/u/narger)\
**Post date:** [April 1, 2023, 4:24pm UTC](https://openfhe.discourse.group/t/errors-with-many-coefficients-in-evalpoly/443/5 "2023-04-01T16:24:35Z")

</div>

Amazing, thank you for the detailed explaination!!