## On Equivalence, Multiplication and Efficiency

I recently came across a blog post by Brett Berry on *Why 5 x 3 = 5 + 5 + 5 Was Marked Wrong*. Twitter-discussion of how children should be taught aside, the post imho is an interesting read; the TL;DR of which is that while `5 x 3 = 15`

and therefore is **equal** to `5 + 5 + 5`

, it is **equilvalent** only to `3 + 3 + 3 + 3 + 3`

. This is due to the fact that the first factor of the multiplation equation represents the *number of times* that the second factor is to be *accumulated*. Therefore `5 x 3`

is equivalent to an operation whereby the number `3`

is *accumulated* `5`

times, i.e. `3 + 3 + 3 + 3 + 3`

.

This may seem like a frivilous distinction; after all the function `f() = 5 x 3`

will always yield `15`

. However whether the function implements the operation internally as `3 + 3 + 3 + 3 + 3`

or `5 + 5 + 5`

will impact the *efficiency* of the function. The two respective implementations fail the equivalence test when their execution time is considered.

Take for example the implementation of an 8-bit multiplication function in the *CUPC/8* kernel code:

mul_n: resb 1 math_mul: st [mul_n], r0 xor r0, r0 .loop: push r0 ld r0, [mul_n] eq r0, #0 bzf .done sub r0, #1 st [mul_n], r0 pop r0 add r0, r1 b .loop .done: pop r0 pop pcl pop pch

The `mul_n`

variable, received as a function parameter in register `r0`

represents the *number of times* the value from register `r1`

should be accumulated. As the Arithmetic Logic Unit takes exacly the same amount of time to add two 8-bit numbers regardless of their values, it obviously makes sense to limit `mul_n`

, thereby limiting the number of loop iterations the function will execute. Calling `math_mul(3, 5)`

would perform `5 + 5 + 5`

and is obviously preferable efficiency-wise to `math_mul(5, 3)`

(`3 + 3 + 3 + 3 + 3`

).