Schnelle Multiplikation 8Bit auf 16Bit

[Dr. Irata]

Thema:
Multiplikation mittels Umformung einer Binomischen Formel und Nutzung von Quadrattabellen zur Geschwindigkeitsverbesserung!

Die Idee ist super, es geht aber noch besser... statt die 1. Binomische Formel zu nutzen nimmt man einfach die 2. Binomische Formel!
Zunächst ersetzen wir x durch b - das sieht dann mathematisch exakt aus.
Die 2. Binomische Formel lautet:
(a-b)²=a²+b²-2ab -> 2ab=a²+b²- (a-b)² -> ab=a²/2 + b²/2 - (a-b)²/2
Keine Zahl, die wir als Quadrat ablesen müssen geht nun über 16-Bit - übrigens teilen wir auch gar nicht durch 2, sondern passen die Tabelle einfach an und legen in der Tabelle nicht das Quadrat ab, sondern die Hälfte des Quadrates....

Syntax: a mal b soll ausgerechnet werden, a und b sind max. 8 Bit groß.
Zunächst wird der Betrag von a-b gebildet. Dann in der Tabelle die halben Quadrate für a, b und Betrag a-b ablesen, jeweils addieren bzw. subtrahieren... fertig.
Den Code dafür baue ich jetzt und stelle ihn hier rein...

LG
Peter

[Dr. Irata]

... aus Spaß habe ich mir auch für diesen Zweck die 3. Binomische Formel angeschaut:
(a+b)*(a-b) = a²-b² --> geht auch! Umgeformt (ich verschone euch mal mit der Rechnung) erhält man folgendes:
a*b = ((a+b)/2)²- ((a-b)/2)² --> sieht erstmal komisch aus, ist aber vielleicht noch schneller:

Addition von a und b, teilen durch 2, dann das Quadrat aus der Tabelle raussuchen.
Subtraktion b von a, teilen durch 2, dann das Quadrat aus der Tabelle raussuchen.
Beide Werte voneinander subtrahieren, das wars....
... allerdings teilt man vor dem quadrieren durch 2 und bekommt einen zu großen Rundungsfehler. Teilt man nach dem quadrieren durch 4 (was auch ginge), müsste man wieder über die 32 Bit Tabelle gehen.... a*b = (a+b)²/4 - (a-b)²/4

[Erhard]

Hallo Doc,

verstehe ich das richtig, daß man hier eine 512 Byte große Tabelle benötigt, die die .word aller Quadrate von 0 bis 255 enthält?

Dann müßten die halbierten Werte jedes mal ausgerechnet werden (LSR, ROR).

Oder ist es eine 1K Tabelle, wo noch mal die halbierten Werte drin stehen?

Wie groß ist hierbei die maximale Abweichung von einem echten Ergebnis?

Erhard

[Dr. Irata]

Guten Morgen Erhard,
ich habe das jetzt nicht ganz genau ausgerechnet, aber bleibt man bei der 2. Binomischen Formel, dann enthält die Tabelle alle schon halbierten Quadratergebnisse der 256 Zahlen. Man braucht dann tatsächlich 256 Bytes für den Low-Wert und nochmal 256 Bytes für den High-Wert, also ein halbe kB. Mit schlauer Codierung kommt man sicherlich auch deutlich unter 512 Bytes, das würde aber wieder etwas Zeit kosten...
LG
Peter

[Dr. Irata]

... und hier der Code:
Insgesamt wohl noch schneller. Alle diese schnelle Varianten haben neben des etwas erhöhten Speicherbedarfes einen weiteren Nachteil: Man teilt die Quadrate ja durch 2 und bekommt somit automatisch kleinere Rundungsfehler!

Code: Alles auswählen

a			.by 00		
b			.by 00		
c			.by 00,00		

temp1		.by 00,00		;Zwischenspeicher1
temp2		.by 00,00		;Zwischenspeicher2
 	
			;.... schnelle 8Bit auf 16 Bit-Multiplikation ......
			; die 2. Binomische Formel lautet:
			; (a-b)²=a²+b²-2a*b -> 2*a*b=a²+b²-(a-b)² 
			; -> a*b=a²/2+b²/2-(a-b)²/2 = c
			
			; Eingabe als Beispiel für a und b: 11 * 123 = 1353

			lda #11
			sta a
			lda #123
			sta b
			
			; Start Routine für a * b = c
			; Betrag von a-b bilden
			sec
			lda a
			sbc b
			bcs weiter
			sbc #0
			eor #$ff
