Routinensammlung und Gewusst-wie für Mikrocontroller

Wurzel ziehen bei Mikrocontrollern

Betrachtet wird hier nur das Radizieren ganzer Zahlen.

Eine schnelle Quadratwurzel wird recht oft benötigt:

Grundlagen

Beim Berechnen der Quadratwurzel gilt folgende Regel der Bitbreiten:

sqrt(Radikand) = Wurzel
sqrt(2n bit) = n bit

Bei Kubikwurzeln hat der Radikand entsprechend 3n bit usw.

Folgende Lösungsmöglichkeiten sind üblich und gängig:

VerfahrenSchleifen-DurchläufeVor- und Nachteile
Summe der ungeraden Zahlen= Wurzelwertlangsam; schnell bei kleinen Ergebnissen
Tabellenzugriff= log2 nsehr schnell; braucht viel ROM/RAM/Flash
Wie schriftlich= nschnell und sparsam

Merke: Alle diese Verfahren runden standardmäßig ab.

Hinweis: Keines dieser Verfahren benötigt die Multiplikation und ist deshalb auch auf weniger leistungsstarken Mikrocontrollern verwendbar.

Summe der ungeraden Zahlen

Es wird ganz einfach folgende Formel verwendet (rechts für Kubikwurzeln):

n-1
n² = Σ 2 i + 1
i = 0
n-1
n³ = Σ 6 i + 1
i = 0

Also werden einfach ungerade Zahlen so lange aufaddiert, bis der Radikand überschritten wird. Danach die letzte ungerade Zahl halbieren (rechtsschieben) und dekrementieren, und der Wurzelwert ist fertig.

Eine Tabelle soll jedoch noch einmal die Langsamkeit dieser Routine verdeutlichen:

RadikandErgebnisSchleifen-DurchläufeBewertung
8 bit4 bit15 max.sehr gut
16 bit8 bit255 max.gut
24 bit12 bit4095 max.langsam
32 bit16 bit65535 max.inakzeptabel

Tabellenzugriff

Der Tabellenzugriff mit binärer Suche ist für alle streng monotonen Funktionen verwendbar, so auch für eine Quadratwurzel. Die erforderliche Tabellengröße, die für jeden Index das Quadrat enthält, ergibt sich aus:

2n * 2n/8 Bytes

und damit beispielhaft:

RadikandErgebnis = Schleifen-DurchläufeTabellengröße (Bytes)Bewertung
8 bit4 bit16 * 1 = 16lohnt sich nicht
16 bit8 bit256 * 2 = 512gut
24 bit12 bit4096 * 3 = 12288 (12K)Wer den Platz hat, ist gut dran
32 bit16 bit65536 * 4 = 262144 (256K)Platzverschwendung!

Zum Drücken des Tabellen-Speicherbedarfs sind natürlich auch "krumme" Bitbreiten ins Kalkül zu ziehen! Wenn bspw. für eine 3½-stellige Anzeige ein 10-bit-Effektivwert reicht, reduziert sich die 24-bit-Wurzeltabelle auf erträgliche 3 KByte.

Aber - für popelige Anzeigen gibt es ein besseres Verfahren, s.u.

QuadTab:	;!UNGETESTET!
.set i = 0
	.rept 256

	.dw	i*i
.set i = i+1
.endm

;Löwenfangmethode: Wüste halbieren...
	ldiw	zh,zl,(QuadTab+128)*2	;Zeiger auf ersten Testwert (Tabellen-Mitte)
	ldi	r16,128			;Distanz (zum nächsten Testwert)
halbieren:		;8 Runden
	lpm	r0,z+
	lpm	r1,z
	dec	zl

	cp	r0,r3
	cpc	r1,r4
	
	brcc	h1

	sub	zl,r16
	subi	zh,0
	rjmp	h2
h1:
	add	zl,r16
	adci	zh,0
h2:
	srl	r16			;Distanz halbieren
	brne	halbieren		;Distanz=0 wenn fertig
	srl	zh
	ror	zl		;Wortadresse
	subi	zl,LOW(QuadTab)	;jetzt steht in ZL der ganzzahlige WurzelWert
				;und in R1:R0 (immer noch) das Quadrat dazu
	or	r16,zl

Lösung wie schriftlich, aber binär

