MIPS 上的多精度算法

发布于 2024-08-29 16:22:11 字数 617 浏览 8 评论 0原文

我只是想在本机 MIPS 上实现多精度算术。假设一个 64 位整数位于寄存器 $12 和 $13 中，另一个 64 位整数位于寄存器 $14 和 $15 中。总和将被放置在寄存器 $10 和 $11 中。 64 位整数的最高有效字位于偶数寄存器中，最低有效字位于奇数寄存器中。它在互联网上说，这是最短的实现方式。

addu  $11, $13, $15    # add least significant word
sltu  $10, $11, $15    # set carry-in bit 
addu  $10, $10, $12    # add in first most significant word
addu  $10, $10, $14    # add in second most significant word

我只是想仔细检查我的理解是否正确。 sltu 检查是否两个最低有效字的总和小于或等于以下之一操作数。如果是这种情况，那么就发生了进位，对吗？

检查最高位两位相加时是否发生进位单词并将结果存储在 9 美元中我必须做：

sltu  $9, $10, $12    # set carry-in bit

这有意义吗？

原文

I am just trying to implement multi-precision arithmetic on native MIPS. Assume that
one 64-bit integer is in register $12 and $13 and another is in registers $14 and $15.
The sum is to be placed in registers $10 and $11. The most significant word of the 64-bit integer is found in the even-numbered registers, and the least significant word is found in the odd-numbered registers. On the internet, it said, this is the shortest possible implementation.

addu  $11, $13, $15    # add least significant word
sltu  $10, $11, $15    # set carry-in bit 
addu  $10, $10, $12    # add in first most significant word
addu  $10, $10, $14    # add in second most significant word

I just wanna double check that I understand correctly. The sltu checks if
the sum of the two least significant words is smaller or equal than one of
the operands. If this is the case, than did a carry occur, is this right?

To check if there occured a carry when adding the two most significant
words and store the result in $9 I have to do:

sltu  $9, $10, $12    # set carry-in bit

Does this make any sense?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

北座城市 2024-09-05 16:22:11

sltu 检查两个最低有效字的总和是否小于或等于操作数之一。

不完全是：如果两个最低有效字的总和严格小于操作数之一（被视为 32 位无符号值），则将 $10 设置为 1；如果总和等于或大于该操作数，则为 0。

如果是这种情况，那么就发生了进位，对吗？

是的。

考虑将 b 的各种可能值添加到某个特定值 a（其中所有内容都是无符号 32 位值）时会发生什么：

如果没有发生溢出，我们必须有 a <= sum <= 0xFFFFFFFF，因此 0 <= b <= (0xFFFFFFFF - a)。
b 的其余情况会导致溢出；这些情况下的实际总和必须为 0x100000000 <= sum <= a + 0xFFFFFFFF，当截断为 32 位时给出 0 <= sum <= a - 1.

检查两个最高有效字相加时是否发生进位，并将结果存储在$9中
我要做的是：
sltu $9, $10, $12 # 设置进位位

不完全是。

这里的问题是您要添加两个 32 位值和，可能是最低有效字之和的进位。例如，考虑存在进位且两个最高有效字均为 0xFFFFFFFF 的情况：总和将为 1+ 0xFFFFFFFF + 0xFFFFFFFF = 0xFFFFFFFF，因此进位不会被设置（但应该设置）。

处理此问题的一种方法是在将 $12 添加到 $10 后检查进位，并在将 $11 添加到该总和后再次检查。这些和中只有一个可以产生进位（$12 + $10 仅当 $12 为 0xFFFFFFFF 时才会溢出，因为 $10 要么是 0，要么是 1；并且在这种情况下，总和为 0，因此第二个总和也不会溢出）。

所以这可能（免责声明：已经晚了，而且未经测试）可以解决问题：

addu $11, $13, $15
sltu $10, $11, $15  # carry from low word
addu $10, $10, $12
sltu  $9, $10, $12  # possible carry from high word (1)
addu $10, $10, $14
sltu  $8, $10, $14  # possible carry from high word (2)
or    $9,  $8,  $9  # carry in result if either (1) or (2) were true (can't both be true at once)

The sltu checks if the sum of the two least significant words is smaller or equal than one of the operands.

Not quite: it sets $10 to 1 if the sum of the two least significant words is strictly less than one of the operands (considered as 32-bit unsigned values); and 0 if the sum is equal to, or greater than, that operand.

If this is the case, than did a carry occur, is this right?

Yes.

Consider what can happen when adding various possible values of b to some particular value a (where everything is an unsigned 32-bit value):

If overflow has not occurred, we must have a <= sum <= 0xFFFFFFFF, so 0 <= b <= (0xFFFFFFFF - a).
The remaining cases for b cause an overflow; the actual sum in these cases must be 0x100000000 <= sum <= a + 0xFFFFFFFF, which when truncated to 32 bits gives 0 <= sum <= a - 1.

To check if there occured a carry when adding the two most significant words and store the result in $9
I have to do:
sltu $9, $10, $12 # set carry-in bit

Not quite.

The problem here is that you're adding two 32-bit values and possibly a carry from the sum of the least significant words. For example, consider the case where there is a carry and both most significant words are 0xFFFFFFFF: the sum will be 1+ 0xFFFFFFFF + 0xFFFFFFFF = 0xFFFFFFFF, and so the carry will not be set (but it should be).

One way to deal with this would be to check for carry after adding $12 to $10, and check again after adding $11 to that sum. Only one of those sums can produce a carry ($12 + $10 only overflows when $12 is 0xFFFFFFFF, because $10 is either 0 or 1; and in that case the sum is 0, so the second sum can't overflow as well).

So this might (disclaimer: it's late, and this is untested) do the trick:

addu $11, $13, $15
sltu $10, $11, $15  # carry from low word
addu $10, $10, $12
sltu  $9, $10, $12  # possible carry from high word (1)
addu $10, $10, $14
sltu  $8, $10, $14  # possible carry from high word (2)
or    $9,  $8,  $9  # carry in result if either (1) or (2) were true (can't both be true at once)

回复收藏 0 原文

~没有更多了~