Schlagwort: Mathematik

Zahl auf Zweierpotenz prüfen 👍 👎

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)    );}

(Pseudo-)Zufallszahlen 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.

Farbcodes 👍 👎

Ab dem 1. August haben wir in der Firma einen neuen Auszubildenden zum Fachinformatiker für Anwendungsentwicklung. Dieser hat vor Kurzem noch ein zweiwöchiges Praktikum bei uns absolviert und dabei auch einiges von mir erfahren (ich hoffe, er hat sich erholt Smiley: winking). Auf dem Plan stand auch das Thema Farbcodes, wie sie insbesondere im Webdesign auftreten und nun möchte ich hier ebenfalls ein paar Worte dazu verlieren.

Zuerst einmal muss klar sein, was eigentlich die theoretische Grundlage dieser Notation ist, um sinnvolle Aussagen treffen zu können. Wir besprechen hier den RGB-Farbraum, welcher ein (additiver) Farbraum aus den drei Grundfarben Rot, Grün und Blau darstellt – wir besitzen demnach also drei Farbkanäle. Mit ein wenig Fantasie lässt sich bereits jetzt erahnen, wie entsprechende Farbcodes aus CSS zu verstehen sind:
#R1R0G1G0B1B0
Für jeden Farbkanal stehen uns in dieser Notation zwei hexadezimale Ziffern zur Verfügung, d. h. der Wertebereich pro Farbkanal erstreckt sich von 0 – ff16 (bzw. 0 – 25510) ≙ 162 (= 256) mögliche Werte.

Durch entsprechend niedrige bzw. hohe Werte pro Farbkanal ergibt sich proportional dazu die Intensität der jeweiligen Grundfarbe, d. h. um eben diese in voller Ausprägung darzustellen müssen wir lediglich den entsprechenden Farbkanal mit dem höchsten Wert belegen:
Grundfarben als Farbcode
010203
#ff0000 = ff (Rot) + 00 (Grün) + 00 (Blau) = Rot#00ff00 = 00 (Rot) + ff (Grün) + 00 (Blau) = Grün#0000ff = 00 (Rot) + 00 (Grün) + ff (Blau) = Blau
Wenn man sich den Farbraum wörtlich vorstellt, d. h. als Koordinatensystem mit den entsprechenden Farbkanälen als Achsen, können wir jeder Koordinate einen Farbeindruck entnehmen. Die tatsächlichen Farbmodelle sind noch etwas komplexer, für diese kleine Einführung ist diese Vorstellung jedoch durchaus legitim.

Sofern wir alle drei Farbkanäle mit einem identischen Wert belegen, erhalten wir einen grauen Eindruck zwischen niedrigster (Schwarz) und höchster (Weiß) Intensität:
Grauwerte
010203040506070809
#000000 = 00 (R) + 00 (G) + 00 (B) = Schwarz#333333 = 33 (R) + 33 (G) + 33 (B) = dunkles Grau#777777 = 77 (R) + 77 (G) + 77 (B) = mittleres Grau#cccccc = cc (R) + cc (G) + cc (B) = helles Grau#ffffff = ff (R) + ff (G) + ff (B) = Weiß
Sofern – wie im o. g. Beispiel, was dafür nicht unbedingt notwendig gewesen wäre – jeder Farbkanal aus zwei identischen Ziffern besteht, erlauben uns CSS und viele Grafikprogramme eine Kurzschreibweise, so dass aus #RRGGBB die Verkürzung #RGB werden kann. So kann beispielsweise aus #112233 schlicht #123 werden.

Weitere prägnante Farben zur Orientierung:
Weitere Farbcodes
010203
#00ffff (= #0ff) = 00 (R) + ff (G) + ff (B) = Cyan#ff00ff (= #f0f) = ff (R) + 00 (G) + ff (B) = Magenta#ffff00 (= #ff0) = ff (R) + ff (G) + 00 (B) = Gelb
Zugegebenermaßen war das nun wirklich nur eine sehr minimale Einführung mit einigen Vereinfachungen. Ich hoffe dennoch, dass manchem reinen "Farbcode-Kopierer" das System dadurch etwas klarer geworden ist.

Möglicherweise – das kann ich allerdings noch nicht versprechen – kann ich meinen ehem. Ausbilder einmal zu einem Gastbeitrag zum Thema Farbe und Licht bewegen, der als Elektrotechniker auf diesem Gebiet ein Experte ist und das auch sehr gut verständlich machen kann. Ein anderer Gastbeitrag ist auf jeden Fall bereits geplant. Smiley: smiling