Es geht viel einfacher, wirklich, und das mit akzeptablem Rechenaufwand. Nur wenig langsamer als die binäre Suche in einer Quadrate-Tabelle.

Die folgende Routine für AT90, ATmega8 ist für 24-bit-Radikand und getestet. Sie ist sogar schneller als der A/D-Wandler:-)

AktionBemerkung
Setze Akku (24bit), Wurzel (Ergebnis) sowie Quadrat (Hilfsspeicher) auf Null
12x ausführen Wurzel linksschieben (verdoppeln)kann beim ersten Mal entfallen
Quadrat 2x linksschieben (vervierfachen)
Schiebe zwei Bit in Akku (linksschieben), beginnend mit MSB des Radikanden
Hilfsquadrat = Quadrat + 2*Wurzel + 1zunächst 1
WENNAkku >= Hilfsquadrat
DANNQuadrat = Hilfsquadrat
Wurzel++
SONSTnichts tun

Diese grundlegende Funktion wurde verändert, um das Hilfsquadrat abzuschaffen (Veränderungen fett):

AktionBemerkung
Setze Akku (24bit), Wurzel (Ergebnis) sowie Quadrat (Hilfsspeicher) auf Null
12x ausführen Wurzel linksschieben (verdoppeln)kann beim ersten Mal entfallen
Quadrat 2x linksschieben (vervierfachen)
Schiebe zwei Bit in Akku (linksschieben), beginnend mit MSB des Radikanden
Quadrat += 2*Wurzel + 1zunächst 1
WENNAkku >= Quadrat
DANNWurzel++
SONSTQuadrat -= 2*Wurzel + 1

Die nächste Veränderung betrifft die Verwendung einer "ungeraden Doppelwurzel", um die ständige Bildung von 2*Wurzel + 1 zu vermeiden:

AktionBemerkung
Setze Akku (24bit) sowie Quadrat auf Null, Doppelwurzel auf 1
12x ausführen Doppelwurzel geeignet linksschieben: xxxx1 => xxxx01kann beim ersten Mal entfallen
Quadrat 2x linksschieben (vervierfachen)
Schiebe zwei Bit in Akku (linksschieben), beginnend mit MSB des Radikanden
Quadrat += Doppelwurzelzunächst 1
WENNAkku >= Quadrat
DANNDoppelwurzel += 2das Null-Bit auf Eins setzen
SONSTQuadrat -= Doppelwurzel
Doppelwurzel 1x rechtsschiebenWurzelwert fertig

Als nächstes die Reduktion der Bitbreiten für Akku und Abschaffung von Quadrat, im Akku steht anschließend der Wurzel-Rest:

AktionBemerkung
Setze Akku (16bit) auf Null, Doppelwurzel auf 1
12x ausführen Doppelwurzel geeignet linksschieben: xxxx1 => xxxx01kann beim ersten Mal entfallen
Schiebe zwei Bit in Akku (linksschieben), beginnend mit MSB des Radikandensetzt ggf. C
WENNAkku >= Doppelwurzeloder C = 1 (vorher)
DANNAkku -= Doppelwurzel
Doppelwurzel += 2Null-Bit auf Eins
SONSTnichts tun
Doppelwurzel 1x rechtsschiebenWurzelwert fertig
Rest im Akku

Ich Idiot, warum eigentlich nicht gleich so?

Man beachte für 8- oder 16-bit-Ergebnisse, dass die Doppelwurzel ein Bit mehr erfordert. Der Akku braucht sogar zwei Bit mehr, dies kann mit dem Übertragsflag abgefangen werden!
Daher ist diese Routine für genau 8 oder 16 bit Ergebnisbreite aufzublasen.

.def RL = r2	;Radikand (24 bit), Datenquelle
.def RM = r3
.def RH = r4
.def AL = r12	;Akku (14 bit), Rest (13bit) am Ende
.def AH = r13
.def WL = r18	;Ungerade Doppelwurzel (13bit), Wurzel (12bit) am Ende
.def WH = r19
.def LoopCounter = r17	;Schleifenzähler

;ca. 280 Takte (17,5 µs @ 16 MHz)
Wurzel:
;Doppelwurzel = 0 (LSB wird sowieso gesetzt)
	clr	WL
	clr	WH
