base:mathematics_in_assembly_part_5

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

— |
base:mathematics_in_assembly_part_5 [2015-04-17 04:32] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | ====== Mathematics in Assembly - Part 5 ====== | ||

+ | |||

+ | by Krill/Plush | ||

+ | |||

+ | And again we (still...) discuss multiplication. At first an apology to all who are already fed up with it but according to my opinion, all commonly used methods to multiply should be discussed in these tutorials, as it really depends on the specific problem and which approach is more optimal for solving it. Apart from that, also seemingly rather less interesting approaches can help finding new ideas and insights, and I'm telling that from my own experience. Enough useless talk for now. Let's begin. | ||

+ | |||

+ | The method of bit-wise multiplication discussed in the previous article is, seen relatively to it's possibilities, | ||

+ | |||

+ | Shall also the second factor be chose arbitrarily, | ||

+ | |||

+ | Now what to do? Do you remember the old school times, where your maths teachers could multiply almost arbitrary numbers unbelievably fast (for a pupil) only using their heads, or those dudes in TV-shows multiplying extremely long numbers? The trick' | ||

+ | |||

+ | ====== Binomial formulas? ====== | ||

+ | |||

+ | Exactly. Here we have a small approach showing what's meant by that | ||

+ | |||

+ | < | ||

+ | a * b = (4*a*b) / 4 | ||

+ | = (2*a*b + 2*a*b) / 4 | ||

+ | = (2*a*b + 2*a*b +a^2 - a^2 + b^2 - b^2) / 4 | ||

+ | = (a2+2*a*b+b^2) - (a^2-2*a*b+b^2) / 4 | ||

+ | = ( (a^2+2*a*b+b^2) - (a^2-2*a*b+b^2) ) / 4 | ||

+ | = ((a+b)^2 - (a-b)^2) / 4 | ||

+ | = (a+b)^2/4 - (a-b)^2/4 | ||

+ | </ | ||

+ | |||

+ | From line 5 to line number 6 one can see what's meant by binomial formulas: the two bracketed terms were transformed to two binomes using the 2nd binomial formula. But what's the use of this mathematical transformation? | ||

+ | |||

+ | To square a number only needs one argument, an addition is one of the simplest exercises for the processor, and the division by four is also just a twofold binary shifting right. | ||

+ | |||

+ | So we just derived a formula for fast multiplication, | ||

+ | |||

+ | < | ||

+ | STA factor1 ; factors in accu and x-register | ||

+ | TXA | ||

+ | SEC | ||

+ | SBC factor1 | ||

+ | TAY ; factor 2 - factor 1 | ||

+ | TXA | ||

+ | CLC | ||

+ | ADC factor1 | ||

+ | TAX ; factor 2 + factor 1 | ||

+ | SEC | ||

+ | LDA table,x | ||

+ | SBC table,y ; subtract the squares | ||

+ | </ | ||

+ | |||

+ | As a result we get the product of the two factors. By the way, in this routine the factors of the derivation are swapped, but that does not matter at all because of the commutative law. Furthermore, | ||

+ | |||

+ | I hope that you understood my explanations. Now just only a small hint for generating the table (which is always better than having pre-stored tables as it's more memory efficient): the squares are 0, 1, 4, 9, 16 etc.; the differences 1, 3,5, 7 etc. - so the table can be generated only using the addition and shifting right and without complicated routines. | ||

+ | |||

+ | That's it for this article. Read this magazine' | ||

+ | |||

+ | Krill | ||

base/mathematics_in_assembly_part_5.txt ยท Last modified: 2015-04-17 04:32 (external edit)