Rundung in C# (und PHP) 👍 👎

Rundung erscheint auf den ersten Blick so selbstverständlich, dass so mancher geneigt scheint, sich darüber gar keine großen Gedanken zu machen. Beim Ab- und Aufrunden mit Methoden wie Math.Floor und Math.Ceiling gibt es auch tatsächlich keine großen Überraschungen bei den meisten Programmiersprachen:
Auf- und Abrunden
010203040506070809
  // Abrundungdouble floor1 = Math.Floor(1.3);  // 1double floor2 = Math.Floor(1.5);  // 1double floor3 = Math.Floor(1.7);  // 1  // Aufrundungdouble ceiling1 = Math.Ceiling(1.3);  // 2double ceiling2 = Math.Ceiling(1.5);  // 2double ceiling3 = Math.Ceiling(1.7);  // 2
Spannend wird es jedoch beim allgemeineren Rundungsverfahren mit Math.Round, bei welchem sich das Verhalten standardmäßig zu dem unterscheiden kann, was man beispielsweise aus der Schule als kaufmännisches Runden oder vom Standardverhalten von round aus PHP kennt. Der Unterschied liegt konkret beim Rundungsverhalten an der Ziffer 5:
Rundungsverhalten an der Ziffer "5"
01020304050607
double rounded11 = Math.Round(2.3);  // 2double rounded12 = Math.Round(2.5);  // 2 (!)double rounded13 = Math.Round(2.7);  // 3
double rounded21 = Math.Round(7.3); // 7double rounded22 = Math.Round(7.5); // 8double rounded23 = Math.Round(7.7); // 8
Die Ursache für dieses für manche möglicherweise überraschende Verhalten liegt darin begründet, dass bei C# das mathematische Rundungsverfahren zur Anwendung kommt, welches in so einem Fall standardmäßig die Rundung zur nächsten geraden Ziffer vorschreibt, anstatt pauschal aufzurunden. Das Anliegen dabei ist es, statistische Verzerrungen durch ausschließliches Aufrunden an dieser Stelle zu vermeiden. Dies ist in jedem Fall bei der Interoperabilität mit anderen Systemen, die auf eine gleiche Datenbasis zugreifen, zu berücksichtigen.

Sowohl bei C# als auch bei PHP lässt sich dieses Verhalten jedoch manuell anpassen (und dadurch nötigenfalls angleichen), indem man unter C# einen Wert der Enumeration MidpointRounding oder unter PHP eine der Konstanten PHP_ROUND_HALF_* an die entsprechende Methode/Funktion zur Rundung übergibt.

Zahl ohne Konvertierung umdrehen 👍 👎

Passend zu einem etwas älteren Beitrag zur Ermittlung der Anzahl der Ziffern einer Zahl soll es noch einmal darum gehen, ein Problem mathematisch zu lösen, statt den Umweg über Zeichenketten zu gehen. Konkret möchten wir eine Zahl schlicht "umdrehen". Im Prinzip soweit natürlich kein Problem:
Zahl umdrehen (mit Konvertierung)
010203
int number = 12345;
int numberReverse = Int32.Parse(String.Concat(number.ToString().Reverse())); // 54321
Wir konvertieren die Zahl hierbei zuerst zu einer Zeichenkette, drehen die Zeichen anschließend um und fügen sie zusammen, um sie letztlich wieder zu einer Zahl zu konvertieren.

Das funktioniert – zumindest bei nicht-negativen Zahlen – soweit auch einwandfrei und kann je nach Kontext auch die schnellste Variante sein, jedoch lässt sich das Problem auch rein rechnerisch lösen:
Zahl umdrehen (ohne Konvertierung)
010203040506070809
int number = 12345;
int numberReverse = 0;while(number != 0) { numberReverse *= 10; numberReverse += (number % 10);
number /= 10;} // "numberReverse" enthält nun (ebenfalls) 54321
Wir nutzen dabei aus, dass uns der Modulo-Operator (%) jeweils den Rest einer ganzzahligen Division liefert, welchen wir als neue Ziffer der Lösung verwenden und anschließend die gegebene Zahl um eben diesen Anteil verringern. Als netter "Nebeneffekt" funktioniert diese Vorgehensweise auch bei negativen Zahlen problemlos.

Projektverweise

Kategorien / Archiv  |  Übersicht RSS-Feed

Schlagworte

Suche