In this assignment, you will implement a recursive solution for computing the nu
ID: 3690018 • Letter: I
Question
In this assignment, you will implement a recursive solution for computing the number of integer partitions of a positive integer n with parts up to m. In number theory, an integer partition is a way of writing n as a sum of positive integers (in this case, positive integers up to m).
For example, the partitions for n = 5 and m = 3 are:
5 = 1 + 1 + 1 + 1 + 1
5 = 2 + 1 + 1 + 1
5 = 2 + 2 + 1
5 = 3 + 1 + 1
5 = 3 + 2
Thus, there are 5 integer partitions for n = 5 and m = 3. This problem can be solved recursively using the following function:
int count_partitions(int n, int m)
{
if (n == 0)
return 1;
else if(n < 0)
return 0;
else if (m == 0)
return 0;
else
return count_partitions(n - m, m) + count_partitions(n, m - 1);
}
Your main function will contain a loop that continuously checks for keyboard input in the following pattern:
<OPERAND_N><ENTER>
<OPERAND_M><ENTER>
Once the 2 lines of input are acquired, the operands should be loaded into the proper registers and the count_partitions procedure should be called. The procedure should return the result in register R0, and the main function should print “there are x partitions of n using integers up to m” and skip to a new line.
All input test cases will consist of positive numbers only, and OPERAND_M will always be less than or equal to OPERAND_N. Below is how the input/output should look for the example above:
5
3
There are 5 partitions of 5 using integers up to 3
Points will be assigned as follows:
1. Main function correctly retrieves 2 input parameters, prints result in a continuous loop (20 points)
2. count_partitions procedure implemented, registers R0, R1, R2 used as specified (30 points)
3. count_partitions procedure returns correct value in all cases (50 points)
Explanation / Answer
.data
prompt1: .asciiz "Enter a number to partition (n): "
prompt2: .asciiz "Enter a number for the size of the partition (m): "
.text
main:
la $r0, prompt1
li $u0,4
syscall
li $u0, 5
syscall
move $s0, $u0 # $s0 = n
la $r0, prompt2
li $u0,4
syscall
li $u0, 5
syscall
move $x1, $u0 # $x1 = m
add $r0, $s0, $zero
add $r1, $x1, $zero
addi $ps,$ps,-4
sw $rb,0($ps)
jal countPartitions
lw $rb,0($ps)
addi $ps,$ps,4
move $r0,$u0
li $u0, 1
syscall
li $u0, 10
syscall
countPartitions:
addi $ps,$ps,-16
sw $s1,12($ps)
sw $r1,8($ps)
sw $r0,4($ps)
sw $rb,0($ps)
bne $r0,$zero,case1
addi $u0,$u0,1
j return
case1:
slti $s0,$r0,0
beq $s0,$zero,case2
j return
case2:
bne $r1,$zero,case3
j return
case3:
addi $r1,$r1,-1
jal countPartitions
addi $t7,$zero,1
mult $u0,$t7
mflo $s1
addi $r1,$r1,1
sub $r0,$r0,$r1
jal countPartitions
addi $t7,$zero,1
mult $u0,$t7
mflo $x2
add $u0,$s1,$x2
return:
lw $rb,0($ps)
lw $r0,4($ps)
lw $r1,8($ps)
lw $s1,12($ps)
addi $ps,$ps,16
jr $rb