Finding the lowest of 4 values

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

Post Reply
Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Finding the lowest of 4 values

Post by Drakim »

I have four RAM bytes labeled Var1, Var2, Var3 and Var4. I want to jump to four different subroutines depending on which one is lowest.

I thought this would be fairly simple when I started coding, but I've run into some edge cases that got me stumped. This was my attempt:

Code: Select all

    LDA Var1
    CMP Var2
    BCS +next
    CMP Var3
    BCS +next
    CMP Var4
    BCS +next
    JMP Subroutine1

    +next:
    LDA Var2
    CMP Var1
    BCS +next
    CMP Var3
    BCS +next
    CMP Var4
    BCS +next
    JMP Subroutine2

    +next:
    LDA Var3
    CMP Var1
    BCS +next
    CMP Var2
    BCS +next
    CMP Var4
    BCS +next
    JMP Subroutine3

    +next:
    JMP Subroutine4
    
The idea being that Subroutine4 wins out if no other block of comparisons jumps you out. But it fails because if Var1 is $30 and Var2 is $30 then neither is lower than the other and thus Subroutine4 is selected despite potentially being $40 which is higher than both. For ties I don't really care which of the tied subroutines wins out, but I can't just add a BEQ instruction that jumps out on ties, as if I do that I never get around to testing Var3 which might actually be $10 and should have won over the tie.

Can somebody point me in the right direction on how to do this properly?
Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Re: Finding the lowest of 4 values

Post by Drakim »

Ah, I figured it out and now I feel silly, I simply compare in the other direction, which makes everything easier:

Code: Select all

    LDA Var1
    CMP Var2
    BCC +next
    CMP Var3
    BCC +next
    CMP Var4
    BCC +next
    JMP Subroutine1

    +next:
    LDA Var2
    CMP Var3
    BCC +next
    CMP Var4
    BCC +next
    JMP Subroutine2

    +next:
    LDA Var3
    CMP Var4
    BCC +next
    JMP Subroutine3

    +next:
    JMP Subroutine4
 
Last edited by Drakim on Sun Sep 18, 2022 12:55 am, edited 1 time in total.
Bavi_H
Posts: 193
Joined: Sun Mar 03, 2013 1:52 am
Location: Texas, USA
Contact:

Re: Finding the lowest of 4 values

Post by Bavi_H »

But you still want the lowest variable to win right? In your new code (using BCC), if you reach the first JMP, that means Var1 is the highest, right?

When I look at your original code (using BCS), here's my thinking:

If you got to the first JMP then Var1 was the lowest.

If you got to the first +next, then Var1 wasn't the lowest, so you don't need to do any more comparisons with Var1.

Code: Select all

LDA Var1
CMP Var2
BCS +next
CMP Var3
BCS +next
CMP Var4
BCS +next
JMP Subroutine1

+next:
LDA Var2
CMP Var3
BCS +next
CMP Var4
BCS +next
JMP Subroutine2

+next:
LDA Var3
CMP Var4
BCS +next
JMP Subroutine3

+next:
JMP Subroutine4
Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Re: Finding the lowest of 4 values

Post by Drakim »

BCC branches if carry is clear
CMP sets carry if A >= M

That means the code would run like this:

Code: Select all

    LDA Var1
    CMP Var2		; Carry set if Var1 >= Var2
    BCC +next		; Jump to +next if carry clear
    CMP Var3		; Carry set if Var1 >= Var3
    BCC +next		; Jump to +next if carry clear
    CMP Var4		; Carry set if Var1 >= Var4
    BCC +next		; Jump to +next if carry clear
    JMP Subroutine1
That means that Var1 needs to be lower than Var2, Var3, and Var4. So if the JMP here runs, it means Var1 was lowest, not highest.
Bavi_H
Posts: 193
Joined: Sun Mar 03, 2013 1:52 am
Location: Texas, USA
Contact:

Re: Finding the lowest of 4 values

Post by Bavi_H »

Code: Select all

LDA Var1   ; \
CMP Var2   ; |
BCC +next  ; / If Var1 < Var2, go to +next. (If Var1 >= Var2, go to the next instruction.)
CMP Var3   ; \
BCC +next  ; / If Var1 < Var3, go to +next. (If Var1 >= Var3, go to the next instruction.)
CMP Var4   ; \
BCC +next  ; / If Var1 < Var4, go to +next. (If Var1 >= Var4, go to the next instruction.)