;Akku löschen
	clr	AL
	clr	AH

	ldi	LoopCounter,12	;Für jedes Ergebnis-Bit eine Runde
zieh:
;Doppelwurzel "verdoppeln"
	sec
	rol	WL	;[xxxxx1 -> xxxxx01]
	rol	WH
	cbr	WL,2
;Zwei Bits aus Radikand in Akku schieben
	lsl	RL
	rol	RM
	rol	RH
	rol	AL
	rol	AH
	lsl	RL
	rol	RM
	rol	RH
	rol	AL
	rol	AH
;	brcs	setbit	;auskommentieren für 22/30-bit-Radikand
;Akku mit Doppelwurzel vergleichen
	cp	AL,WL
	cpc	AH,WH
	brcs	okay
setbit:
;Doppelwurzel vom Akku abziehen
	sub	AL,WL
	sbc	AH,WH
;Doppelwurzel+=2
	sbr	WL,2	;[xxxxx01 -> xxxxx11]
okay:
;nächste Runde
	dec	LoopCounter
	brne	zieh
;Doppelwurzel halbieren
	lsr	WH
	ror	WL
;fertig
	ret
Z80-Version (Mann, ist der lahm!):
;PE: BC:IY = Radikand 30 bit
;PA: DE = Wurzel 15 bit
;    HL = Rest 16 bit
;VR: IY=BC=A=0, HL, DE
;Ta: ca. 3300 (1,9 ms @ 1,75 MHz)
Wurzel:
;Doppelwurzel = 0 (LSB wird sowieso gesetzt)
	xor	a	;(4)
	ld	e,a	;(4)
	ld	d,a	;(4)
;Akku löschen
	ld	l,a	;(4)
	ld	h,a	;(4)
	ld	a,16	;(7)
zieh:
;Doppelwurzel "verdoppeln"
	scf		;(4)
	rl	e	;(8) [xxxxx1 -> xxxxx01]
	rl	d	;(8)
	res	e,1	;(8)
;Zwei Bits aus Radikand in Akku schieben
	add	iy,iy	;(15)
	rl	c	;(8)
	rl	b	;(8)
	adc	hl,hl	;(15)
	add	iy,iy	;(15)
	rl	c	;(8)
	rl	b	;(8)
	adc	hl,hl	;(15)
	jc	setbit	;(12/7)
;Akku mit Doppelwurzel vergleichen
	sbc	hl,de	;(15)
	add	hl,de	;(11)
	jc	okay	;(12/7)
setbit:
;Doppelwurzel vom Akku abziehen
	or	a	;(4)
	sbc	hl,de	;(15)
;Doppelwurzel += 2
	set	e,1	;(8) [xxxxx01 -> xxxxx11]
okay:
;nächste Runde
	dec	a	;(4)
	jnz	zieh	;(12/7) => (203) *16 = (3248)
;Doppelwurzel halbieren
	srl	h	;(8)
	rr	l	;(8)
;fertig
	ret		;(10)

Mischtechnologien

Es ist bspw. bei 24-bit-Input auch möglich, eine gemischte Technologie aus Tabellenzugriff und ungerade-Zahlen-Methode anzuwenden.

Wegen der Effektivität der „schriftlichen“ Routine ist diese Möglichkeit ins Hintertreffen geraten.

;Deshalb hier eine Mischtechnologie für den 24-bit-Input:
;* Das QH wird genommen und die Wurzel bestimmt (0..15)
;* Ausgehend vom Quadrat der Wurzel * 256 sowie der Wurzel * 16
;  wird die Wurzel aus QH:QM bestimmt, das sind wieviel Iterationen max.??
;Beispiel:
;  FF² = FE01
;  sqrt(FE) = F (Wurzel aus High-Byte ziehen)
;  F²  = E1 (Nebenprodukt des Wurzelziehens)
;  F0² = E100 (zusammensetzen, weil 16² = 256)
;  F1² = E2E1 (addiere 2E1 = 2*F0+1)
;  das Beispiel zeigt: max. 16 weitere Iterationen, allerdings 16-bit-Strichrechnung
;Weiter geht's dann genauso mit 24-bit-Strichrechnung

Andere Quellen

Gesehen habe ich eine Modifikation der Methode der ungeraden Zahlen mit folgenden Verbesserungen: