1

我正在尝试在 C 中实现一个简单、中等效率的 bignum 库。我想使用它编译的系统的完整寄存器大小(大概是 32 位或 64 位整数)来存储数字。我的理解是,我可以使用 intptr_t 完成此操作。这个对吗?是否有更适合语义的类型,例如 intword_t?

我还知道,使用 GCC,我可以通过将两个参数向上转换为 64 位整数来轻松地在 32 位机器上进行溢出检测,这将占用两个寄存器并利用 IA31 ADC 之类的指令(带进位相加)。我可以在 64 位机器上做类似的事情吗?有没有我可以向上转换的 128 位类型,如果它们可用,它们将编译以使用这些指令?更好的是,是否有代表两倍寄存器大小的标准类型(如 intdoubleptr_t),因此可以以独立于机器的方式完成?

谢谢!

4

2 回答 2

1

有什么理由不使用 size_t?size_t 在 32 位系统上是 4 个字节,在 64 位系统上是 8 个字节,并且可能比使用 WORD_SIZE 更便携(我认为 WORD_SIZE 是 gcc 特定的,不是吗?)

我不知道 64 位系统上的任何 128 位值,这里可能是错误的,但在内核或常规用户应用程序中没有遇到这种类型。

于 2010-01-10T06:42:57.707 回答
1

我强烈建议使用 C99<stdint.h>标头。它声明了int32_t, int64_t,uint32_tuint64_t, 看起来像你真正想要使用的。

编辑:正如 Alok 指出的那样,int_fast32_t,int_fast64_t等可能是您想要使用的。您指定的位数应该是数学工作所需的最小值,即计算不会“翻转”。

优化来自这样一个事实,即 CPU 不必浪费周期重新对齐数据、在读取时填充前导位以及在写入时执行读取-修改-写入。事实是,许多处理器(例如最近的 x86s)在 CPU 中都有硬件可以很好地优化这些访问(至少是填充和读取-修改-写入部分),因为它们非常常见并且通常只涉及之间的传输处理器和缓存。

因此,您唯一要做的就是确保访问对齐:获取sizeof(int_fast32_t)或使用它来确保您的缓冲区指针与之对齐。

事实是,这可能不会带来太大的改进(由于硬件在运行时优化传输),所以编写一些东西并计时它可能是唯一可以确定的方法。此外,如果您真的对性能非常着迷,您可能需要查看 SSE 或 AltiVec 或您的处理器拥有的任何矢量化技术,因为在进行矢量数学时,它们的性能将优于您可以编写的任何可移植的东西。

于 2010-01-10T05:21:42.520 回答