Schlagwort: Informatik

Arbitrary-precision Arithmetic in C# 👍 👎

Für manche Anwendungen kann es notwendig werden, mit ganzen Zahlen zu arbeiten, die mitunter deutlich größer (bzw. kleiner) sind, als die CLS-Typen Int16 (short), Int32 (int) und Int64 (long) definieren.

Zwar ist es eine gute Übung, arithmetische Operationen auf ganzen Zahlen, die als Zeichenkette vorliegen, selbst zu implementieren – das .NET-Framework bringt jedoch bereits seit v4.0 die Struktur BigInteger aus System.Numerics mit. Sofern du dir also nicht sehr sicher bist, eine für deinen spezifischen Anwendungsfall bessere Implementierung vorliegen zu haben, solltest du eher auf das Framework setzen.

Die Verwendung gestaltet sich denkbar einfach, insofern belasse ich es für den Moment bei ein paar Beispielen:
BigInteger verwenden
0102030405060708091011
BigInteger a = BigInteger.Parse("34872923458349238592320478");BigInteger b = BigInteger.Parse("14782398471853465710237672");
// Operatorüberladung für BigInteger.Add(a, b)BigInteger sum = (a + b); // 49655321930202704302558150
// Operatorüberladung für BigInteger.Subtract(a, b)BigInteger difference = (a – b); // 20090524986495772882082806
// Operatorüberladung für BigInteger.Multiply(a, b)BigInteger product = (a * b); // 515505450439764661138576432136536115538523372647216
Selbstverständlich stehen noch einige andere nützliche Operationen und Indikatoren zur Verfügung.

Notwendig sind derartige Vorgehensweisen beispielsweise in der Kryptologie oder bei Simulationen in der numerischen Mathematik. Hauptsächlich kam ich jedoch deswegen auf diesen kurzen Beitrag, da einige Entwickler die Einführung dieser Struktur (BigInteger ist nicht als Klasse implementiert) verpasst zu haben scheinen. Smiley: smiling

Determine if a Number is a Power of Two 👍 👎

Für manche Algorithmen bestehen Optimierungsansätze, wenn eine zu untersuchende Zahl eine Zweierpotenz ist. Daher möchte ich mit diesem Beitrag aufzeigen, wie sich diese Problemstellung möglichst effizient lösen lässt.

Naive Ansätze arbeiten mit Schleifen und prüfen schrittweise alle in Frage kommenden Zweierpotenzen – es ist leicht einzusehen, dass dieses Vorgehen insbesondere für größere Zahlen eher mäßig effizient ist. Alternativ könnte man auf die Idee kommen, das Problem mit Logarithmen zu lösen – hier kann es jedoch zu Rundungsproblemen kommen. Wir sollten uns daher die Struktur entsprechender Zahlen einmal genauer ansehen:
Zweierpotenzen
010203040506
                  Dualzahl     Dezimalzahl--------------------------------------------       20               1            1       21              10            2       22             100            4       23            1000            8
Offensichtlich ist bei einer Zweierpotenz 2n demnach das (n + 1)-te Bit auf 1 gesetzt und alle ggf. nachfolgenden Stellen besitzen den Wert 0 – was kaum eine Überraschung darstellen sollte. Wir müssen nun jedoch nicht jedes Bit einzeln prüfen, ob die Zahl auf dieses "Muster" passt, sondern können uns das Bitmuster der Zahl 2n – 1 zu Nutze machen:
Voränger von Zweierpotenzen
010203040506
                  Dualzahl     2n – 1 (dual)--------------------------------------------       20               1            0       21              10           01       22             100          011       23            1000         0111
Wie selbstverständlich zu erwarten war, muss der Vorgänger ein inverses Bitmuster besitzen. Dies hilft uns insofern weiter, als dass wir diese beiden Zahlen mit einem bitweisen UND verknüpfen und auf Gleichheit mit 0 prüfen können, was bei Zweierpotenzen zutreffen muss.

In C# könnte die Implementierung beispielsweise wie folgt aussehen:
Zahl auf Zweierpotenz prüfen (Basis)
010203
public static bool IsPowerOfTwo(uint number) {    return ((number & (number – 1)) == 0);}
Dieses Vorgehen liefert jedoch auch für die Zahl 0 den Wert true zurück. Wir prüfen diesen Fall daher separat:
Zahl auf Zweierpotenz prüfen (Erweiterung)
01020304050607
public static bool IsPowerOfTwo(uint number) {    return (        (number != 0)          &&        ((number & (number – 1)) == 0)    );}

Aufrufer-Informationen für Methoden in C# 👍 👎

Manchmal kann es sinnvoll sein, sich Informationen über den Aufrufer einer Methode übermitteln zu lassen. Wir werden dies im Folgenden mit zwei praxisnahen Beispielen genauer untersuchen.

