Efficient and Concise Multiplication in CHIP-8 I've entertained how to nicely express a decent many algorithms in CHIP-8 but hadn't thought my such thoughts warranted an article. I recently read of someone doing something similar, and this changed my mind. This other wrote a program to unintelligently and inefficiently find instruction listings. My approach targets multiplication and uses simple logic to get, I think, a nicer result; in mulling possible instructions, it's clear which are applicable; if the machine can or can't perform the task in one instruction it's clear if, say, two are found to suffice they form an answer and upper bound. Binary shifts give powers of two a clear advantage, and an important aspect of intelligently hacking machine code is to consider global optimizations; this simple routine is optimal for all such shifts and it could be optimized further through more indirection to handle register management. The first shift is unnecessary; it ultimately clears the register. These are placed at no particular address: 400-401 1024-1025 ▀ ▄▄▄ 800E 32782  ×256 V0 ← V0 × 2; VF ← MSB 402-403 1026-1027 ▀ ▄▄▄ 800E 32782  ×128 V0 ← V0 × 2; VF ← MSB 404-405 1028-1029 ▀ ▄▄▄ 800E 32782  ×64 V0 ← V0 × 2; VF ← MSB 406-407 1030-1031 ▀ ▄▄▄ 800E 32782  ×32 V0 ← V0 × 2; VF ← MSB 408-409 1032-1033 ▀ ▄▄▄ 800E 32782  ×16 V0 ← V0 × 2; VF ← MSB 40A-40B 1034-1035 ▀ ▄▄▄ 800E 32782  ×8 V0 ← V0 × 2; VF ← MSB 40C-40D 1036-1037 ▀ ▄▄▄ 800E 32782  ×4 V0 ← V0 × 2; VF ← MSB 40E-40F 1038-1039 ▀ ▄▄▄ 800E 32782  ×2 V0 ← V0 × 2; VF ← MSB 410-411 1040-1041 ▄▄▄ ▄▄▄ 00EE 00238  Return Addition of a register with itself or a lone shift instruction are both suitable for a doubling, but the latter has the significant advantage of selecting a destination register rather than clobbering. A simple multiplication by three uses a second register, forming this trivial pair: 200-201 0512-0513 ▀ ▄▄▄▀ 810E 33038  V1 ← V0 × 2; VF ← MSB 202-203 0514-0515 ▀ ▄ ▀ 8104 33028  V1 ← V1 + V0; VF ← overflow A multiplication by five is opportunity to use part of the routine and is a mere instruction larger: 200-201 0512-0513 ▀ ▀ 8100 33024  V1 ← V0 202-203 0514-0515  ▀ ▄█ 240C 09228  Call ×4 204-205 0516-0517 ▀ ▄ ▀ 8104 33028  V1 ← V1 + V0; VF ← overflow Multiplying by seven is close enough to a power of two for this alternative approach to be pleasant: 200-201 0512-0513 ▀ ▀ 8100 33024  V1 ← V0 202-203 0514-0515  ▀ ▄▀▄ 240A 09226  Call ×8 204-205 0516-0517 ▀ ▄ ▄ ▄ 8015 32789  V0 ← V0 − V1; VF ← borrow Multiplying by larger numbers well uses fragmentation; this takes twenty-four as eight plus sixteen: 200-201 0512-0513 ▀ ▄ 8010 32784  V0 ← V1 202-203 0514-0515  ▀ ▄▀▄ 240A 09226  Call ×8 204-205 0516-0517 ▀ ▀ 8200 33280  V2 ← V0 206-207 0518-0519 ▀ ▄ 8010 32784  V0 ← V1 208-209 0520-0521  ▀ ▄▀ 2408 09224  Call ×16 20A-20B 0522-0523 ▀ ▄ ▄ 8024 32804  V0 ← V0 + V2; VF ← overflow That's no comparison to the much nicer method of splitting twenty-four as eight times three, though: 200-201 0512-0513 ▀ ▄▄▄▄ 801E 32798  V0 ← V1 × 2; VF ← MSB 202-203 0514-0515 ▀ ▄ ▄ 8014 32788  V0 ← V0 + V1; VF ← overflow 204-205 0516-0517  ▀ ▄▀▄ 240A 09226  Call ×8 The number forty-three, resulting by adding or subtracting powers of two, should suit as a bad case: 200-201 0512-0513 ▀ ▄ 8010 32784  V0 ← V1 202-203 0514-0515  ▀ █▄ 2406 09222  Call ×32 204-205 0516-0517 ▀ ▀ 8200 33280  V2 ← V0 206-207 0518-0519 ▀ ▄ 8010 32784  V0 ← V1 208-209 0520-0521  ▀ ▄▀▄ 240A 09226  Call ×8 20A-20B 0522-0523 ▀ ▄ ▄ 8024 32804  V0 ← V0 + V2; VF ← overflow 20C-20D 0524-0525 ▀ ▄ ▄ 8014 32788  V0 ← V0 + V1; VF ← overflow 20E-20F 0526-0527 ▀ ▄ ▄ 8014 32788  V0 ← V0 + V1; VF ← overflow 210-211 0528-0529 ▀ ▄ ▄ 8014 32788  V0 ← V0 + V1; VF ← overflow Notice three additions is cost just large enough to make other approaches infeasible; multiplication by four, followed by a subtraction, is one instruction larger, due to the extra register management; replacing the three additions with one and a shifting results in the same count, and so isn't shown: 200-201 0512-0513 ▀ ▄ 8010 32784  V0 ← V1 202-203 0514-0515  ▀ █▄ 2406 09222  Call ×32 204-205 0516-0517 ▀ ▀ 8200 33280  V2 ← V0 206-207 0518-0519 ▀ ▄ 8010 32784  V0 ← V1 208-209 0520-0521  ▀ ▄▀▄ 240A 09226  Call ×8 20A-20B 0522-0523 ▀ ▄▀ 8204 33284  V2 ← V2 + V0; VF ← overflow 20C-20D 0524-0525 ▀ ▄ 8010 32784  V0 ← V1 20E-20F 0526-0527  ▀ ▄█ 240C 09228  Call ×4 210-211 0528-0529 ▀ ▄ ▄ 8024 32804  V0 ← V0 + V2; VF ← overflow 212-213 0530-0531 ▀ ▄ ▄ ▄ 8015 32789  V0 ← V0 − V1; VF ← borrow Loop adding forty-three would be concise, but inefficient; a table is a good solution yet changes I: 200-201 0512-0513 ▀ ▀ ▄ ▀ A208 41480  I ← forty three 202-203 0514-0515 ▀▀▀█▄▄▄ F01E 61470  I ← I + V0 204-205 0516-0517 ▀██▀ ▄ ▄ F065 61541  Load V0→V0; I ← I + 01 206-207 0518-0519 ▄▄▄ ▄▄▄ 00EE 00238  Return 208 0520  00 000  forty three 209 0521  █ █ ██ 2B 043 20A 0522  █ █ ██ 56 086 20B 0523 █ █ 81 129 20C 0524 █ █ ██ AC 172 20D 0525 ██ █ ███ D7 215 Know the lower registers are rather poor choices for practical routines here, and zero in particular due to its use by BXXX. I will provide no general rule for determining efficient multiplication, as this can easily be done by a human at a whim. An easy way to get good multiplication chooses a good number to multiply by. Making a routine unnecessary is much better than making such more efficient. .