weiter
			; ab hier die Quadrate/2 holen und entsprechend die Summanden bilden
			tax		
			lda quadratlow,x
			sta temp1
			lda quadrathi,x
			sta temp1+1
			clc
			ldx a
			lda quadratlow,x
			ldx b
			adc quadratlow,x
			sta temp2
			lda quadrathi,x
			ldx a
			adc quadrathi,x
			sec
			sbc temp1+1
			sta c+1
			lda temp2
			sbc temp1
			sta c
			
			;....................... Routine Ende ..........
	
				
quadratlow
 	 .byte   0,  1,  2,  5,  8, 13, 18, 25, 32, 41, 50, 61, 72, 85, 98,113
  	.byte 128,145,162,181,200,221,242,  9, 32, 57, 82,109,136,165,194,225
 	 .byte   0, 33, 66,101,136,173,210,249, 32, 73,114,157,200,245, 34, 81
	  .byte 128,177,226, 21, 72,125,178,233, 32, 89,146,205,  8, 69,130,193
 	 .byte   0, 65,130,197,  8, 77,146,217, 32,105,178,253, 72,149,226, 49
  .byte 128,209, 34,117,200, 29,114,201, 32,121,210, 45,136,229, 66,161
  .byte   0, 97,194, 37,136,237, 82,185, 32,137,242, 93,200, 53,162, 17
  .byte 128,241, 98,213, 72,189, 50,169, 32,153, 18,141,  8,133,  2,129
  .byte   0,129,  2,133,  8,141, 18,153, 32,169, 50,189, 72,213, 98,241
  .byte 128, 17,162, 53,200, 93,242,137, 32,185, 82,237,136, 37,194, 97
  .byte   0,161, 66,229,136, 45,210,121, 32,201,114, 29,200,117, 34,209
  .byte 128, 49,226,149, 72,253,178,105, 32,217,146, 77,  8,197,130, 65
  .byte   0,193,130, 69,  8,205,146, 89, 32,233,178,125, 72, 21,226,177
  .byte 128, 81, 34,245,200,157,114, 73, 32,249,210,173,136,101, 66, 33
  .byte   0,225,194,165,136,109, 82, 57, 32,  9,242,221,200,181,162,145
  .byte 128,113, 98, 85, 72, 61, 50, 41, 32, 25, 18, 13,  8,  5,  2,  1

quadrathi
  .byte   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
  .byte   0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1
  .byte   2,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  4,  4
  .byte   4,  4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7
  .byte   8,  8,  8,  8,  9,  9,  9,  9, 10, 10, 10, 10, 11, 11, 11, 12
  .byte  12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17
  .byte  18, 18, 18, 19, 19, 19, 20, 20, 21, 21, 21, 22, 22, 23, 23, 24
  .byte  24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31
  .byte  32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39
  .byte  40, 41, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49
  .byte  50, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 57, 57, 58, 59, 59
  .byte  60, 61, 61, 62, 63, 63, 64, 65, 66, 66, 67, 68, 69, 69, 70, 71
  .byte  72, 72, 73, 74, 75, 75, 76, 77, 78, 78, 79, 80, 81, 82, 82, 83
  .byte  84, 85, 86, 86, 87, 88, 89, 90, 91, 91, 92, 93, 94, 95, 96, 97
  .byte  98, 98, 99,100,101,102,103,104,105,106,106,107,108,109,110,111
  .byte 112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127

[DjayBee]

Nachteil: Man teilt die Quadrate ja durch 2 und bekommt somit automatisch kleinere Rundungsfehler!

Falls du die Genauigkeit brauchst und 10-12 Taktzyklen übrig hast, kannst du die Tabellen auch mit den vollen Quadraten bauen und am Ende das Ergebnis halbieren.

Code: Alles auswählen

lsr c+1
ror c

[Dr. Irata]

... also tatsächlich habe ich auch schon daran gedacht. Die Genauigkeit ist dann etwas besser und es noch weitere Vorteile: Durch eine normalisierte Tabelle, würde man ganz praktisch auch Wurzeln ziehen können...

[JAC!]

Codebase64 ist für sowas immer eine gute Quelle:

https://codebase64.org/doku.php?id=base ... d_division