Operations on fields

[Herakles]

Hi,

we have to do the following new task:

Below you are asked to implement some operations on one-dimensional (ordinary) fields:

a. Write a MIPS programme that counts the negative and positive elements of a field and prints out the result.

b. Write a MIPS programme that computes the minimum and maximum of a field.

Advice:
Assume the field has a constant length (at least 10 elements) and does already exist in the data segment of your programme.

I just wanted to ask you whether there is again a trick for this task, like the logic shift operator in the task last week?
Would it even make sense to use logic shift operators in the implementation of this task, too?

Thank you very much.

Regards,
Herakles

[donkey]

Please read rule #9

http://www.masm32.com/board/index.php?topic=31.0

[clive]

Well for a) you could certainly look at the high order sign bit to determine if the number was negative. You could count the negative numbers in the list.  If you know the size of the list you can compute the number of positive numbers by subtracting the negative count from the total count.

b) You will have to compare each number against a running pair of min/max values, replacing with a new value when appropriate. This would require a greater than, less than test rather than a bit field test.

[Herakles]

To donkey:
Of course I do respect the forum rules, but I don't see where the problem is, as I didn't say "Give me the solution!!!" or something like that. I just asked the forum members for a hot tip as they have much more experience than me. Nothing more. If I am really wrong, then I do apologise myself most sincerely.

To clive:
I am not sure if I understood the advice in the task, but does it mean that it is not necessary to implement a function like "read integer into $v0" and a defined field within the code like "-2, 8, 3, -10, 20, 6, 30, -50, -32, 70" would be okay?


EDIT:
I've finished subtask a., but I get an error message in line 49:

la      $a0, $t5         # number of negative elements

This is my code:

Code Select Expand


.data

str1: .ascii "The number of negative and positive elements \n"
.ascii "of the following field will be counted: \n"
.asciiz "-2, 8, 3, -10, 20, 6, 30, -50, -32, 70\n"

answstr1: .asciiz "The number of negative elements is: "

answstr2: .asciiz "\nThe number of positive elements is: "

crlf: .asciiz "\n\n"

field: .word -2, 8, 3, -10, 20, 6, 30, -50, -32, 70


.text

main: li $v0, 4 # Print String
la $a0, str1 # load adress str1
syscall

la $a0, field # load address of field

li $t0, 0 # counter1 for field position
li $t3, 0 # counter2 for number of positive elements

sign: lb $t1, field($t0) # current position of the field

srl $t2, $t1, 31 # $t2 := $t1 >> 31
beqz $t2, positive # jump to positive, if $t2 = 0
addiu $t0, $t0, 1 # counter1 + 1
bgtu $t0, 10, exit # jump to exit if counter1 > 9
b sign

positive: addiu $t3, $t3, 1 # counter2 + 1
addiu $t0, $t0, 1 # counter1 + 1
bgtu $t0, 10, exit # jump to exit if counter1 > 9
b sign # jump to sign


exit: li $v0, 4 # Print String
la $a0, answstr1 # Answer Message 1
syscall

li $t4, 10 # $t4 := 10
subu $t5, $t4, $t3 # number of negative elements = 10 - number of positive elements

li $v0, 1 # Print Int
la $a0, $t5 # number of negative elements
syscall

li $v0, 4 # Print String
la $a0, answstr1 # Answer Message 2
syscall

li $v0, 1 # Print Int
la $a0, $t3 # number of positive elements
syscall

la $a0, crlf # Carriage Return, Line Feed
syscall

li $v0, 10 # Exit
syscall



It would be very nice, if you could tell me, where my mistake is or even if my code makes sense.

Thanks.

[clive]

la      $a0, $t5         # number of negative elements

LA is load effective address (immediate load), the instruction you want is MOVE (register-to-register)

Edit: Ok, so fixing it up a bit, using MOVE, and correcting the >9 test.

Code Select Expand

        .data

str1:   .ascii "The number of negative and positive elements \n"
        .ascii "of the following field will be counted: \n"
        .asciiz "-2, 8, 3, -10, 20, 6, 30, -50, -32, 70\n"

answstr1: .asciiz "The number of negative elements is: "

answstr2: .asciiz "The number of positive elements is: "

crlf:   .byte   10, 13, 0

field:  .word   -2, 8, 3, -10, 20, 6, 30, -50, -32, 70

        .text

main:   li      $v0, 4          # Print String
        la      $a0, str1       # load adress str1
        syscall

        la      $a0, field      # load address of field

        li      $t0, 0          # counter1 for field position
        li      $t3, 0          # counter2 for number of positive elements

