Рекурсия в Мипс - PullRequest
Новая
       16

Рекурсия в Мипс

0 голосов
/ 05 декабря 2010

В настоящее время я пытаюсь выяснить, как закодировать функцию нахождения наименьшего целого числа в MIPS, следуя этому алгоритму ... 

int Min( int[] A, int low, int high)
{   if (low== high) return A[low];
     int mid = (low+high)/2;
     int  min1 = Min( int[] A, low, mid);
     int   min2 =Min( int[] A, mid +1, high);
     if(min1>min2) return min2;
     return min1;
}

Я получаю проблемы при попытке закодировать это вMIPS.Вот мой текущий код MIPS.Пользователь вводит до 6 целых чисел, которые хранятся в массиве.Регистры $ a0, $ a1 и $ a2 используются в качестве аргументов для функции.

  • $ a0 = int [] A
  • $ a1 = int low // index
  • $ a2 = int high // index

Вот функция рекурсии ... 

min:
bne $a1, $a2, recur
mul $t4, $a1, 4
add $a0, $a0, $t4
lw $v1, 0($a0) 
jr $ra
# recursion start
recur:
addiu $sp, $sp, -12 #reserve 12 bytes on stack
sw $ra, 0($sp) #push return address
# mid = (low+high)/2 t0 = mid t1= min1 t2=min2 t3 = mid+1
add $t0, $a1, $a2 # t0 = low + high
div $t0, $t0, 2 # t0 = (low+high)/2


# mid1 = min(int[]A,low,mid)
min1:
sw $a2, 4($sp) #push high
addi $t3, $t0, 1 # mid+1
sw $t3, 8($sp) #store mid+1
move $a2, $t0 #change high to mid
jal min #compute
# check
move $t1, $v1 #set up the min1 = return value

# mid2 = min(int[]A,mid+1,high)
min2:
lw $a2, 4($sp) #reload high prior call
lw $a1, 8($sp) #change low to mid+1
jal min #compute
move $t2, $v1 #set as the min2 = return value

confirm:
# return mid2 if mid1 > mid2
bgt $t1, $t2, returnMid2
# else return mid1
move $v1, $t1
j minFinal
returnMid2:
move $v1, $t2
minFinal:
lw $ra, 0($sp)
addiu $sp, $sp, 12 #release stack
jr $ra

Проблема в том, какую комбинацию целых чисел я введу во времяПрограмма, я никогда не получаю минимальное значение, а число «543976553».Я просматривал свой код и заметки и до сих пор не понимаю.

Ответы [ 2 ]

1 голос
/ 08 июня 2011

Для mid1 попробуйте положить возвращаемое значение в стек, а затем переместить его в $ t1 ПОСЛЕ того, как вызывается mid2. Затем сравните $ v0 с $ t1 вместо сравнения $ t1 с $ t2

0 голосов
/ 24 декабря 2010

При использовании команды div в MIPS не нужно ли получать частное от $ LO?

Таким образом, ваша логика для (high + low) / 2 может выглядеть примерно так: 

add $t0, $a1, $a2 # t0 = low + high
addi $t5, $zero, 2 # t5=2
div $t0, $t5 # LO = t0/t5, HI = t0%t5
addi $t0, $LO, 0 # t0 = LO (t0/t5)

некоторые из этих строк написаны так, как я научился делать MIPS, но у вас может быть другой стиль для загрузки непосредственных значений в регистр.

Я также не могу обещать, что это все исправит, но на первый взгляд, это то, что я заметил.

...