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

← 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 ==

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

2018-03-01T17:31:55Z

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

← Older revision		Revision as of 17:31, 1 March 2018
Line 638:		Line 638:
	jr nc,muluw_cont		jr nc,muluw_cont
	inc de		inc de
			muluw_cont
	dec a		dec a
	jr nz,muluw		jr nz,muluw

Roudoudou: optimised 16x16=32

2018-03-01T17:30:37Z

optimised 16x16=32

@@ 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''

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

← Older revision		Revision as of 07:47, 24 October 2015
Line 536:		Line 536:

	Fast 8 bit unsigned multiplication with 16 bit result. It uses formula		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		<pre> cp b

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

← Older revision		Revision as of 07:41, 24 October 2015
Line 537:		Line 537:
	Fast 8 bit unsigned multiplication with 16 bit result. It uses formula		Fast 8 bit unsigned multiplication with 16 bit result. It uses formula
	<pre>		<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>		</pre>

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

← Older revision		Revision as of 07:39, 24 October 2015
Line 443:		Line 443:
	== Very fast 8bit * 8bit Unsigned with only 1K of tables ==		== 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		'''CPC Cycles''': 104-112 (108 on average) = 26-28 (27) usec
Line 496:		Line 496:
	Now for the actual multiply routine:		Now for the actual multiply routine:

	~~'''Input:''' A = ''Multiplier'', L = ''Multiplicand''~~

	~~'''Output:''' DE = ''Product''~~
	<pre>		<pre>
	ld h,umul_tab_lo / #100 ; 2		ld h,umul_tab_lo / #100 ; 2

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

← Older revision		Revision as of 07:36, 24 October 2015
Line 534:		Line 534:
	'''Output''': A:E = Product		'''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		'''Size''': 44 bytes of code and 512 bytes for the 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

← Older revision		Revision as of 07:33, 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 ==		== Fast 8bit * 8bit Unsigned with only 512 bytes of tables ==

	'''Input''': A = Multiplier, B = Multiplicant		'''Input''': A = Multiplier, B = Multiplicant

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

← 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

Litwr: a new fast multiplication routine added

2015-10-24T07:29:58Z

a new fast multiplication routine added

@@ 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 ==