计算商而不跟踪余数的除法算法
Division algorithm for calculating quotient without keeping track of remainder
作为一个业余项目，我正在尝试使用独立的 C 实现一些密码算法 - 即没有标准库函数的 C 变体（标准库类型和常量仍然可用），以及没有诸如 VLA（可变长度数组）之类的可选功能。
我做过的其中一件事是为大整数（大小 > 128 位）实现了一些函数。但是，此设置中的整数除法函数需要跟踪其当前形式的余数，并且由于我使用的是独立环境，调用者必须为其提供 space。
是否可以实现计算商的除法算法而不依赖于跟踪余数，并且可能使用位分片技术？使用调用递归将变量保存在堆栈上是可以接受的。
我们假设大整数的类型是 bigint_t:
#define N 8
typedef uint32_t bigint_t[N]; // least-significant word first.
您可以使用二进制搜索。选择一个数字，将其乘以除数。如果结果太大，减少数量；如果结果太小，增加数量。控制 increment/decrement 使其呈指数趋于零。
我了解到您担心剩余部分需要的额外 space，因为您不能调用 malloc。
请注意，在正常的 long-division 样式实现期间，随着被除数缩小成为余数，商的长度会增加。在每个阶段，商和余数加起来至多需要比原始股息所需的 space 恒定的数量。
如果将 dividend-becoming-remainder 和增长的商保留在同一个数组中，则只需要几个变量来表示额外的数字。
作为一个业余项目，我正在尝试使用独立的 C 实现一些密码算法 - 即没有标准库函数的 C 变体（标准库类型和常量仍然可用），以及没有诸如 VLA（可变长度数组）之类的可选功能。
我做过的其中一件事是为大整数（大小 > 128 位）实现了一些函数。但是，此设置中的整数除法函数需要跟踪其当前形式的余数，并且由于我使用的是独立环境，调用者必须为其提供 space。
是否可以实现计算商的除法算法而不依赖于跟踪余数，并且可能使用位分片技术？使用调用递归将变量保存在堆栈上是可以接受的。
我们假设大整数的类型是 bigint_t:
#define N 8
typedef uint32_t bigint_t[N]; // least-significant word first.
您可以使用二进制搜索。选择一个数字，将其乘以除数。如果结果太大，减少数量；如果结果太小，增加数量。控制 increment/decrement 使其呈指数趋于零。
我了解到您担心剩余部分需要的额外 space，因为您不能调用 malloc。
请注意，在正常的 long-division 样式实现期间，随着被除数缩小成为余数，商的长度会增加。在每个阶段，商和余数加起来至多需要比原始股息所需的 space 恒定的数量。
如果将 dividend-becoming-remainder 和增长的商保留在同一个数组中，则只需要几个变量来表示额外的数字。