Programming:Integer Multiplication - Revision history

Prodatron: /* Fast 8bit * 8bit Unsigned with only 512 bytes of tables */ added improved version by calc84maniac

2025-03-06T12:13:06Z

‎Fast 8bit * 8bit Unsigned with only 512 bytes of tables: added improved version by calc84maniac

Roudoudou: /* 16bit * 16bit Unsigned -> 32 bits result */ forgotten label

2018-03-01T17:31:55Z

‎16bit * 16bit Unsigned -> 32 bits result: forgotten label

Roudoudou: optimised 16x16=32

2018-03-01T17:30:37Z

optimised 16x16=32

Litwr: /* Fast 8bit * 8bit Unsigned with only 512 bytes of tables */

2015-10-24T07:47:31Z

‎Fast 8bit * 8bit Unsigned with only 512 bytes of tables

Litwr: /* Fast 8bit * 8bit Unsigned with only 512 bytes of tables */

2015-10-24T07:41:18Z

‎Fast 8bit * 8bit Unsigned with only 512 bytes of tables

Litwr: /* Very fast 8bit * 8bit Unsigned with only 1K of tables */

2015-10-24T07:39:52Z

‎Very fast 8bit * 8bit Unsigned with only 1K of tables

Litwr: /* Fast 8bit * 8bit Unsigned with only 512 bytes of tables */

2015-10-24T07:36:59Z

‎Fast 8bit * 8bit Unsigned with only 512 bytes of tables

Litwr: /* Very fast 8bit * 8bit Unsigned with only 512 bytes of tables */

2015-10-24T07:33:26Z

‎Very fast 8bit * 8bit Unsigned with only 512 bytes of tables

Litwr: /* Very fast 8bit * 8bit Unsigned with only 1K of tables */

2015-10-24T07:32:38Z

‎Very fast 8bit * 8bit Unsigned with only 1K of tables

Litwr: a new fast multiplication routine added

2015-10-24T07:29:58Z

a new fast multiplication routine added

← Older revision		Revision as of 12:13, 6 March 2025
Line 622:		Line 622:

	[[User:Litwr\|Litwr]] 10:25, 24 October 2015 (CEST)		[[User:Litwr\|Litwr]] 10:25, 24 October 2015 (CEST)
		+
		+
		+
		+	== Fast 8bit * 8bit Unsigned with only 512 bytes of tables (improved version) ==
		+
		+	'''Input''': A = Multiplier, L = Multiplicant
		+
		+	'''Output:''' DE = ''Product''
		+
		+	'''CPC Cycles''': 124 = 31 usec
		+
		+	'''Size''': 27 bytes of code and 512 bytes for the tables
		+
		+	'''by calc84maniac'''
		+
		+	Hey, so someone brought up the wiki's 512-byte table routine in the context of Game Boy development, and I thought I'd take a crack at seeing if the speed and size could be made closer to the 1KB table routine. I actually had a good bit of success, by making the following observations:<br>
		+	* The x >= y constraint isn't necessary if negative values for floor((x - y) / 2) have their square calculated properly, so no need to swap inputs.<br>
		+	* Going from floor((x + y) / 2) to floor((x - y) / 2) simply requires a subtraction of y, so no need to divide by 2 twice or save the input value of x.<br>
		+	* To square a negative number z, it's sufficient to calculate z ^ 2 = (z + 256) ^ 2 - z * 512 - 65536, meaning a conditional offset of -(z * 512) in the subtracted square, or z * 512 in the final result.<br>
		+	* When conditionally adding y to the result when x + y is odd, the carry can be propagated into the low bit of the 8-bit register holding the upper half of z * 512.<br>
		+	* Both of these conditional adds can be turned into branchless adds of either the value or zero.<br>
		+	<br>
		+	This results in the following implementation (which I adjusted to take the same inputs and outputs as the 1KB routine for a fair comparison), which comes out to 27 bytes and a constant 31 usec:<br>
		+
		+	<pre>
		+	; Input: A = x, L = y
		+	; Output: DE = x * y
		+	; C = floor((x + y) / 2)
		+	add a,l ; 1
		+	rra ; 2
		+	ld c,a ; 3
		+	; E = y if x + y is odd, else 0
		+	sbc a,a ; 4
		+	and l ; 5
		+	ld e,a ; 6
		+	; L = floor((x - y) / 2)
		+	ld a,c ; 7
		+	sub l ; 8
		+	ld l,a ; 9
		+	; D = L if negative, else 0
		+	sbc a,a ; 10
		+	and l ; 11
		+	ld d,a ; 12
		+	; Calculate low half of product
		+	ld h,high(sqrlo) ; 14
		+	ld b,h ; 15
		+	ld a,(bc) ; 17
		+	add a,e ; 18
		+	rl d ; 20, multiplies D by 2 and propagates carry
		+	sub (hl) ; 22
		+	ld e,a ; 23
		+	; Calculate high half of product
		+	inc h ; 24, loads high(sqrhi)
		+	ld b,h ; 25
		+	ld a,(bc) ; 27
		+	sbc a,(hl) ; 29
		+	add a,d ; 30
		+	ld d,a ; 31
		+	</pre>

	== 16bit * 16bit Unsigned -> 32 bits result ==		== 16bit * 16bit Unsigned -> 32 bits result ==

@@ Line 638: / Line 638: @@
    jr nc,muluw_cont
     inc de
   dec a
   jr nz,muluw