sign:   lb      $t1, field($t0) # current position of the field

        srl     $t2, $t1, 31    # $t2 := $t1 >> 31
        beqz    $t2, positive   # jump to positive, if $t2 = 0
        addiu   $t0, $t0, 1     # counter1 + 1
        bgtu    $t0, 9, exit   # jump to exit if counter1 > 9
        b       sign

positive: addiu $t3, $t3, 1     # counter2 + 1
        addiu   $t0, $t0, 1     # counter1 + 1
        bgtu    $t0, 9, exit    # jump to exit if counter1 > 9
        b       sign            # jump to sign


exit:   li      $v0, 4          # Print String
        la      $a0, answstr1   # Answer Message 1
        syscall

        li      $t4, 10         # $t4 := 10
        subu    $t5, $t4, $t3   # number of negative elements = 10 - number of positive elements

        li      $v0, 1          # Print Int
        move    $a0, $t5        # number of negative elements
        syscall

        li      $v0, 4          # Print String
        la      $a0, crlf       # Carriage Return, Line Feed
        syscall

        li      $v0, 4          # Print String
        la      $a0, answstr2   # Answer Message 2
        syscall

        li      $v0, 1          # Print Int
        move    $a0, $t3        # number of positive elements
        syscall

        li      $v0, 4          # Print String
        la      $a0, crlf       # Carriage Return, Line Feed
        syscall

        li      $v0, 10         # Exit
        syscall


Will add an optimized solution shortly.

[Herakles]

Here is the beginning of my code to subtask b.:

Code Select Expand


.data

str1: .ascii "The number of negative and positive elements \n"
.ascii "of the following field will be counted: \n"
.asciiz "-2, 8, 3, -10, 20, 6, 30, -50, -32, 70\n"

answstr1: .asciiz "The number of negative elements is: "

answstr2: .asciiz "\nThe number of positive elements is: "

crlf: .asciiz "\n\n"

field: .word -2, 8, 3, -10, 20, 6, 30, -50, -32, 70


.text

main: li $v0, 4 # Print String
la $a0, str1 # load adress str1
syscall

li $t0, 0 # set starting field position
li $t1, 1 # counter for elaborating field position

lb $t2, field($t0) # first position of the field

minimum: lb $t3, field($t1) # current position  of the field

addiu $t1, $t1, 1 # counter := counter + 1
bgtu $t0, 10, exit # jump to exit if counter > 9
ble $t2, $t3, minimum # jump to minimum if $t2 <= $t3

move $t2, $t3
b minimum # jump to minimum


Would you say it's acceptable so far?

Thank you very much.


EDIT:
Thank you clive for the clarification - one problem solved.
I am a nervous wrack... Sitting here 7 hours in front of the current task and to subtask a. Spim gives me only crazy results:

The number of negative elements is: 3
The number of positive elements is: 7268501196

I can't understand why my code is wrong. My idea was that if I use shift right logical, the last number from the left side (0 -> positive, 1 -> negative) will be left. I don't want to put a strain on you with this task, since there are much more important things than helping a beginner like me, so if you see the mistake at a glance, it would be very nice, if you could tell me, what's wrong, otherwise I'll upload this version, hoping to get at least some points...

[clive]

The large number is because you are not setting the SYSCALL number for the string print.  See fixed code above.

[Herakles]

A thousand thanks, clive! :thumbu :U

Sitting here in front of it all night, I couldn't even spell my own name correctly, right now...

[clive]

Here refining the counting of negatives, and only loading the length once. This is a consideration if you want to expand the list, as you only need to modify one location, and is a more general solution.

Also loading WORDs, not BYTEs

Code Select Expand

        .data

str1:   .ascii "The number of negative and positive elements \n"
        .ascii "of the following field will be counted: \n"
        .asciiz "-2, 8, 3, -10, 20, 6, 30, -50, -32, 70\n"

answstr1: .asciiz "The number of negative elements is: "

answstr2: .asciiz "The number of positive elements is: "

crlf:   .byte   10, 13, 0

field:  .word   -2, 8, 3, -10, 20, 6, 30, -50, -32, 70

        .text

main:   li      $v0, 4          # Print String
        la      $a0, str1       # load adress str1
        syscall

        la      $a0, field      # load address of field

        li      $t0, 10         # field count, ONLY reference

        move    $t2, $t0        # positive count (PosCount)
        move    $t3, $zero      # negative count (NegCount)

count:  lw      $t1, 0($a0)     # current position of the field
        addiu   $a0, $a0, 4     # $a0 += 4 (word size)
        srl     $t1, $t1, 31    # $t1 = $t1 >> 31
        addu    $t3, $t3, $t1   # $t3 += $t1 (1=Neg, 0=Pos)
        addiu   $t0, $t0, -1    # $t0--
        bne     $t0, $zero, count

        subu    $t2, $t2, $t3   # $t2 = $t2 - $t3 (PosCount = Count - NegCount)

