使用 CKKS 进行 Goldschmidt 除法初始化

Question

我最近发现我不太明白如何对以下文章中提到的 Goldschmidt 部门进行初始化：Samanvaya Pandah：使用 CKKS 进行主要组件分析 同态方案
它并没有真正解释如何找到初始值，只是指出我们希望维持以下关系：

我有以下Python代码：

def gold_div(a,b):
    r = 1/b     
    for i in range(0,10):
        a = r*a
        b = r*b
        r = 2 + -1*b
    return a

它可以工作，但是除以一个应该是除法算法的函数没有多大意义。
我正在考虑使用他引用的来源：Markstein, P.：使用 Goldschmidt 算法的软件部门和平方根，但我对他们在做什么感到困惑。

下图说明了他们在做什么：

我知道 sgn() 是一个函数，它基本上只是找出 b₀ 是负还是正，但我真的不知道如何使用它们的 Y₀，因为它似乎替代了未知的 Y ₀ 与未知数 n （因此我们有 2 个未知数）。他们似乎也很快跳过它，因为我们通常只使用一个查找表，我再次不相信我们可以使用它，因为我们使用的是 CKKS。

我能看到的唯一可行的办法是利用这样一个事实：既然我们正在进行除法，那么我们可以假设 b 不为 0，从而我们可以将 Y₀ 的初始表达式重写为 3/4 *b₀<=Y₀<3/2*b₀.

Answer 1

我找到了一个答案，我可以通过以下方式使用 Newton-rahpson 解决问题：

import numpy as np
def newton_method(a, number_iters = 70):
number = np.finfo(float).eps # number to get inverse of
for i in range(number_iters): # iteration number
    number = number*(2-a*number) # update
return number

它使用 epsilon，因为它有助于使用非常小的数字，因此它不会趋向无穷大。