MIPS编程指令计数问题

我写了这个mips代码来找到gcf，但我很困惑得到这个代码执行的指令数。我需要找到一个线性函数，作为在答案之前必须计算余数的次数的函数。我试着用Qtspim单步执行这段代码，但不知道如何继续。MIPS编程指令计数问题

gcf: 
    addiu $sp,$sp,-4    # adjust the stack for an item 
    sw  $ra,0($sp)    # save return address 

    rem  $t4,$a0,$a1    # r = a % b 
    beq  $t4,$zero,L1   # if(r==0) go to L1 
    add  $a0,$zero,$a1   # a = b 
    add  $a1,$zero,$t4   # b = r 
    jr  gcf 

L1: 
    add  $v0,$zero,$a1   # return b 
    addiu $sp,$sp,4    # pop 2 items 
    jr  $ra      # return to caller

来源

2016-09-26 Aaks

第一个问题是实际编写此代码。我编写了这个代码来找到gcf，它可以工作，但是不能弄清楚他们希望我怎么做才能找到说明。我试着一步一步地运行这个代码，但我不知道如何获得线性函数。有没有公式或方法来解决它？ – Aaks

完成。现在有意义吗？我只是想知道这样做的一种方法。 – Aaks

看起来好多了。 – paisanco

绝对没有新显示在这里，你刚才实现的算法是欧几里得算法，它是在文献众所周知的。

我会在这里写一个非正式的分析作为链接只有问题是邪恶的。

首先让重写代码以高水平制剂：

unsigned int gcd(unsigned int a, unsigned int b) 
{ 
    if (a % b == 0) 
     return b; 

    return gcd(b, a % b); 
}

^{_{的unsigned int VS int的选择是由MIPS ISA，使rem未定义负操作数dicated。}}

缺货目标是找到一个函数T（A，B）给出步骤的数量的算法需要计算的一个和b的GDC。

由于直接方法无效，我们尝试颠倒该问题。
什么对（A，B）使得T（A，B）= 1，换句话说什么对使GCD（A，B）终止在一个步骤中？
我们显然必须具有A％B = 0，这意味着一个必须是b的倍数。
实际上有对的（可数）无穷数，我们可以限制我们自己来对具有最小，一个和b 。

总括来说，有T（A，B）= 1我们需要一个= NB，我们挑选对（A，B）=（1，1）。

现在，给定的一对（C，d）需要Ñ步骤，我们如何发现一个新的对（A，B）使得T（A，B）= T（C ，d）+ 1？

由于GCD（A，B）必须采取一步然后GCD（C，d）和由于从GCD开始（A，B）下一步是GCD（B，A％ b）我们必须有：

c = b  => b = c 
d = a % b => d = a % c => a = c + d

步骤d = a % c => a = c + d来源于一个的极小，我们所需要的最小一个当被ç分由于（c + d）％c = c％c d％c = 0 + d = d。

对于d％C = d是真实的，我们需要的是d <Ç。
我们的碱基对是（1,1）不满足这一假设，幸运的是，我们可以采取（2，1）作为碱基对（说服你的自我该T（2，1）= 1）。

然后我们有：

gcd(3, 2) = gcd(2, 1) = 1 T(3, 2) = 1 + T(2, 1) = 1 + 1 = 2 gcd(5, 3) = gcd(3, 2) = 1 T(5, 3) = 1 + T(3, 2) = 1 + 2 = 3 gcd(8, 5) = gcd(5, 3) = 1 T(8, 5) = 1 + T(5, 3) = 1 + 3 = 4 ...

如果我们看一下在一对（2，1），（3，2），（5,3），（8,5 ），...我们看到第n对（从1开始）由编号（F _{n + 1}，F _n）制成。
其中F _n是第n个斐波纳契数。

我们比有：

Ť（F _{N + 1}，F _Ñ） = N

关于斐波那契数我们知道˚F_Ñαφ^Ñ。

我们现在要使用渐近分析所有的诡计，尤其是在大O符号考虑φ^ñ或φ^{N + 1}相同的限制。
此外，我们不会明确使用big-O符号，而是假定每个等式在极限中都是真实的。这是一种滥用，但会使分析更加紧凑。

我们可以不失一般性地假设Ñ是一个上限在对中的两个数，并且它正比于^φÑ。
我们有Nαφ^Ñ给出日志_φ N = N，此CA被重写为日志（N）/日志（φ）= N（其中日志是在底座10和log（φ）可以取1/5）。
因此，我们终于有5logN =正或写入以相反的顺序

N = 5 logN个

凡Ñ是采取GCD（A，B）其中步骤的数目 b < a < N。

我们可以进一步表明，如果一个=纳克和B =毫克与Ñ，米 coprimes，比T（A，B）= T（N，M）因此取最小双对的限制不是限制。

在你重新发现了这样的算法，我反对用读这个答案继续强烈建议不测。你肯定会有一个敏锐的头脑，从挑战中获益最大，而不是回答。
我们稍后会看到这不会导致一般性的丧失。

来源

2016-09-26 09:23:39

MIPS编程指令计数问题

回答

相关问题