Zuerst möchten wir ein (einfaches) Logging-System implementieren:
Logging implementieren
010203040506070809
public static class Logging {    public static void Enter(string caller) {        Trace.WriteLine(caller + " betreten");    }
public static void Leave(string caller) { Trace.WriteLine(caller + " verlassen"); }}
Diese Klasse können wir nun beispielsweise wie folgt verwenden:
Logging verwenden
010203040506070809
static void Main(string[] args) {    Logging.Enter("Main");
/** * Aktionen ausführen **/
Logging.Leave("Main");}
Nun stellt uns jedoch das .NET-Framework ein spezielles Attribut CallerMemberName zur Verfügung, um diesen Prozess ein wenig zu optimieren – dazu müssen wir unsere Klasse minimal ergänzen:
Logging-Implementierung erweitern
010203040506070809
public static class Logging {    public static void Enter([CallerMemberName] string caller = "") {        Trace.WriteLine(caller + " betreten");    }
public static void Leave([CallerMemberName] string caller = "") { Trace.WriteLine(caller + " verlassen"); }}
Der Parameter caller wird nun beim Aufruf automatisch festgelegt, so dass die explizite Angabe in Main bei gleichem Ergebnis entfallen kann.

Ich möchte noch einen weiteren praktischen Anwendungsfall mit INotifyPropertyChanged demonstrieren:
INotifyPropertyChanged mit impliziten Aufruferinformationen
01020304050607080910111213141516171819202122232425262728293031323334353637
public class Person : INotifyPropertyChanged {    public event PropertyChangedEventHandler PropertyChanged;

private string name; public string Name { get { return this.name; } set { if(this.name != value) { this.name = value;
this.OnPropertyChanged(); } } }
private int age; public int Age { get { return this.age; } set { if(this.age != value) { this.age = value;
this.OnPropertyChanged(); } } }

private void OnPropertyChanged([CallerMemberName] string propertyName = "") { this?.PropertyChanged(this, new PropertyChangedEventArgs(propertyName)); }}
Dies vereinfacht die Verwendung dieser Schnittstelle, die insbesondere zur Datenbindung im Rahmen der WPF Verwendung findet – vor allem bei Refaktorierungsmaßnahmen. Das Verhalten ist wie erwartet:
Objekt verwenden
0102030405060708091011121314151617
Person ich = new Person() {    Name = "Holger",    Age = 25};
ich.PropertyChanged += (sender, e) => { Debug.WriteLine("Der Wert der Eigenschaft '{0}' hat sich geändert!", (object) e.PropertyName );};
ich.Age = 26;
/** * Das Ereignis "PropertyChanged" wird ausgelöst * und "PropertyName" implizit auf "Age" gesetzt.**/
Weitere Informationen (und hilfreiche Attribute) lassen sich im MSDN nachlesen.

.NET framework source code published 👍 👎

Einige werden es bereits erfahren haben, dennoch möchte auch ich darauf hinweisen, dass Microsoft weitere große Teile des .NET-Frameworks öffentlich zur Verfügung stellt. Unterstützt wird das Vorhaben durch Roslyn.

Die Inhalte sind dabei durchgängig interaktiv gestaltet und stehen unter der Reference Source License.

(Pseudo) Random Numbers in C# 👍 👎

Sehr häufig benötigt man in div. Anwendungen zufällige Zahlen (oder zumindest solche, die sich hinreichend ähnlich verhalten). Hierfür steht uns in C# die grundlegende Klasse Random zur Verfügung:
Random-Klasse verwenden
0102030405060708091011121314
Random random = new Random();
int randomInt = random.Next(); // Intervall: [0,Int32.MaxValue)int randomIntMax = random.Next(8); // Intervall: [0,8) bzw. [0,7]int randomIntMinMax = random.Next(5, 19); // Intervall: [5,19) bzw. [5,18]
/** * Befüllt "randomData" mit * zufälligen Byte-Werten.**/
byte[] randomData = new byte[3];random.NextBytes(randomData);
double randomDouble = random.NextDouble(); // Intervall: [0,1)
Manche Entwickler sind ggf. erst einmal etwas auf Grund der oberen Grenze verwirrt, welche bei Verwendung der entsprechenden Methoden exklusiv ist. Das bedeutet, dass ihr das eigentlich gewünschte Maximum inkrementiert angeben müsst, sofern dieses ebenfalls enthalten sein soll.

Die Verwendung gestaltet sich dennoch offensichtlich sehr einfach. Zu berücksichtigen gilt jedoch, dass als Seed standardmäßig ein zeitabhängiger Wert verwendet wird – um dieses Verhalten selbst zu steuern, existiert eine weitere Variante des Konstruktors. Gleiche Startwerte ergeben wie üblich gleiche Sequenzen an Zufallszahlen.

Für sensiblere Anwendungen, beispielsweise zur Schlüsselgenerierung, steht der kryptografische Zufallszahlengenerator RNGCryptoServiceProvider als konkrete Implementierung der abstrakten Basisklasse RandomNumberGenerator zur Verfügung. Die Verwendung gestaltet sich ähnlich einfach:
RNGCryptoServiceProvider-Klasse verwenden
01020304050607080910111213
using(RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider()) {      // 3 Zufallszahlen erzeugen    byte[] randomData = new byte[3];    rng.GetBytes(randomData);
// Zufalls-Bytes durchlaufen foreach(byte randomNumber in randomData) { /** * "randomNumber" enthält nun jeweils * eine der erzeugten Zufallszahlen. **/ }}
Weitere sinnvolle Hinweise finden sich in den jeweiligen Klassenbeschreibungen des MSDN.

Project links

Categories / Archive  |  Übersicht RSS feed

Tags

Search