Wie kann ich Division in einem Programm, Ziffer für Ziffer durchführen?

Question

Ich bin mit dem Schreiben einer Klasse ähnlich wie mpz (C) oder BigInteger (Java). Dies ist nur zum Spaß, also bitte nicht weiter darüber, wie ich nicht mein eigenes schreiben sollte.

Ich habe eine Klasse ähnlich wie:

public class HugeInt 
{ 
    public List<Integer> digits; 

    public HugeInt(String value) 
    { 
     // convert string value into its seperate digits. 
     // store them in instance variable above 
    } 
} 

nun das Add tun() und subtrahieren() -Methode dieser Klasse sind ziemlich einfach. Hier ein Beispiel:

private List<Integer> add(List<Integer> a, List<Integer> b) 
    { 
     List<Integer> smallerDigits = (compareDigits(a,b) < 0) ? a : b; 
     List<Integer> largerDigits = (compareDigits(a,b) >= 0) ? a : b; 
     List<Integer> result = new ArrayList<Integer>(); 

     int carry = 0; 

     for(int i = 0; i < largerDigits.size(); i++) 
     { 
      int num1 = largerDigits.get(i); 
      int num2 = (i < smallerDigits.size()) ? smallerDigits.get(i) : 0; 

      result.add((num1 + num2 + carry) % 10); 
      carry = ((num1 + num2 + carry)/10); 
     } 

     if (carry != 0) result.add(carry); 

     return result; 
    } 

In ähnlicher Weise macht die mehrfach nicht so schwer, entweder war.

Ich sehe auf Wikipedia gibt es eine Seite auf Division Algorithms, aber ich bin mir nicht sicher, welches für das, was ich versuche, geeignet ist.

Da diese positiven ganzen Zahlen (dargestellt als Ziffern) beliebig lang sein können, möchte ich sicherstellen, dass ich nicht versuche, irgendetwas anderes als Ziffer für Ziffer zu tun.

Kann aber jemand mich in die richtige Richtung für eine Division von zwei Zahlen, die als List<Integer> 's dargestellt sind, zeigen? Außerdem kann ich den Rest ignorieren, da dies eine Integer-Division ist.

Answer 1

Da ich davon ausgehe, dass es sich nur um Integer Division handelt, ist es nicht sehr schwer. Multiplikation ist wiederholte Addition, Division ist das Gegenteil - wiederholte Subtraktion. Sie werden also prüfen, wie oft Sie den Divisor von der Dividende subtrahieren können. Zum Beispiel 3 kann von 10 3 mal abgezogen werden, ohne < zu gehen 0, so dass die Integer-Division Quotient 3.

Answer 2

Sie nur long division tun könnte, aber das ist sicherlich nicht der optimale Weg, es zu tun (bearbeiten : obwohl es scheint, dass so etwas ein guter Weg ist, es zu tun). Sie können other implementations große Integer-Bibliotheken betrachten, und ein wenig Googling ergibt ein gutes Stück nützliche Informationen.

Answer 3

Dies kann ein leichter zu viel des Guten, aber wenn dies die Art von Dingen, die Sie für Spaß zu tun, werden Sie genießen das lesen: http://www.fizyka.umk.pl/nrbook/c20-6.pdf (das „Rechnen in beliebiger Genauigkeit“ von „Numerical Recipes in C“ ist) . Ziemlich faszinierend, wie die meisten dieses Buches, mit guten Erklärungen und viel Code.

Answer 4

Dieser Artikel A Larger Integer zeigt nicht, wie Ziffern für Ziffernoperationen für "größere Ganzzahlen" implementiert werden, aber es zeigt, wie eine (scheinbar voll funktionsfähige) 128-Bit-Ganzzahl in Bezug auf zwei Int64-Typen implementiert wird. Ich würde mir vorstellen, dass es nicht zu schwer wäre, den Ansatz zu erweitern, ein Array von Int64-Typen zu verwenden, um eine ganze Zahl mit beliebiger Länge zu erhalten. Ich habe gerade ein paar Minuten damit verbracht, auf den Artikel zurückzublicken, und die Implementierung von Multiply sieht so aus, als könnte es für beliebige Länge ziemlich kompliziert werden.

Der Artikel zeigt, wie Division (Quotienten und Rest) mit binary division implementieren.