超过 32 位的 MIPS 乘法

Question

对于一个作业，我需要开发一个递归算法，给定一个输入字符串，我打印出对应于 base-30 的无符号十进制整数由字符串表示的数字。 (a-10;b-11;...) 例如：

给定输入：

"AAAAAAAAAAaaaaaaaaaa"

预期输出：

120233944862068965517241379310

附加说明：最多允许输入 20 个字符。输入字符串的内存地址通过寄存器传递给子程序，十进制整数通过堆栈返回（因为寄存器可能不足以保存结果）。

我了解 MIPS 的递归部分，但寄存器只能容纳 32 位。所以我们根本无法将结果存储在寄存器中，因为它更大。什么是分解问题的有效方法，我可以通过乘法进行计算？

例如。 'A'(10)*30^19 + 'A'(10)*30^18 + ... + 'a'(10)*30^0

不只是给我代码，因为这是一项作业，但如果有人能指出正确的方向，那就太好了！

Answer 1

您可以拥有与寄存器或内存一样大的数字，想一想小学乘法，并想一想以二为底数如何简化它。

     abcdef
*    111101
============
     abcdef
    000000
   abcdef
  abcdef
 abcdef
abcdef

但是如果我只有 2 位寄存器怎么办？

你会做这种事：

        ab cd ef
      0 00 00 0
     ab cd ef
   a bc de f
  ab cd ef
a bc de f
===============

你可以一次取两行。

另一种从小学十六进制数来思考它的方法我想说乘以 16 位数字，但我只有一个 8 位 * 8 位 = 16 位乘法指令：

