12
\$\begingroup\$

I was trying to write a short MIPS32 code for computing the median of three registers.

The rules:

  • Assume that some values are pre-loaded into $t0, $t1, $t2.
  • The median of the three values should be placed in $t0.
  • No branches are allowed, but otherwise any instruction is okay.
  • You may arbitrarily modify the values of all registers.

I was able to optimize it down to 15 instructions. Can you do better?

\$\endgroup\$
6
  • \$\begingroup\$ Welcome to Code Golf! I added the code-golf tag, but other than that this challenge looks good. (You might still want to check out the sandbox for future challenges, it can be pretty useful sometimes) \$\endgroup\$ Commented Nov 2, 2021 at 16:59
  • \$\begingroup\$ @RedwolfProgrammed - thanks! \$\endgroup\$
    – M A
    Commented Nov 2, 2021 at 17:00
  • 1
    \$\begingroup\$ I've retagged this as atomic-code-golf since the count seems to be the number of instructions, although this could be made more clear in the body of the challenge. \$\endgroup\$
    – Wheat Wizard
    Commented Nov 2, 2021 at 20:08
  • \$\begingroup\$ May I modify some specific addresses in memory? May I use jump instructions j/jal/jr? May I modify the code during execution? \$\endgroup\$
    – Bubbler
    Commented Nov 3, 2021 at 0:45
  • \$\begingroup\$ @Bubbler - anything is allowed except branches. \$\endgroup\$
    – M A
    Commented Nov 4, 2021 at 9:49

2 Answers 2

8
\$\begingroup\$

7 instructions

slt $t3, $t0, $t1
slt $t4, $t2, $t1
slt $t5, $t2, $t0

Compare all three pairs of values.

xor $t3, $t3, $t4
movn $t0, $t1, $t3

$t1 is the median if it is greater than exactly one of the other values.

xor $t5, $t5, $t4
movn $t0, $t2, $t5

$t2 is the median if it is less than exactly one of the other values.

(Otherwise, $t0 is already the median.)

\$\endgroup\$
1
  • \$\begingroup\$ Very nice. I followed the same logic, but my implementation required more than twice the number of instructions :). \$\endgroup\$
    – M A
    Commented Nov 4, 2021 at 8:40
5
\$\begingroup\$

8 instructions

slt $t4, $t2, $t1
movn $t3, $t1, $t4
movn $t1, $t2, $t4
movn $t2, $t3, $t4

Rearrange $t1 and $t2 so that $t1$t2.

slt $t3, $t2, $t0
slt $t4, $t0, $t1
movn $t0, $t2, $t3
movn $t0, $t1, $t4

If $t0 falls between $t1 and $t2, it is already the median. If it's outside that range, the one it lies beyond is the median.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.