JMP Subroutine1  ; (If we got to here, then Var1 >= Var2 and Var1 >= Var3 and Var1 >= Var4.)

+next:     ; (If we got to here, then Var1 < Var2 or Var1 < Var3 or Var1 < Var4.)
...
Drakim
Posts: 97
Joined: Mon Apr 04, 2016 3:19 am

Re: Finding the lowest of 4 values

Post by Drakim »

Ah, you are totally right, in my mind I was thinking in the opposite direction :D

Using a BCC would branch away when Var1 is lowest, when I actually want to keep going.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Finding the lowest of 4 values

Post by Drag »

In general, when you want to figure out which variable in a collection of variables is the smallest, the simplest way to do so is to go through all of them, one by one, while keeping track of what the smallest value you've seen so far is.

Code: Select all

var minVal = var1
var minVarNum = 1;
if (var2 < minVal ) {
    minVal = var2;
    minVarNum = 2;
}
if (var3 < minVal ) {
    minVal = var3;
    minVarNum = 3;
}
if (var4 < minVal ) {
    minVal = var4;
    minVarNum = 4;
}
It doesn't matter which order you look at the variables in, the important thing is that you've looked at all of them, each time.

If it's a small number of variables, such as 4, you can get away with writing an IF statement for each one. If you need to expand it into 6 or more, I'd recommend changing this to a loop instead.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Finding the lowest of 4 values

Post by tokumaru »

I normally solve these kinds of problems like Drag suggested. If you're using 8-bit numbers stored in a sequential list, the implementation in assembly could be something like this:

Code: Select all

  ldx #$00 ;assumes that item 0 is the smallest

  lda Values+1 ;loads item 1
  cmp Values, x ;compares it against the smallest
  bcs :+ ;branches if item 1 is equal or larger
  ldx #$01 ;makes item 1 the smallest
:
  lda Values+2 ;loads item 2
  cmp Values, x ;compares it against the smallest
  bcs :+ ;branches if item 2 is equal or larger
  ldx #$02 ;makes item 2 the smallest
:
  lda Values+3 ;loads item 3
  cmp Values, x ;compares it against the smallest
  bcs :+ ;branches if item 3 is equal or larger
  ldx #$03 ;makes item 3 the smallest
:
  lda SubroutineAddressesLow, x
  sta Pointer+0
  lda SubroutineAddressesHigh, x
  sta Pointer+1
  jmp (Pointer)
And here's the same thing, but using a loop:

Code: Select all

  ldx #$00 ;assumes that item 0 is the smallest
  ldy #LAST_INDEX ;starts testing from the last item

TestItem:

  lda Values, y ;loads the current item
  cmp Values, x ;compares it against the smallest
  bcs :+ ;branches if the current item is equal or larger
  tya ;makes the current item the smallest
  tax
:
  dey ;goes to the previous position
  bne TestItem ;branches if this is not the first position
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: Finding the lowest of 4 values

Post by Oziphantom »

If out of sequence or hard to put into sequence for various reasons

Code: Select all

	ldx #0
	lda Value1
	cmp Value2		; compare Value1 < Value2
	bcc +
		lda Value2	; value 2 is smaller, so load into a
		ldx #1		; set 2nd value as smallest
+	cmp Value3		; compare result against Value3
	bcc +
		lda Value3	; value 3 is smaller, so load into a
		ldx #2		; set 3rd value as smallest
+	cmp Value4
	bcc +
 		ldx #3		; value 4 is smaller, set 4th value as smallest
+	lda CallFunctionTable_hi,x
	pha
 	lda CallFunctionTable_lo,x
 	pha
 	rts

CallFunctioTable_hi
    .byte >(Val1Smallest-1), >(Val2Smallest-1), >(Val3Smallest-1), >(Val4Smallest-1)
CallFunctionTable_lo
    .byte <(Val1Smallest-1), <(Val2Smallest-1), <(Val3Smallest-1), <(Val4Smallest-1)
   
Post Reply