?
Hi, ist das hier noch aktuell?
Ich habe vor ewiger Zeit mal was ähnliches programmiert und jedenfalls noch etwas Code dazu gefunden. Wollte das eigentlich schon anfang die Woche posten, ist aber irgendwie untergegangen.
Habe alles rausgeworfen, was für die Aufgabe nicht relevant ist. Ob das alles korrekt ist weiß ich nicht, das ist wie gesagt schon länger her, dass ich das mal geschrieben habe und war nur ein privater Test aus langeweile
using System;
namespace Big
{
class Program
{
static void Main(string[] args)
{
ulong Base = 100000;
Bignum factorial = new Bignum(Base, 1);
Bignum max = new Bignum(Base, 100);
Bignum one = new Bignum(Base, 1);
for (Bignum i = new Bignum(Base, 1); i <= max; i += one)
{
factorial *= i;
}
Console.WriteLine(factorial.ToString());
Console.ReadKey(true);
}
}
}
Das ist das Hauptprogramm um die Fakultät von 100 zu berechnen. Zum Konstruktor der Bignum-Klasse sei gesagt, dass man im letzten Parameter die Ziffern einer Zahl getrennt angibt. Beispiel die Zahl 4711 im Dezimalsystem würden man konstruieren als: new Bignum(10, 4, 7, 1, 1)
Oben im Beispiel arbeiten wir mit dem 100k-System. Das heißt der max-Wert von 100 wird als einzelne Ziffer dieses Systems angegeben im Konstruktor!
Die Klasse Bignum verwendet eine Digit-Klasse um eine Ziffer zu repräsentieren:
using System;
namespace Big
{
struct Digit : IComparable<Digit>
{
public readonly ulong digit;
public readonly ulong radix;
public Digit(ulong radix, ulong digit)
{
if (digit >= radix)
throw new ArgumentException("digit>=radix");
this.digit = digit;
this.radix = radix;
}
public static void Add(Digit a, Digit b, ref Digit carry, out Digit sum)
{
ulong radix = a.radix;
sum = new Digit(radix, (a.digit + b.digit + carry.digit) % radix);
carry = sum.digit < a.digit || sum.digit < b.digit || a.digit == radix - 1 && b.digit == radix - 1 && carry.digit == 1
? new Digit(radix, 1)
: new Digit(radix, 0);
}
public static void Sub(Digit a, Digit b, ref Digit carry, out Digit diff)
{
ulong radix = a.radix;
ulong diff_;
ulong carry_;
if (a.digit >= (b.digit + carry.digit))
{
diff_ = a.digit - (b.digit + carry.digit);
carry_ = 0;
}
else
{
diff_ = radix + a.digit - (b.digit + carry.digit);
carry_ = 1;
}
diff = new Digit(radix, diff_);
carry = new Digit(radix, carry_);
}
public static void Mul(Digit a, Digit b, ref Digit carry, out Digit product)
{
ulong radix = a.radix;
product = new Digit(radix, (a.digit * b.digit + carry.digit) % radix);
//das geht nicht gut für hohe radixe (überlauf)
carry = new Digit(radix, (a.digit * b.digit + carry.digit) / radix);
}
public override bool Equals(object obj)
{
return this.CompareTo((Digit)obj) == 0;
}
public int CompareTo(Digit other)
{
return digit.CompareTo(other.digit);
}
public override string ToString()
{
if (radix == 16 && digit >= 10)
return new string(new char[] { (char)('A' + digit - 10) });
return digit.ToString();
}
}
}
Und nun Bignum selbst:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Big
{
class Bignum : IComparable<Bignum>
{
readonly ulong radix;
private List<Digit> digits;
public enum Sign { Pos = 1, Neg = -1 }
public Bignum(ulong radix, params ulong[] num)
{
this.radix = radix;
digits = num.Select(u => new Digit(radix, u)).Reverse().ToList();
}
public Bignum(ulong radix, List<Digit> num)
{
this.radix = radix;
digits = num;
}
public Bignum(Bignum other)
{
radix = other.radix;
digits = other.digits.ToList();
}
public int DigitCount()
{
return digits.Count;
}
public int CompareTo(Bignum other)
{
if (radix != other.radix)
throw new ArgumentException("base mismatch");
int cmp = 0;
if (digits.Count != other.digits.Count)
cmp = Math.Sign(digits.Count - other.digits.Count);
else
for (int i = digits.Count - 1; i >= 0; --i)
{
int digitCmp = digits[i].CompareTo(other.digits[i]);
if (digitCmp != 0)
{
cmp = digitCmp;
break;
}
}
return cmp;
}
public override bool Equals(object obj)
{
return this.CompareTo((Bignum)obj) == 0;
}
public static Bignum operator *(Bignum a, Bignum b)
{
return Mul(a, b);
}
public static Bignum operator +(Bignum a, Bignum b)
{
return Add(a, b);
}
public static bool operator <(Bignum a, Bignum b)
{
return a.CompareTo(b) < 0;
}
public static bool operator >(Bignum a, Bignum b)
{
return a.CompareTo(b) > 0;
}
public static bool operator <=(Bignum a, Bignum b)
{
int cmp = a.CompareTo(b);
return cmp < 0 || cmp == 0;
}
public static bool operator >=(Bignum a, Bignum b)
{
int cmp = a.CompareTo(b);
return cmp > 0 || cmp == 0;
}
public static bool operator ==(Bignum a, Bignum b)
{
return a.CompareTo(b) == 0;
}
public static bool operator !=(Bignum a, Bignum b)
{
return a.CompareTo(b) != 0;
}
private static Bignum Mul(Bignum a, Digit d)
{
if (a.radix != d.radix)
throw new ArgumentException("base mismatch");
ulong radix = a.radix;
int count = a.digits.Count;
List<Digit> result = new List<Digit>(count + 1);
Digit carry = new Digit(radix, 0);
for (int i = 0; i < count || carry.digit != 0; ++i)
{
Digit first = i < a.digits.Count ? a.digits[i] : new Digit(radix, 0);
Digit prod;
Digit.Mul(first, d, ref carry, out prod);
result.Add(prod);
}
Bignum product = new Bignum(radix, result);
//product.Normalize();
return product;
}
public static Bignum Mul(Bignum a, Bignum b)
{
if (a.radix != b.radix)
throw new ArgumentException("base mismatch");
ulong radix = a.radix;
Bignum product = new Bignum(radix, 0);
for (int i = 0; i < b.digits.Count; ++i)
{
Bignum mul = Bignum.Mul(a, b.digits[i]);
mul.ShiftLeft(i);
product = Bignum.Add(product, mul);
}
Bignum zero = new Bignum(radix, 0);
product.Normalize();
return product;
}
public static Bignum Add(Bignum a, Bignum b)
{
if (a.radix != b.radix)
throw new ArgumentException("base mismatch");
ulong radix = a.radix;
int count = Math.Max(a.digits.Count, b.digits.Count);
List<Digit> result = new List<Digit>(count + 1);
Digit zero = new Digit(radix, 0);
Digit carry = zero;
for (int i = 0; i < count || carry.digit == 1; ++i)
{
Digit first = i < a.digits.Count ? a.digits[i] : zero;
Digit second = i < b.digits.Count ? b.digits[i] : zero;
Digit sum;
Digit.Add(first, second, ref carry, out sum);
result.Add(sum);
}
return new Bignum(radix, result);
}
public void Normalize()
{
int i;
for (i = digits.Count - 1; i > 0 && digits[i].digit == 0; --i) ;
digits.RemoveRange(i + 1, digits.Count - 1 - i);
}
public void ShiftLeft(int count)
{
if (count <= 0)
return;
List<Digit> dig = new List<Digit>(digits.Count + count);
Digit zero = new Digit(radix, 0);
for (int i = 0; i < digits.Count + count; ++i)
if (i < count)
dig.Add(zero);
else
dig.Add(digits[i - count]);
digits = dig;
}
public override string ToString()
{
StringBuilder b = new StringBuilder();
for (int i = digits.Count - 1; i >= 0; --i)
{
b.Append(digits[i].ToString() + " ");
}
return b.ToString();
}
}
}
Das Beispiel zur Fakultät von 100 liefert als Ausgabe:
933 26215 44394 41526 81699 23885 62667 490 71596 82643 81621 46859 29638 95217 59999 32299 15608 94146 39761 56518 28625 36979 20827 22375 82511 85210 91686 40000 0 0 0 0
Wolfram Alpha sagt 100! =
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000 00000 00000 00000 00000
Auffällig ist die unterschiedliche Anzahl Nullen am Ende. Beachte wieder, dass die Ausgabe oben im 100k-System erfolgt. D.h. jeder 5-er Block Zahlen muss um 100000^k verschoben werden. Die letzte Ziffer != 0 ist 40000 und das wäre im Dezimalsystem: 40000 * 100000^4 = 4000000000000000000000000. Das Ergebnis stimmt also.
Grüße
