KSP Aufgabe 6

1. In dieser Version der VM wollen wir als Rechenobjekte beliebig grosse ganze Zahlen zulassen. Diese neuen Rechenobjekte ersetzen die alten 32-Bit-Zahlen und haben ihren Speicherplatz ebenfalls auf dem Heap. Auf dem Stack, in der Static Data Area und im Rueckgabewertregister stehen wie gehabt Zeiger auf die Rechenobjekte.

2. Die Algorithmen zum Rechnen mit beliebig grossen ganzen Zahlen ("Multiple Precision Arithmetic") sind entnommen aus [D. Knuth: The Art of Computer Programming, Vol. 2, Seminumerical Algorithms]. Eine Implementierung in C finden Sie hier . Entpacken Sie das Paket und studieren Sie die darin enthaltene Datei README . Bauen Sie das Paket und lassen Sie die Tests laufen! Machen Sie sich mit der Struktur der Zahlendarstellung vertraut! Hinweise: Jede Ziffer der Zahl ist ein Byte, d.h. die Zahldarstellung benutzt die Basis 256. Die Ziffern werden in einem genuegend grossen Array gespeichert, das zusammen mit der Groessenangabe in einer Struktur ("Objekt") auf dem Heap steht.

3. Die Multiple Precision Arithmetic braucht eine winzige Support-Bibliothek, deren Funktionalitaet aber in Ihrer VM schon enthalten ist. Stellen Sie die benoetigten Funktionen aus Ihrer VM zur Verfuegung!

4. Studieren Sie das Benutzer-Programmierinterface und passen Sie Ihre VM an. Achten Sie darauf, ALLE Operationen mit Rechenobjekten der Bibliothek zu ueberlassen; dazu gehoeren auch die Vergleiche!

5. Der Instruktionssatz ist gegenueber Aufgabe 5 unveraendert; auch der Compiler und der Assembler bleiben exakt gleich (bis auf die Versionsnummern).

6. Hier wie immer die Referenzimplementierung:
njvm

Aufgaben fuer Tests

a) Schreiben Sie ein kleines Ninja-Programm zur Berechnung von 100! = 1*2*3*..*100. Faellt Ihnen am Ergebnis etwas auf? Kann das denn ueberhaupt richtig sein?

b) Die Fibonacci-Folge ist definiert als F(0) = 0, F(1) = 1, und F(n) = F(n-1) + F(n-2) fuer alle n > 1. Schreiben Sie ein kleines Ninja-Programm zur Berechnung von F(100). Hinweis: Nur die iterative Version wird in annehmbarer Zeit zum Ergebnis fuehren!

c) Schreiben Sie ein kleines Ninja-Programm zur Berechnung der Summe aller Brueche 1/i fuer i = 1..100 (die einhundertste "harmonische Zahl"). Das Ergebnis soll als exakter Bruch in gekuerzter Darstellung angegeben werden. Hinweise: Halten Sie den Zaehler und den Nenner des Ergebnisses in zwei verschiedenen Variablen. Wenn Sie einen neuen Term addieren wollen, muessen Sie die Brueche auf einen gemeinsamen Nenner bringen. Beim Kuerzen (das Sie entweder bei jeder Rechnung oder aber einmal ganz am Ende aller Rechnungen durchfuehren koennen) leistet der groesste gemeinsame Teiler gute Dienste! Koennen Sie die Zahl in Dezimalschreibweise mit z.B. 10 Stellen nach dem Komma ausgeben? Dazu sind nur Ganzzahloperationen noetig!