Fibonacci Zahlen auf dem AT&T WE 32100
======================================


I/ Einfache Loesung
-------------------

Idee: Ausnutzen der speziellen Struktur der Fibonaccizahlen-
berechnung:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

Also, jedesmahl wenn wir in den entfalteten Prozeduraufrufen
auf einen Aufruf "fib(1)" stossen, muessen wir einen Zaehler um
eins erhoehen. Nach Beendung der Aufruf von "fib(n)" enthaelt
dieser Zaehler dann den gewuenschten Wert.

Diese Loesung ist einfach, aber hat als Nachteil dass globale
Variablen (der Zaehler) benutzt wird.

In Assembler:


fib:	save %fp		# das sichern kann man sogar weglassen
if:	tst (%ap)		# n=0?
then: 	bneb elseif
	brb done

elseif:	cmp &1, (%ap)		# n=1?
	bneb else
then:	addw2 &1, r0		# add 1 to r0
	brb done

else:				# wir wissen: n >= 2!
	subw3 (%ap), &1, r1	# setze r1 := n-1; (%ap) ergibt n
	push %r1		# "push n-1"
	call -4(%sp), fib	# berechne fib(n-1)
				
ret1:	subw3 (%ap), &2, r1	# setze r1 := n-2; (%ap) ergibt n
	push %r1		# "push %r1"
	call -4(%sp), fib	# berechne fib(n-2)

ret2:
done:	restore %fp		# kann mann sogar weglassen
	ret			# return to Aufrufer



Der Aufruf soll dann folgendermassen aussehen:

aufruf:	movw2 &0, r0		# r0 := 0
	push r4			# push r4; annahme: n steht in r4 bereit
	call -4(%sp), fib	# berechne fib(n)

cont:	....			# ergebnis fib(n) in r0



II/ Bessere Loesung
-------------------

Eine schoenere Loesung benuztzt keine globale Variablen (wie r0
oben), sondern reserviert expliziet bei Aufrug von fib(n) eine
Stapelzelle (4 Byte) fuer das Ergebnis. Die freie Zelle wird gerade
*unter* der Parameter fuer den Aufrug reserviert. Bei "ret" wird
diese Zelle also nicht geloescht!  Falls wir Aufrufe fuer fib(n-1) und
fib(n-2)gemacht haben, stehen die berechnete Werte gerade ueber einander
auf dem Stapel. Die beide werte koennen dann addiert werden, und liefern
somit das Ergebnis. Beide Zwischenergebnisse muessen dann natuerlich
noch vom Stapel geloescht werden.

Also, in Assembler:

fib:	save %fp		# das sichern kann man sogar weglassen
if:	tst (%ap)		# n=0?
then: 	bneb elseif
	movw2 &0, -4(%ap)	# schreibe 0 als Ergebnis in -4(%ap)
	brb done

elseif:	cmp &1, (%ap)		# n=1?
	bneb else
then:	movw2 &1, -4(%ap)	# schreibe 1 als Ergebnis in -4(%ap)
	brb done

else:				# wir wissen: n >= 2!
	subw3 (%ap), &1, r5	# setze r5 := n-1; (%ap) ergibt n
	push &0			# reserviere Stapelplatz fuer Ergebnis
	push %r5		# "push n-1"
	call -4(%sp), fib	# berechne fib(n-1); Ergebnis in -4(%ap)
				
ret1:	subw3 (%ap), &2, r5	# setze r5 := n-2; (%ap) ergibt n
	push &0			# reserviere Stapelplatz fuer Ergebnis
	push %r5		# "push n-2"
	call -4(%sp), fib	# berechne fib(n-2); Ergebnis in -4(%ap)

ret2:	addw3 -8(%sp), -4(%sp), -4(%ap)
				# fib(n) := fib(n-1) + fib(n-2)
				# fib(n-1) steht an stelle -8(%sp)
				# fib(n-2) steht an stelle -4(%sp)
				# das Ergebnis soll an Stelle -4(%ap)
				# gesichert werden

	pop dummy		# loeschen von benutzten ergebnisse
	pop dummy
done:	restore %fp		# kann mann sogar weglassen
	ret			# return to Aufrufer


Der Aufruf soll dann folgendermassen aussehen:

aufruf:	push &0			# Resultatzelle auf dem Stack reservieren
	push r4			# push r4; annahme: n steht in r4 bereit
	call -4(%sp), fib	# berechne fib(n)

cont:	....			# ergebnis fib(n) in -4(%sp)