exit:   li      $v0, 4          # Print String
        la      $a0, answstr1   # Answer Message 1
        syscall

        li      $v0, 1          # Print Int
        move    $a0, $t3        # number of negative elements
        syscall

        li      $v0, 4          # Print String
        la      $a0, crlf       # Carriage Return, Line Feed
        syscall

        li      $v0, 4          # Print String
        la      $a0, answstr2   # Answer Message 2
        syscall

        li      $v0, 1          # Print Int
        move    $a0, $t2        # number of positive elements
        syscall

        li      $v0, 4          # Print String
        la      $a0, crlf       # Carriage Return, Line Feed
        syscall

        li      $v0, 10         # Exit
        syscall


[Herakles]

I'll have a look into it later on, since my tiredness now won't let me understand it... But it seems to be perfect.

This is my code to subtask b.
Spim falls into an infinite loop (hundreds of bad data errors), so please don't run it on your system.
Well the theory says "no (efficient) terminating condition -> infinite loop", but it's difficult for me to see where the problem is in this code...

Code Select Expand


.data

str1: .ascii "The minimum and maximum of the following \n"
.ascii "field will be counted: \n"
.asciiz "-2, 8, 3, -10, 20, 6, 30, -50, -32, 70\n"

answstr1: .asciiz "The minimum is: "

answstr2: .asciiz "\nThe maximum is: "

crlf: .asciiz "\n\n"

field: .word -2, 8, 3, -10, 20, 6, 30, -50, -32, 70


.text

main: li $v0, 4 # Print String
la $a0, str1 # load adress str1
syscall

li $t0, 0 # set starting field position
li $t1, 1 # counter for elaborating field position

lb $t2, field($t0) # first position of the field

minimum: lb $t3, field($t1) # current position of the field

addiu $t1, $t1, 1 # counter := counter + 1
bgtu $t0, 9, pre_max # jump to pre_max if counter > 9
ble $t2, $t3, minimum # jump to minimum if $t2 <= $t3

move $t2, $t3
b minimum # jump to minimum

pre_max: li $t0, 0 # set starting field position
li $t1, 1 # counter for elaborating field position

lb $t4, field($t0) # first position of the field

maximum: lb $t5, field($t1) # current position of the field

addiu $t1, $t1, 1 # counter := counter + 1
bgtu $t0, 9, exit # jump to exit if counter > 9
bge $t4, $t5, maximum # jump to maximum if $t4 >= $t5

move $t4, $t5
b maximum # jump to maximum

exit: li $v0, 4 # Print String
la $a0, answstr1 # Answer Message 1
syscall

li $v0, 1 # Print Int
move $a0, $t2 # minimum
syscall

li $v0, 4 # Print String
la $a0, answstr2 # Answer Message 2
syscall

li $v0, 1 # Print Int
move $a0, $t4 # maximum
syscall

li $v0, 4 # Print String
la $a0, crlf # Carriage Return, Line Feed
syscall

li $v0, 10 # Exit
syscall



[clive]

My stab at the min/max. The comparison method on your original code was good, there is a problem with how it looped and wasn't finding the 10th element as the smallest if I changed it to -70. I changed how/where I test for the exit condition.

It also differs from you last example as it searches for both min and max in a single pass.

You need to use LW to load words, which are 32-bits wide (4 bytes), as LB only load bytes, and consequently you only scan the first 2.5 entries and don't see the data you want to.

Code Select Expand

        .data

str1:   .ascii "The minimum and maximum elements \n"
        .ascii "of the following field will be identified: \n"
        .asciiz "-2, 8, 3, -10, 20, 6, 30, -50, -32, 70\n"

answstr1: .asciiz "The minimum elements is: "

answstr2: .asciiz "The maximum elements is: "

crlf:   .byte   10, 13, 0

field:  .word   -2, 8, 3, -10, 20, 6, 30, -50, -32, 70

        .text

main:   li      $v0, 4          # Print String
        la      $a0, str1       # load adress str1
        syscall

        li      $t0, 10         # field count

        la      $a0, field      # address of field list

        li      $t3, 0x7FFFFFFF # Largest positive number (min element will be smaller)
        li      $t4, 0x80000000 # Smallest negative number (max element will be bigger)

loop:   lw      $t2, 0($a0)     # current position of the field
        addiu   $a0, $a0, 4     # $a0 += 4, word is 4 bytes

        bge     $t2, $t3, bigger # jump to bigger if $t2 >= $t3

        move    $t3, $t2        # new minimum

