8. Multiplication and Division
Multiplication
Multiplication is just repeated addition, however, this is not efficient for larger values. Now if we remember our multiplication tables, we can do much better.
Then, using these tables, we can do partial products and add those products to get our final result.
This works since we are using the foil method of grouping. For example, $78\cdot 54=78\cdot 50 + 78\cdot 4$.
Unlike addition, when we multiply two n-digit numbers, we get at most 2n digits. This is a problem. So, mips has two 32-bit registers for this, HI and LO. The mul instruction is really a mult then mflo.
We could also divide-and-conquer multiplication. Which can reduced our time complexity down to $O(log(n))$.
Division
Division is repeated substraction. But more complicated.
If we go backwards, we see all we are really doing is partial products.
With binary, it works similarly:
MIPS, like multiplication, uses HI and LO for division. div does signed division, divu does unsigned division. It uses HI for the remainder and LO for quotient. To get the HI and LO, use mfhi and mflo.