More about programming arithmetic operations (addition)

Hello, All! ═══════════════════ mult .t ══════════════════ (c) Ivan Roshchin, Moscow Fido: 2:5020/689.53 ZXNet: 500:95/462.53 E-mail: bestview@mtu-net.ru WWW: http://www.ivr.da.ru More about programming arithmetic operations (addition) ═════════════════════════════ ══════════════════════════════ In [1], considering various methods of fast multiplication integers, I gave two formulas taken from [2]: 1 2 2 2 xy = ─ ((x+y) - x - y ), (1) 2 1 2 2 xy = ─ ((x+y) - (x-y) ). (2) 4 I further stated: "To get rid of division by 2 in the first formula and from dividing by 4 in the second, it is enough to store in the table of squares already divided by 2 or 4 values. Multiplication will be faster, but will be inaccurate, especially for small values of the factors." In other words, the following was meant: ┌ 2┐ ┌ 2┐ ┌ 2┐ │(x+y) │ │ x │ │ y │ xy ~= │───── │ - │ ─ │ - │ ─ │, (3) └ 2 ┘ └ 2 ┘ └ 2 ┘ ┌ 2┐ ┌ 2┐ │(x+y) │ │(x-y) │ xy ~= │───── │ - │───── │. (4) └ 4 ┘ └ 4 ┘From what followed my conclusions about the inaccuracy of multiplication using these formulas? Since when stored in a table already divided by 2 (or 4) values (i.e. whole parts of these values) occurs loss of accuracy, it is logical to assume that the calculations will be occur with error. Since the absolute size errors are limited when multiplying large values the relative error will be small, and with a decrease factors it will increase. It seems that everything is obvious, right? It seemed that way to me too. :-) B reality, even statements that are obvious at first glance need careful checking. While looking through [3], I found a formula equivalent to the following: ┌ 2┐ ┌ 2┐ │(x+y) │ │(x-y) │ xy = │───── │ - │───── │. (5) └ 4 ┘ └ 4 ┘ This is the same as formula (4), only the equality It turned out to be not approximate (as I thought), but accurate. Why? In [3] it is stated that the fractional parts (x+y)^2/4 and (x-y)^2/4 are equal. Indeed, the product of integers x and y is also an integer, and the difference of two numbers (x+y)^2/4 and (x-y)^2/4 can be whole only when their fractional parts are equal. Thus, discarding fractional parts in this case does not affect the result obtained, and multiplication according to formula (5) is valid will be accurate.By the way, in [3] it is also mentioned that this formula, together with table of function values [z^2/4] for natural values of z used to facilitate the multiplication of multi-digit numbers before the invention of logarithm tables. Maybe formula (3) also provides exact multiplication? Let's check it out. Since x and y can be even or odd, There are four different cases possible. 1. x is even, y is even. Then (x+y)^2, x^2, y^2 will be even, and the fractional parts of all three expressions in brackets will be equal to 0. 2. x is even, y is odd. Then x+y is odd, (x+y)^2 is also odd (fractional part (x+y)^2/2 is equal to 1/2). x^2 even (fractional part of x^2/2 is 0), y^2 is odd (fractional part of y^2/2 is 1/2). As a result, after subtraction, the fractional parts are mutually will be destroyed, which means that the result of discarding them will not will change. 3. x is odd, y is even - the situation is similar to the previous one, because the formula is symmetrical with respect to x and y. 4. x is odd, y is odd. Then x+y is even, (x+y)^2 is also is even (the fractional part of (x+y)^2/2 is 0), but x^2 and y^2 are not (fractional parts x^2/2 and y^2/2 are equal to 1/2). Therefore, when discarding fractional parts, the result will be 1 more true. As we see, multiplication according to formula (3) is indeed inaccurate - in the case when both factors are odd. The theoretical issues have been dealt with. :-) Let's move on nowto the practical use of formula (5). In [1] I cited a procedure for multiplying two integers based on formula (2) 8-bit numbers with the constraint that the sum of the factors does not exceed 255". When a table of squares already divided by 4 is stored values, division commands must be removed from this procedure result by 4. Accordingly, we get the following: Input: D - first factor, E - second factor. Output: DE - product. Length: 22 bytes - the procedure itself + 512 bytes - the table squares. Time: 101 or 104 measures - depending on the first the factor is greater than the second or vice versa (if in advance it is known that one is always larger than the other, the procedure can be simplify). LD H,TABL_SQR/256 LD B,H LD A,D ADD A,E LD C,A ;C=x+y LD A,D SUB E JR NC,M1 N.E.G. M1 LD L,A ;L=│x-y│ LD A,(BC) SUB (HL) LD E,A INC H INC B LD A,(BC) SBC A,(HL) LD D,A ;DE=x*y RET Multiplication is now 24 clock cycles (~20%) faster compared to the original version of the procedure. Below is the text of the procedure for constructing a table of squares, divided by 4. When writing it, I took as a basis the[1] the procedure for constructing a table of squares (which, in its queue is the result of the optimization procedure given in [4]). XOR A LD H,A LD L,A LD E,A M2 LD D,TABL_SQR/256+1 EX DE,HL LD(HL),D LD A,E SRL (HL) RRA SRL (HL) RRA DEC H LD(HL),A EX DE,HL LD D,0 ADD HL,DE INC E ADD HL,DE ;The Z flag is not affected. JR NZ,M2 RET Literature ────────── 1. I. Roshchin. "More about programming arithmetic operations." "Radio amateur. Your computer" 12/2000, 1-4/2001. 2. M.A. Kartsev. "Arithmetic of Digital Machines". Moscow, publishing house "Science", 1969. 3. A.P.Domoryad. "Mathematical games and entertainment." Moscow, State Publishing House of Physics and Mathematics literature, 1961. 4. Card!nal/PGC/BD. “I want to code!” Deja Vu #5. ════════════════════════ ════════════════════════ Best regards, Ivan Roshchin.