bigger:

        ble     $t2, $t4, smaller # jump to smaller if $t2 <= $t4

        move    $t4, $t2        # new maximum

smaller:

        addiu   $t0, $t0, -1    # $t0--
        bne     $t0, $zero, loop

        li      $v0, 4          # Print String
        la      $a0, answstr1   # Answer Message 1
        syscall

        li      $v0, 1          # Print Int
        move    $a0, $t3        # value of minimum element
        syscall

        li      $v0, 4          # Print String
        la      $a0, crlf       # Carriage Return, Line Feed
        syscall

        li      $v0, 4          # Print String
        la      $a0, answstr2   # Answer Message 2
        syscall

        li      $v0, 1          # Print Int
        move    $a0, $t4        # value of maximum element
        syscall

        li      $v0, 4          # Print String
        la      $a0, crlf       # Carriage Return, Line Feed
        syscall

        li      $v0, 10         # Exit
        syscall


[Herakles]

I have still some questions concerning this task, but I'll ask them later on, since I have to go to university in a moment.

Here is the "sample solution" they gave us and I have to say, that they are very silly.
- The task said "at least 10 elements" and in their solution to subtask a) they just used seven elements.
- The "sample solution" to subtask b) must contain a bug, because nothing happens when I run it on PCSpim.

From my point of view the sample solution is very complex and there is no reason for making it so complex. But I am curious to get to know your opinion, clive.

Subtask a):

Code Select Expand


# #include <iostream.h>
# main() {
# int a[] = {-36, 20, -27, 15, 1, -62, -41};
# int n = 7, i, npos, nneg;
#
# for (i = npos = nneg = 0; i<n; i++) {
# if (a[i] == 0) continue;
# if (a[i] > 0) npos++;
# else nneg++;
# }
# cout << "+: " << npos << "; -: " << nneg  << endl;
# }

.data
a: .word -36, 20, -27, 15, 1, -62, -41
n: .word 7
max: .word 0
endl: .asciiz "\n"

.text
main: li $t0, 0 # i in $t0
li $t1, 0 # npos in $t1
li $t2, 0 # nneg in $t2
lw $s1, n # n in $s1

m1: bge $t0, $s1, m4
mul $t3, $t0, 4 # scale i
lw $t4, a($t3) # load a[i] into $t4
beqz $t4, m3 # if (a[i] == 0) ...
bgez $t4, m2 # if (a[i] > 0) ...
addi $t2, $t2, 1 # "else part": increment nneg
b m3 # skip over the "then part"

m2: addi $t1, $t1, 1 # "then part": increment npos
m3: addi $t0, $t0, 1 # i++
b m1

m4: move $a0, $t1 # print npos
li $v0, 1
syscall

la $a0, endl
li $v0, 4
syscall

move $a0, $t2 # print nneg
li $v0, 1
syscall

li $v0, 10
syscall




Subtask b):

Code Select Expand


.data
array: .word 3, 4, 2, 6, 12, 7, 18, 26, 2, 14, 19, 7, 8, 12, 13
count: .word 15
endl: .asciiz "\n"
ans1: .asciiz "min = "
ans2: .asciiz "\nmax = "

## Assumes the array has at least two elements (a[0]
## and a[1]). It initializes both min and max to a[0]
## and then goes through the loop count-1 times.
## This program will use pointers.
##
## t0 - points to array elements in turn
## t1 - contains count of elements
## t2 - contains min
## t3 - contains max
## t4 - each word from array in turn

.text
main: la $t0, array # $to will point to elements
lw $t1, count # exit loop when $t1 is 0
lw $t2, ($t0) # initialize both min ($t2)
lw $t3, ($t0) # and max ($t3) to a[0]
add $t0, $t0, 4 # pointer to start at a[1]
add $t1, $t1, -1 # and go round count-1 times

loop: lw $t4, ($t0) # load next word from array
bge $t4, $t2, notMin
# skip if a[i] >= min
move $t2, $t4 # copy a[i] to min
notMin: ble $t4, $t3, notMax
# skip if a[i] <= max
move $t3, $t4 # copy a[i] to max
notMax: add $t1, $t1, -1 # decrement counter
add $t0, $t0, 4 # increment pointer by word
bnez $t1, $loop # and continue if counter>0

la $a0, ans1
li $v0, 4
syscall # print "min = "

move $a0, $t2
li $v0, 1
syscall # print min

la $a0, ans2
li $v0, 4
syscall # print "\nmax = "

move $a0, $t3
li $v0, 1
syscall # print max

la $a0, endl # system call to print
li $v0, 4 # out a newline
syscall

li $v0, 10
syscall # au revoir...



[BogdanOntanu]

No homework rule ... locked.