abcd * 1234 =
((ab*(2^8))+(cd*(2^0))) * ((12*(2^8))+(34*(2^0)) = 
((ab*x)+(cd*y)) * ((12*x)+(34*y) = 
ab*12*x*x + ab*34*x*y + cd*12*x*y + cd*34*y*y =

x 和 y 只是 2 的幂，但不仅如此，它们将结果放在 8 位边界的 8 次或 16 次或更多次幂上。这些数字现在可以用 8 位 * 8 位 = 16 位乘法或 16 位 * 16 位 = 16 位乘法来完成，并填充高位。然后你跟踪谁降落在哪里，有一些添加和一些添加到下一组的进位。

这就是您如何使用从学校学到的知识，将这些东西与您拥有的 registers/instructions 相结合。

所以你可以构建一个大的乘法器，我假设你知道如何级联加法或者可以用类似的方式计算出来，然后“只是”使用它。

但是你的问题和你说的一样。 (10)*30^19 + (10)*30^18 等等。

#include <stdio.h>
int main ( void )
{
    unsigned int ra;
    unsigned int rb;
    unsigned int rc;

    for(ra=1;ra<6;ra++)
    {
        rc=1;
        for(rb=0;rb<ra;rb++)
        {
            rc*=30;
        }
        printf("%2u 0x%08X %u\n",ra,rc,rc);
    }
    return(0);
}

 1 0x0000001E 30
 2 0x00000384 900
 3 0x00006978 27000
 4 0x000C5C10 810000
 5 0x0172C9E0 24300000

30 是 352。它在二进制中看起来一点也不漂亮，在十进制中看起来也不错。也许那里有技巧。

abc = 10*30*30 + 11*30 + 12*0
9000 + 330 + 12
9312

我还没有看到。

但如果你考虑一下 3,5,2

二进制 x3 是 (x<<1)+x; x5 是 (x<<2)+x 并且 x*2 = x<<1;

如果十进制（以 10 为底）1234

x = 1;
for each digit that remains in the string
x = x * 10; //shift left one number place
x = x + 2; //next digit
...

将基数 10 转换为二进制

x = 1;
x = (x<<3)+(x<<1); //x = x * 10;
x = x + 2;
x = (x<<3)+(x<<1);
x = x + 3;
x = (x<<3)+(x<<1);
x = x + 4;

或

x = 0;
x = (x<<3)+(x<<1);
x = 1;
x = (x<<3)+(x<<1);
x = x + 2;
x = (x<<3)+(x<<1);
x = x + 3;
x = (x<<3)+(x<<1);
x = x + 4;

或

x = 0;
y = x<<3;
x = y + x<<1;
x = x + 1;
y = x<<3;
x = y + x<<1;
x = x + 2;
y = x<<3;
x = y + x<<1;
x = x + 3;
y = x<<3;
x = y + x<<1;
x = x + 4;

如图所示，从 30 进制到二进制而不是 10 进制到二进制很容易形成循环。移动小数字很容易在您有空间的情况下级联尽可能多的寄存器或内存位置。加法步骤只能执行一位，因此很容易级联到 registers/memory 个位置。因此，以 10 为基数到以 2 为基数的长于寄存器中的位数并不困难。现在把那个很长的二进制数转换成10进制打印出来，是的，这是一个新问题。

也许这里的技巧是一种伪 bcd 类型的方法，每个十进制数字一个半字节，而您正在做这种事情：

 1 0x0000001E 30
 2 0x00000384 900
 3 0x00006978 27000
 4 0x000C5C10 810000
 5 0x0172C9E0 24300000

"abc" 10, 11, 12

x = 0x0
x = x * 0x30 = (x<<5) + (x << 4); //hmmm is that right?
x = x + 0x10;
...

但是对于所有这些加法，您必须从右到左遍历并覆盖 bcd 溢出，因此 0x1A 变为 0x20，因为 0xA 比 9 大一个，所以这是一个进入下一个半字节的进位。这变得很难看，但是如果每个 BCD 数字都是 8 位呢？

这就是我的想法，如果您要自己构建一个多寄存器大型乘法器，需要多少 registers/memory 个位置来处理 30^19 次方？那就是它必须有多大，但是如果您构建了它，那么它就很容易使用。把它变成二进制。现在你要构建一个大的除法器来将它从二进制转换为 10 进制？

这是可行的，你做长除法 10 是 0b1010 你实际上是在位下走 101 对于每一位你得到 0 或 1 它的长除法你可以在循环中编程拉出一个从 msbit 开始一次从分子中取出一个位，并将该位累加与 0b101 或 0b1010 进行比较，它将小于 10 的 2 倍，因此结果是累加 1 或 0，就像长除法一样，你减去 0 乘以 10 或1 次 10 次。

0x1D / 10

11101

如果你愿意的话，我们一次拉下一个分子位，就像累加器中的长除法一样，并将其与分母进行比较

1与1010相比是0余1 下一位 11 与 1010 相比是 0 余数 11 111 与 1010 相比是 0 余数 111 1110 与 1010 相比是 1 余数 100 1001 与 1010 相比是 0 余数 1001

结果为00010或2, 0x1D / 10 = 29 / 10 = 2 很容易制作一个累加器只需要 4 位很容易在无限数量的 32 位寄存器或内存位置一次遍历一位。但你必须这样做无数次

1234 十进制 = 0x4D2

0x4D2 / 10 = 0x7B remainder 4
0x7B / 10 = 0xC remainder 3
0xC / 10 = 0x1 remainder 2
0x1 / 10 = 0 remainder 1

所以我们完成了，结果 1234 十进制。

您从 0x4D2 开始并从中得到 0x7B 和 4，但不是少量的位，而是 dozens/hundreds 位。

蛮力如果你可以在二进制级联中为你需要的 32 位字的数量制作乘法器而没有错误，那么除法就不难编码了。你可以用乘法来完成这项工作。

30^20 = 3.4..*10^29

我的大脑不太清楚你需要存储这个数字的 bits/words 个数字。

无论如何，是的，你可以级联一个 32 位 * 32 位 = 32 位（一次 16 位）或 32 位 * 32 位 = 64 位（一次 32 位）乘法器，只要你有内存for（从寄存器中转到运行快速使用寄存器进行乘法和加法以及带进位的加法，使用内存来保存实际数字）。以基数 2 结果结束。然后你可以做一个长除法算法并通过它搅动直到分子为 0。分配需要乘法吗？

超过 32 位的 MIPS 乘法

MIPS Multiplication of More Than 32 Bits

assembly

mips

bigint

qtspim