作为一个业余项目,我试图使用独立的C来实现一些密码算法——也就是说,C的变体没有标准库函数(标准库类型和常量仍然可用),也没有可选的特性,比如VLA(可变长度数组)。
我做的一件事是为大整数(大小>128位)实现一些函数。但是,此设置中用于整数除法的函数需要跟踪其当前形式的余数,而且由于我使用的是独立环境,调用者必须为其提供空间。
有没有可能实现除法算法来计算商而不依赖于跟踪余数,并可能使用位切片技术使用调用递归将变量保留在堆栈上是可以接受的。
我们假设大整数的类型是bigint:

#define N 8
typedef uint32_t bigint_t[N]; // least-significant word first.

最佳答案

我认为您关心的是剩余部分需要的额外空间,因为您不能调用malloc。
注意,在正常的长除法风格的实现过程中,商的长度随着股息收缩而变为余数而增长。在每个阶段,商和余数加在一起最多需要比原始股息所需的空间恒定的量。
如果将股息保持为余数,并将增长商保持在同一数组中,则只需要为额外的数字使用两个变量。

关于c - 计算商而不跟踪余数的除法算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/56422858/

10-11 18:57