32位以上的MIPS乘法

Question

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

所提供的投入：

"AAAAAAAAAAaaaaaaaaaa“

预期产出：

120233944862068965517241379310

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

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

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

不只是给我的代码，因为这是一个任务，但如果有人可以指出我在正确的方向，那将是伟大的！

Answer 1

你可以有像你有寄存器或内存那么大的数字，想想小学乘法，想想基2是如何简化它的。

     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或16或更多8位边界的幂上有更多的结果。这些数字现在可以用8位*8位= 16位乘或16位* 16位= 16位乘与上面的比特相乘来完成。然后你跟踪谁降落在哪里，有一些附加与一些携带添加到下一组。

这就是你如何利用你从学校学到的东西，把这些东西和你所拥有的寄存器/指令连在一起。

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

但正如你所说的，你的问题是。(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是3_5_2，用二进制数看上去一点也不好看，小数点看上去也不错。也许有个诡计。

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

我还没看到呢。

但如果你想想那个3,5,2

二元x_3是(x<<1)+x，x_5 is (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到二进制，如图所示。移动较小的数字很容易串在尽可能多的寄存器或内存位置，因为你有足够的空间。加法步骤只能执行一位，因此很容易在许多寄存器/内存位置之间级联。因此，一个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位呢？

这就是我想的路径，如果你要建立一个多寄存器的大乘法器，需要多少寄存器/内存位置来处理30^19的能量？这是它必须有多大，但如果你建造它，那么它将是容易使用。把它变成二进制。现在你要建立一个大的除法器，使它从二进制到基数10？

这是可行的，长除法10是0b1010，你实际上是在位下走101，每一个位得到0或1它的长除法，你可以在一个循环中编程，一次从分子中抽取一个位，从msbit开始，比较位与0b101或0b1010的累积，结果是累积1s或0s，就像长除法一样，当你走的时候，你会减去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开始，但是不是少量的比特，而是几十/数百位。

蛮力，如果你可以使乘法器在二进制级联为32位字的数目，你需要没有错误，然后除法没有那么难编码。你可以用乘法来完成这个任务。

30^20 =3.4*10^29

我的大脑并没有完全计算出你储存这个数字所需的位/字数。

无论如何，您可以级联32位* 32位= 32位(一次16位)或32位* 32位= 64位(一次32位)乘法器的宽度，就像您有内存一样(要用寄存器来快速使用寄存器来进行乘法和加法，然后用carrys添加，使用内存来保存实际的数字)。最后得到一个基数2的结果。然后你可以做一个长除法，然后翻滚，直到分子是0。作业是否需要乘乘？