Рекурсия в Mips

Question

Я в настоящее время пытаются выяснить, как код функции нахождения наименьшего целого в 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 []
• $ a1 = INT низкий // индекс
• $ a2 = INT высокий индекс //

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

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». Я просматривал свой код и заметки, и у меня все еще нет подсказки.

Answer 1

При использовании команды 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, но у вас может быть другим стиль для загрузки немедленных значений в регистр.

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

Answer 2

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