|
Alright, let's go on with some more maths. This time we'll discuss one of the fastest approaches to divide. Those who remember earlier parts of this tutorial might be able to guess it. Yes, it's the logarithm again, but this time applied on division rather than multiplication.
As this method is very similar to multiplication using logarithm, I won't go into very much detail and refer to part 6 of this tutorial, which had been (re-)published in "Vandalism News #40". Anyways, the logarithm law we use is this:
log[a] (u/v) = log[a] (u) - log[a] (v)
And after a bit of modification:
a^log[a] (u/v) = a^(log[a] (u) - log[a] (v))
u/v = a^(log[a] (u) - log[a] (v)
The logarithm's basis is denoted as [a]. That's the basic theory. Again, we need some look-up tables to perform quick logarithms and exponentiations.
BUILDING THE TABLES
It's recommended to use 2 as base for the logarithm. As arguments and result are arbitrarily accurate, the following examples will have unsigned 8-bit integer dividend and divisor. The divisor must always be bigger than the dividend, so that the result can then be something between 0 and 255/256.
Why's that? A routine like this has mainly one area of application on the C-64: fast line drawing. This needs slopes to be calculated, and those will never be bigger than 1. They are calculated in x direction if the angle between x-axis and the line is 0 to 45 degrees. If the line is steep and thus the angle between it and the x-axis is 45 to 90 degrees, the slope is calculated in y direction. This basically means swapping dividend and divisor, and that's why the quotient is never bigger than 1.
First a table is needed that contains the binary logarithm for the arguments 1 through 255, where that logarithm is scaled to 0 to 255. The scaling factor is given as:
f = 255/log[2] (255)
The logarithm table can be generated like this:
1 FOR X=0 TO 255
2 Y=F*LOG(X)/LOG(2)+.5
3 POKE LOG2TAB+X,Y
4 NEXT
Furthermore, the exponentiation table is needed, but it's smaller for division than for multiplication, since the arguments are never bigger than log[2] (255), which means that the biggest index into the table is 255. A small problem arises. As the divisor's logarithm is subtracted from the dividend's logarithm, the result is always negative, so there is a negative index into the exponentiation table. This problem can be solved with a small trick: the table is reversed and thus starts with the biggest possible result. So, if e.g. the resulting table index is $FF (i.e., -1), the correct value will be read from the table. The generation routine for the second table looks like this:
1 FOR X=1 TO 255
2 Y=2^(8-X/F)+.5
3 POKE POW2TAB+X,Y
4 NEXT
Line 2 looks a bit different than the corresponding code for multiplication. The loop should be passed from 0 to 255, but the resulting value at index 0 would be 256, i.e., bigger than 8 bits. The solution is to simply set table element 0 to 255 instead of 256 outside the loop. This will yield some inaccuracies but simplifies usage (e.g. in a line drawing routine) enormously.
THE ROUTINE
The tables are then accessed like this:
SEC
LDA log2tab,y
SBC log2tab,x
TAX
LDA pow2tab,x
X and Y contain the arguments, dividend in X and divisor in Y. After executing the routine, which weighs in at just 16 cycles, the accu contains the quotient. Note that the dividend's logarithm is subtracted from the divisor's logarithm rather than vice versa in order to solve the aforementioned index sign problem. Basically C=A-B was replaced by -C=B-A, which results in this argument swapping.
ACCURACY
In this configuration, the routine is just barely accurate - the error is about 2 bits left of the comma on average. To increase accuracy, the tables can be enlarged and accessed with indices bigger than 8 bits. The scaling factor f increases accordingly. For details, please refer to part 6 of this tutorial. The methods used for sign handling and other argument and result ranges are the same as with previous approaches.
This method is not suited for complex and very accurate calculations, because very large tables are needed for that, which also makes the routine larger and slower, making common bit-wise division a better choice.
That's it for basic arithmetic operations. The following parts of this tutorial will discuss some less often used operations, starting with the square root. See you!
KRILL/PLUSH |
