einen einfacheren großen Addierer in c#?

Question

Ich hatte gerade in der Schule die Aufgabe, einen großen Zettel zu schreiben. Das heißt, eine Methode, die sehr große Zahlen zusammenzählen kann. Wir hatten 10 Minuten Zeit, und ich habe die Aufgabe pünktlich gelöst. Die Lehrerin hat sie genehmigt.

Mit dem Ergebnis bin ich allerdings nicht ganz zufrieden, und ich dachte, ich hätte vielleicht den falschen Ansatz gewählt.

Hier ist meine Version:

using System;
using System.Text;

namespace kæmpe_adder
{
    static class Program
    {
        static void Main()
        {
            var x = "1111";
            var y = "111111111";

            Console.WriteLine(BigAdder(x, y));
            Console.ReadLine();
        }
        public static StringBuilder BigAdder(string x, string y)
        {
            var a = new StringBuilder(x);
            var b = new StringBuilder(y);
            return BigAdder(a, b);
        }
        public static StringBuilder BigAdder(StringBuilder x, StringBuilder y)
        {
            int biggest;
            int carry = 0;
            int sum;
            var stringSum = new StringBuilder();

            if (x.Length > y.Length)
            {
                y.FillString(x.Length - y.Length);
                biggest = x.Length;
            }
            else if (y.Length > x.Length)
            {
                x.FillString(y.Length - x.Length);
                biggest = y.Length;
            }
            else
            {
                biggest = y.Length;
            }

            for (int i = biggest - 1; i >= 0; i--)
            {
                sum = Convert.ToInt32(x[i].ToString()) + Convert.ToInt32(y[i].ToString()) + carry;
                carry = sum / 10;
                stringSum.Insert(0, sum % 10);
            }

            if (carry != 0)
            {
                stringSum.Insert(0, carry);
            }

            return stringSum;
        }
        public static void FillString(this StringBuilder str, int max)
        {
            for (int i = 0; i < max; i++)
            {
                str.Insert(0, "0");
            }
        }
    }
}

Als ich es schrieb, dachte ich daran, wie man es mit Binärdateien macht.

Gibt es einen kürzeren und/oder vielleicht einfacheren Weg, dies zu tun?

Answer 1

Vom algebraischen Standpunkt aus sieht Ihr Code korrekt aus. Aus der Sicht des Designs wäre es definitiv besser, jede dieser großen Zahlen in einer Klasse zu kapseln, so dass Sie nicht ständig auf die String/String Builder verweisen müssen. Ich bin auch kein großer Fan dieses FillString-Ansatzes, es scheint sinnvoller zu sein, die Ziffern zu addieren, solange beide Zahlen Nicht-Null-Werte haben, und dann einfach den Übertrag zur größeren Zahl hinzuzufügen, bis man fertig ist.

Ich bin mir nicht sicher, wie die Frage zu den Binärdateien lautete. Die Zahlen normaler Länge (32bit und 64bit) werden von der CPU in einer einzigen Operation addiert.

Answer 2

Es gibt eine Reihe von Open-Source-Implementierungen, von denen Sie sich inspirieren lassen können.

http://www.codeproject.com/KB/cs/biginteger.aspx

http://biginteger.codeplex.com/

Im Allgemeinen würde ich empfehlen, ein Array von Byte oder Long für die beste Leistung zu verwenden, aber die Umwandlung von einer Zeichenfolge in das Array wäre nicht trivial.

Speichern Sie die Zahlen in umgekehrter Reihenfolge; dies macht das Auffinden gleichwertiger Stellen trivial.

Dies erleichtert das Hinzufügen unterschiedlich großer Zeichenketten Zahlen:

int place = 0;
int carry = 0;

while ( place < shorter.Length ) {
    result.Append (AddDigits (longer[place], shorter[place], ref carry));
    ++place;
}

while ( place < longer.Length ) {
    result.Append (AddDigits (longer[place], 0, ref carry));
    ++place;
}

if ( carry != 0 )
    result.Append (carry.ToString ());