# ### Site Tools

base:mathematics_in_assembly_part_3

# Differences

This shows you the differences between two versions of the page.

 — base:mathematics_in_assembly_part_3 [2015-04-17 04:32] (current) Line 1: Line 1: + ====== Prologue ====== + + Hello dear sceners, this is the third chapter of my tutorial on maths in assembly, + first published in "​GO64!"​ magazine. The first two chapters of this turorial were + re-published in "​Attitude #4" and "​Domination #17". Have a nice read! + + ====== Mathematics in Assembly, Part 3 ====== + + After increasing the precision of our numbers we're going to have a look at a + slightly more difficult topic, namely the multiplication. But take it easy, this + a bit more complex mathematic operation can be done in many different ways, + depending on the memory an execution time requirements. The simplest implementation + of the multiplication would of course be a simple loop which just increases a zero- + initialised counter by the first multiplication factor as often as the absolute + value of factor 2 demands. This extremely inelegant brute force method is naturally + very inefficient and slow, that's why it's just mentioned in passing here and not + going to be discussed in any more detail. let's take a look at some more elegant + approaches: + + ====== Multiplication by Constants ====== + + A kind of multiplication relatively often needed is to multiply by constants, as it + just takes quite a small and fast algoritm. As an example constant we just take 11 + (\$0B, %00001011). Using our knowledge about binary arithmetic, we can easily reduce + this number to powers of two: + + <​code>​ + 11 =  8  +  2  +  1 + = 2^3 + 2^1 + 2^0 + ​ + + If we wanted to multiply this number with let's say 25 (\$19, %00011001), it would + look like this if written on paper: + + <​code>​ + 11 * 25 = 2^3 * 25 + 2^1 * 25 + 2^0 * 25 + =  8  * 25 +  2  * 25 +  1  * 25 + ​ + + What's all this needed for, you might ask. Very simple: the seperate summands of + the created expression are all shifted 25's. So it's as easy as this: the accu + contains an arbitrary number to be multiplied by the given constant. The number is + shifted by the needed positions an buffered. Afterwards, all summands are added. + Just a small pice of example code: + + <​code>​ + LDA #\$19    ; arbitrary factor + STA BUFFER0 ; some byte in the memory, 2^0 * factor + ASL         ; doubling of the factor + STA BUFFER1 ; buffer 2^1 * factor + ASL         ; doubling + ASL         ; doubling, all in all 8 * factor + CLC         ; clear carry for addition (whithout overflow, like here, actually + ; unnecessary) + ADC BUFFER0 ; 2^3 * factor + 2^0 * factor + ADC BUFFER1 ; 2^3 * factor + 2^0 * factor + 2^1 * factor + ​ + + Simple. Oh, all examples will, just like this one, for the sake of simplicity, + refer to unsigned 8-bit integers to be multiplied. By the way, there are some + "​factors"​ to be aware of with the multiplication. + + ====== Whats to be paid attention of ====== + + #1: After multilying two factors, the result has the double size, for instance + 16 bits with two 8-bit factors. Quite obvious, as for example + 255^2 = \$FF * \$FF = \$FE01. Nevertheless,​ for the sake of simplicity, I'll take + appropriately small values in order not to cause any overflows. + + #2: Also with computers, the exact result of multiplying two fractions has as + many decimals as both the factors have together. So the product of two fixed + point numbers with let's say one fraction byte each has two fraction bytes. + Together with the squaring of the number range this means, for instance: the + product of two 16-bit fixed point numbers with one fraction byte each is + 32 bits in size, 16 bits left hand of the point, 16 bits right hand of it. + + #3: in order to multiply signed numbers, the signs of both factors are + buffered and the absolute value of the result is calculated by multiplying + the absolute values of the factors. Afterwards, the buffered signs are + avaluated and the result is signed accordingly. Of course, the common rules + also apply here, so plus my minus is minus and minus by minus is plus. + + Good. The multiplication in general and in particular with constants can also + done in another way, the magic word here is tables. + + Tables? Correct. More exactly "Look Up Tables"​. Using these tables, it's + possible to calculate products extremely fast, or let's better say "to find + them out" extremely fast. For tha, a table has to be generated at the + beginning of the program, in this case containing the multiplies of the + constant in rising order. With the constant 3 (\$03, %00000011), it would look + like this: + + <​code>​ + \$00, \$03, \$06, \$09, \$0c, ... + ​ + + This table is just read out, using the arbitrary factor as index. On + principle, this table is as large as the range of the factor is, i.e. 256 + bytes with a 1-byte-sized factor. By the way, generating this table, the + above mentioned brute force method can be used, as with the initialisation + speed plays a minor role compared to memory efficiency. + + That's it for the first couple of possibilities to multiply. The next three + chapters will be published in "​Vandalism News Ruby Edition",​ discussing some + more ways to multibly assembly, starting with the most flexible kind of + multiplication,​ the bit-wise multiplication. See You! 