Teilen ganzer Zahlen
-
Hallo zusammen,
ich habe eine Klasse geschrieben, die größere ganze Zahlen verwalten soll. Klappt soweit auch alles, leider ist die Division recht langsam, erscheint mir nicht grade geschickt implementiert, aber ich habe keine bessere Idee. Ich hab eben einfach schriftliche Division, wie man es in der Schule so lernt, gemacht.
Die Frage ist nun, wie kann ich da noch was verbessern? Gibt es da kluge Algorithmen, die das vereinfachen? Es geht mir um den Wissensdurst, ich will also keine fertige Klasse verwenden, ich will wissen wie's effizient geht.
Hab schonmal gesucht, aber bei den Sachen die es schon so gibt (gmp beispielsweise) steig ich ja mal gar nicht durch den Quelltext, als das ich mir da was abgucken könnte :).
Viele Grüße,
Divisor
-
Hmm, ich weiß nicht, ob es dir hilft, aber google mal nach "restoring division" oder "non-performimg division" ...
-
Benutze doch die Binärdarstellung der Zahlen. Mit shift-Methoden kommst du schnell an die Bits, und kannst die Rechnerinterne Darstellung ausnutzen, um einfache Algorithmen zu verwenden.