# Approximation of square root without chebyshev interpolation

**URL:** <https://openfhe.discourse.group/t/approximation-of-square-root-without-chebyshev-interpolation/1813>\
**Category:** Show & Tell\
**Created:** [December 30, 2024, 4:14pm UTC](https://openfhe.discourse.group/t/approximation-of-square-root-without-chebyshev-interpolation/1813 "2024-12-30T16:14:18Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![DenisRed](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/denisred/32/303_2.png) [@DenisRed](https://openfhe.discourse.group/u/DenisRed)\
**Post date:** [December 30, 2024, 4:14pm UTC](https://openfhe.discourse.group/t/approximation-of-square-root-without-chebyshev-interpolation/1813/1 "2024-12-30T16:14:18Z")

</div>

Hi guys,  
I was searching for algorithms to approximate the square root without using Chebyshev interpolation.  
I want to show you my code for implementing the algorithm from [https://eprint.iacr.org/2019/417.pdf](https://eprint.iacr.org/2019/417.pdf) Section 3.2. It approximates the square root of values in an encrypted vector. Maybe this can also be helpful for you.

Here is my code for this algorithm:

 ![Screenshot 2024-12-30 at 15.10.52](https://canada1.discourse-cdn.com/flex031/uploads/openfhe/original/1X/34db175f9e236e03b10dde258f24ce703dafeaf7.png)

```auto
    auto ct_a = ct_input; // make sure to scale down your input values if necessary to meet the condition 0 ≤ x ≤ 1,
    auto ct_b = cc->EvalSub(ct_a, 1);

    int d = 7; // you need to play around with this to reach your required precision. A higher d consumes more levels!
    for (int n = 0; n < d; n++) {
        auto ct1 = cc->EvalSub(1, cc->EvalMult(ct_b, 0.5));
        ct_a = cc->EvalMult(ct_a, ct1);
        auto ct2 = cc->EvalMult(cc->EvalSub(ct_b, 3), 0.25);
        ct_b = cc->EvalMult(cc->EvalSquare(ct_b), ct2);
    }

// Don't forget to scale back ct_a if you scaled it down

```

With this code i reach very good precision for my use case.

---

<div class="post-metadata">

**Author:** ![DenisRed](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/denisred/32/303_2.png) [@DenisRed](https://openfhe.discourse.group/u/DenisRed)\
**Post date:** [January 1, 2025, 2:00pm UTC](https://openfhe.discourse.group/t/approximation-of-square-root-without-chebyshev-interpolation/1813/2 "2025-01-01T14:00:22Z")

</div>

Remark: A tighter lower/upper bound on x requires less iterations.

---

<div class="post-metadata">

**Author:** ![lujoho](https://avatars.discourse-cdn.com/v4/letter/l/a587f6/32.png) [@lujoho](https://openfhe.discourse.group/u/lujoho)\
**Post date:** [January 3, 2025, 11:25am UTC](https://openfhe.discourse.group/t/approximation-of-square-root-without-chebyshev-interpolation/1813/3 "2025-01-03T11:25:20Z")

</div>

Hi @DenisRed,

thank you for your insights.  
As you are looking around for square root approximations without Chebyshev, I recommend looking into [this](https://doi.org/10.1007/s10207-023-00781-0) paper.  
It uses Newton’s method to approximate the function and is therefore not dependent on the range [0,1)

---

<div class="post-metadata">

**Author:** ![DenisRed](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/denisred/32/303_2.png) [@DenisRed](https://openfhe.discourse.group/u/DenisRed)\
**Post date:** [January 3, 2025, 12:07pm UTC](https://openfhe.discourse.group/t/approximation-of-square-root-without-chebyshev-interpolation/1813/4 "2025-01-03T12:07:41Z")

</div>

Thanks for the recommendation, it’s very interesting! But I try to keep the multiplicative depth as low as possible. As your recommendation also says, the algorithm described above is the one with the lowest multiplicative depth.

Another question: Do you perhaps have a recommendation for comparing two vectors in CKKS (without changing the scheme)?

Thank you and Happy New Year!