Ich wollte wissen, wie die BigInt und andere solche Sachen umgesetzt werden. Ich habe versucht, den Quellcode von JAVA auszuchecken, aber es war alles Griechisch und Lateinisch für mich. Kannst du mir bitte den Algo in Worten erklären - kein Code, so dass ich verstehe, was ich eigentlich benutze, wenn ich etwas aus der JAVA-API verwende. grüßeWie funktionieren BigNums-Implementierungen?
Konzeptionell genauso wie Sie willkürliche Größe aritmentic von Hand. Sie haben so etwas wie ein Array von Werten und Algorithmen für die verschiedenen Operationen, die an dem Array arbeiten.
Angenommen, Sie möchten 100 zu 901 hinzufügen. Sie beginnen mit den beiden Zahlen als Arrays:
[0, 1, 0, 0]
[0, 9, 0, 1]
Wenn Sie hinzufügen, beginnt Ihr zusätzlich Algorithmus von rechts, nimmt 0+1, 1 geben, 0+0, 0 geben, und - jetzt kommt der schwierige Teil - 9+1 gibt 10, aber jetzt müssen wir tragen, also fügen wir 1 zur nächsten Spalte hinzu und setzen (9+1)%10 in die dritte Spalte.
Wenn Ihre Zahlen groß genug werden - größer als 9999 in diesem Beispiel - dann müssen Sie irgendwie mehr Speicherplatz zuweisen.
Dies ist natürlich etwas vereinfacht, wenn Sie die Nummern in umgekehrt bestellen.
Reale Implementierungen verwenden ganze Wörter, so dass der Modul wirklich eine große Macht von zwei ist, aber das Konzept ist das gleiche.
Es gibt einen sehr guten Abschnitt darüber in Knuth.
vielen Dank :) – shahensha
Es gibt auch einen Abschnitt in Numerical Recipes (der Knuth genau folgt). Der schwierige Teil ist, die Multiplikation richtig zu machen. Der Schulalgorithmus skaliert nicht sehr gut, daher benutzt man Tricks (zB FFT). Sobald Sie Multiplikation haben, können Sie eine Menge Dinge damit ausdrücken. –