使用 32 位块的 1024 位 2 的补码乘法
Signed Multiplication of 1024-bit 2's complement numbers using 32-bit chunks
所以我的 1024 位数字有以下结构定义（我想在这里使用 2 的补码表示，我在 32 位系统上）：
typedef struct int1024
{
int32_t num[32]; //should I use uint32_t?
} int1024;
基本上是一个包含数字段的数组。
对于add since，有符号加法和无符号加法是一样的。我可以简单地使用指令 add 和 adc 来为我的更大的数组执行扩展操作。
现在进行乘法运算。我能够使用经典的 O(n^2) 乘法算法结合使用 imul（使用上限和下限结果）和 adc 来进行无符号乘法运算。但是我的结果需要带符号的乘法。我知道人们说只使用带符号的震级版本。即在负数时取 2 的补码，并在需要时最后应用 2 的补码。但是所有额外的注意和加 1 都会非常昂贵，因为我需要做很多乘法。有没有一种技术可以像这样对数字表示进行大符号乘法。 （我真的不想在这里进行任何分支或递归调用）。我想我的主要问题之一是如何处理进位和负数乘法的高位部分。 （只是一个想法，也许我可以结合使用有符号和无符号乘法，但我不知道从哪里开始）。如果你没有时间看 1024 位，一个 128 位的答案就足够了（我只是概括一下）。
请注意，在 1024 位整数中 只有 最高位，即第 1023 位，是符号位，位值为 -(2**1023)。所有其他位都有其正常的 +(2**pos) 位值。即，当您对它们进行扩大乘法运算时，较低的“肢体”都需要被视为无符号。
你有一个符号位和 1023 个低位。每个肢体没有一个符号位。
此外，有符号乘法和无符号乘法之间的区别仅在于扩大乘法的高半部分（N x N => 2N 位）。这就是为什么 x86 有单独的指令 imul r/m64 和 mul r/m64 来对 RDX:RAX (https://www.felixcloutier.com/x86/imul vs. https://www.felixcloutier.com/x86/mul) 进行全乘。但是对于非扩展，只有 imul r, r/m 和 imul r, r/m, imm 编译器用于无符号和有符号（人类也应该如此）。
因为你想要一个 1024x1024 => 1024 位的产品，它会丢弃高 1024 位，你可以而且应该让你的整个东西都无符号。
当你用 asm 编写时，你可以使用任何你可以使用的块大小，例如64 位模式下的 64 位，不限制自己的 C 块大小。
查看 https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf for how to use BMI2 mulx (leaves FLAGS untouched so doesn't disturb adc chains, and only has RDX as an implicit input, with other source and both outputs being explicit, saving on MOV instructions). And optionally also Broadwell ADOX / ADCX 到 运行 两个并行的 dep 链以获得更多 ILP 用于中等大小的 BigInteger 东西，如 512x512 位或 512x64 位（他们用作示例）。
所以我的 1024 位数字有以下结构定义（我想在这里使用 2 的补码表示，我在 32 位系统上）：
typedef struct int1024
{
int32_t num[32]; //should I use uint32_t?
} int1024;
基本上是一个包含数字段的数组。
对于add since，有符号加法和无符号加法是一样的。我可以简单地使用指令 add 和 adc 来为我的更大的数组执行扩展操作。
现在进行乘法运算。我能够使用经典的 O(n^2) 乘法算法结合使用 imul（使用上限和下限结果）和 adc 来进行无符号乘法运算。但是我的结果需要带符号的乘法。我知道人们说只使用带符号的震级版本。即在负数时取 2 的补码，并在需要时最后应用 2 的补码。但是所有额外的注意和加 1 都会非常昂贵，因为我需要做很多乘法。有没有一种技术可以像这样对数字表示进行大符号乘法。 （我真的不想在这里进行任何分支或递归调用）。我想我的主要问题之一是如何处理进位和负数乘法的高位部分。 （只是一个想法，也许我可以结合使用有符号和无符号乘法，但我不知道从哪里开始）。如果你没有时间看 1024 位，一个 128 位的答案就足够了（我只是概括一下）。
请注意，在 1024 位整数中 只有 最高位，即第 1023 位，是符号位，位值为 -(2**1023)。所有其他位都有其正常的 +(2**pos) 位值。即，当您对它们进行扩大乘法运算时，较低的“肢体”都需要被视为无符号。
你有一个符号位和 1023 个低位。每个肢体没有一个符号位。
此外，有符号乘法和无符号乘法之间的区别仅在于扩大乘法的高半部分（N x N => 2N 位）。这就是为什么 x86 有单独的指令 imul r/m64 和 mul r/m64 来对 RDX:RAX (https://www.felixcloutier.com/x86/imul vs. https://www.felixcloutier.com/x86/mul) 进行全乘。但是对于非扩展，只有 imul r, r/m 和 imul r, r/m, imm 编译器用于无符号和有符号（人类也应该如此）。
因为你想要一个 1024x1024 => 1024 位的产品，它会丢弃高 1024 位，你可以而且应该让你的整个东西都无符号。
当你用 asm 编写时，你可以使用任何你可以使用的块大小，例如64 位模式下的 64 位，不限制自己的 C 块大小。
查看 https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf for how to use BMI2 mulx (leaves FLAGS untouched so doesn't disturb adc chains, and only has RDX as an implicit input, with other source and both outputs being explicit, saving on MOV instructions). And optionally also Broadwell ADOX / ADCX 到 运行 两个并行的 dep 链以获得更多 ILP 用于中等大小的 BigInteger 东西，如 512x512 位或 512x64 位（他们用作示例）。