@@ Line 623: / Line 623: @@
 [[User:Litwr|Litwr]] 10:25, 24 October 2015 (CEST)
-== 16bit * 16bit Unsigned ==
+== 16bit * 16bit Unsigned -> 32 bits result ==
 '''Input:''' BC = ''Multiplier'', DE = ''Multiplicand''

@@ Line 536: / Line 536: @@
 Fast 8 bit unsigned multiplication with 16 bit result. It uses formula
-<pre>
+<br>x*y = ((x+y)/2)<sup>2</sup> - ((x-y)/2)<sup>2</sup>, if x+y is even
-  x*y = ((x+y)/2)<sup>2</sup> - ((x-y)/2)<sup>2</sup>, if x+y is even
+<br>      = ((x+y-1)/2)<sup>2</sup> - ((x-y-1)/2)<sup>2</sup> + y, if x+y is odd and x>=y
-      = ((x+y-1)/2)<sup>2</sup> - ((x-y-1)/2)<sup>2</sup> + y, if x+y is odd and x>=y
-</pre>
 <pre>    cp b

@@ Line 537: / Line 537: @@
 Fast 8 bit unsigned multiplication with 16 bit result. It uses formula
 <pre>
-   x*y = ((x+y)/2)^2 - ((x-y)/2)^2, if x+y is even
+   x*y = ((x+y)/2)<sup>2</sup> - ((x-y)/2)<sup>2</sup>, if x+y is even
-       = ((x+y-1)/2)^2 - ((x-y-1)/2)^2 + y, if x+y is odd and x>=y
+       = ((x+y-1)/2)<sup>2</sup> - ((x-y-1)/2)<sup>2</sup> + y, if x+y is odd and x>=y
 </pre>

@@ Line 443: / Line 443: @@
 == Very fast 8bit * 8bit Unsigned with only 1K of tables ==
-'''Input''': B = Multiplier, C = Multiplicant
+'''Input:''' A = ''Multiplier'', L = ''Multiplicand''
-'''Output''': DE = Product
+'''Output:''' DE = ''Product''
 '''CPC Cycles''': 104-112 (108 on average) = 26-28 (27) usec
@@ Line 496: / Line 496: @@
 Now for the actual multiply routine:
 <pre>
 	ld h,umul_tab_lo / #100	; 2

@@ Line 534: / Line 534: @@
 '''Output''': A:E = Product
-'''CPC Cycles''': 136-172 (154 on average) = 26-28 (27) usec
+'''CPC Cycles''': 136-172 (154 on average) = 34-43 (38.5) usec
 '''Size''': 44 bytes of code and 512 bytes for the tables

@@ Line 528: / Line 528: @@
 [[User:Executioner|Executioner]] 06:25, 4 April 2008 (CEST)
-== Very fast 8bit * 8bit Unsigned with only 512 bytes of tables ==
+== Fast 8bit * 8bit Unsigned with only 512 bytes of tables ==
 '''Input''': A = Multiplier, B = Multiplicant

← Older revision		Revision as of 07:32, 24 October 2015
Line 528:		Line 528:
	[[User:Executioner\|Executioner]] 06:25, 4 April 2008 (CEST)		[[User:Executioner\|Executioner]] 06:25, 4 April 2008 (CEST)

		+	== Very fast 8bit * 8bit Unsigned with only 512 bytes of tables ==
		+
		+	'''Input''': A = Multiplier, B = Multiplicant

	'''Output''': A:E = Product		'''Output''': A:E = Product

@@ Line 175: / Line 175: @@
 </pre>
-== Faster, accurate 8bit * 8bit Unsigned ==
+== Fastest, accurate 8bit * 8bit Unsigned  with 16 KB tables ==
 '''Input:''' L = Multiplier, C = Multiplicand
@@ Line 294: / Line 294: @@
 </pre>
-K is a lot of memory to use for tables, but I'm working on a way to reduce this to 8K while maintaining similar performance (around 26&mu;s). The idea is rather than using tables for the low and high nibbles, use tables for alternate bits. So there would be 16 tables for the values #00, #01, #04, #05, #10, #11, #14, #15, #40, #41, #44, #45, #50, #51, #54, #55. The values can be shifted by 1 (rather than 4) to give values for the alternate bits using a simple ADD HL,HL.
+== Fast, accurate 8bit * 8bit Unsigned  with 8 KB tables ==
-This routine should be easy to adapt to a 16bit * 8bit unsigned multiplication or even a 16bit * 16bit, using simple additions.
+'''Input:''' L = Multiplier, C = Multiplicand
-[[User:Executioner|Executioner]] 03:58, 8 May 2007 (CEST)
+'''Output:''' DE = Product
 '''CPC Cycles:''' 100 = 25 usec
 '''Size:''' 19 bytes of code + 8 KB tables
 Ok, here is the new 8K routine, first the routine to build the tables:
@@ Line 441: / Line 447: @@
 '''Output''': DE = Product
-'''CPC Cycles''': 104-112 (108 on average) = 26-28 (27)
+'''CPC Cycles''': 104-112 (108 on average) = 26-28 (27) usec
 '''Size''': 24 bytes of code and 1024 bytes for the tables
@@ Line 521: / Line 527: @@
 [[User:Executioner|Executioner]] 06:25, 4 April 2008 (CEST)
 == 16bit * 16bit Unsigned ==