November | 2013 | nerdpause

Zum Testen einer Methode zur Matrix-Multiplikation wollte ich gern Matrizen haben, dass das Ergebnis einer Matrixmultiplikation eine ganzzahlige Matrix mit „schönem“ Aussehen ist, so dass die Korrektheit der Implementation leicht überprüft werden kann. Sämtliche Matrizen sollten nach möglichkeit ganzzahlig sein. Um das Ziel zu erreichen habe ich einen Matrix-Generator geschrieben, mit dem ich das vorgestellte Verfahren erleutere. Der Generator benutzt meine simple Implementation einer Matrix-Klasse, die die wichtigsten Methoden bereitstellt.

Zuerst wollte ich eine Einheitsmatrix erzeugen, ich suchte also zwei Matrizen $A$ und $B$ mit $A \times B = E$ . Dies würde jede invertierbare Matrix erfüllen. Zusätzlich sollten nun aber $A$ und $B$ noch ganzzahlig sein. Allgemein ist für eine ganzzahlige Matrix $A$ die Inverse $A^{- 1}$ zwar rational, aber nicht ganzzahlig.

Meine Kenntnisse der linearen Algebra waren etwas eingerostet, aber nach kurzer Suche fand ich einen Artikel von Nathan Brixius, der ebenfalls über die Erzeugung spezieller Matrizen schrieb und mir bei der Erinnerung half. Für die Determinanten von Matrizen gilt $det(A) \cdot det(B) = det(AB)$ und die Determinante der Einheitsmatrix ist natürlich 1. Außerdem kann man die Determinante von Matrizen in oberer oder unterer Dreiecksform als Produkt der Diagonalen leicht bestimmen.

Wir erzeugen zunächst eine Matrix in unterer Dreiecksform:

double[][] values = new double[dimension][dimension];
for( int i = 0; i < dimension; ++i )
	values[i][i] = 1;
for( int i = 1; i < dimension; ++i )
	for( int j = 0; j < i; ++j )
		values[i][j] = getValue(i, j);
Matrix lowerTriangular = new Matrix( values );

Es wird ein 2-dimensionales Array erzeugt, das die Werte enthält. Die Diagonale wird mit $1$ gefüllt und die untere Hälfte mit Werten, die in der Methode getValue erzeugt werden (z.B. zufällig).

Genauso wird eine Matrix in oberer Dreiecksform benötigt:

values = new double[dimension][dimension];
for( int i = 0; i < dimension; ++i )
	values[i][i] = 1;
for( int i = 0; i < dimension-1; ++i )
	for( int j = i+1; j < dimension; ++j )
		values[i][j] = getValue(i, j);
Matrix upperTriangular = new Matrix( values );

Das Prinzip entspricht dem der LU-Zerlegung einer Matrix: Es werden zwei Matrizen L und U in unterer beziehungsweise oberer Dreiecksform erzeugt, so dass die Determinante 1 ist (d.h. die Diagonale ist 1). Die Matrix $M := L \times U$ ist ganzzahlig und invertierbar und nach der Bestimmung der Inversen über die Determinante ist die inverse Matrix $A^{- 1}$ ebenfalls ganzzahlig.

Matrix matrix = lowerTriangular.mult( upperTriangular );
Matrix inverse = matrix.invert();

Mögliche Matrizen als Testinstanzen sind damit also $M$ und $A^{- 1}$ . Um Abwechslung zu erzeugen kann man nun beliebige Matrizen $F$ an $M$ von links anmultiplizieren (oder an $A^{- 1}$ von rechts) und erhält als Ergebnis nicht mehr die Einheitsmatrix, sondern $F$ : $F \times M \times M^{- 1} = F \times E = F$ .

Als Beispiel erzeugen wir eine Matrix, die natürliche Zahlen von 1 aufsteigend enthält:

values = new double[dimension][dimension];
int c = 1;
for( int i = 0; i < dimension; ++i )
	for( int j = 0; j < dimension; ++j )
		values[i][j] = c++;
Matrix F = new Matrix( values );

Damit kann die Ausgabematrix erstellt werden:

Matrix result = matrix.mult( inverse );

Die beiden Testinstanzen sind dann result und inverse, das Ergebnis der Multiplikation ist $F$ . Natürlich kann $F$ auch rationale Zahlen enthalten, dann ist natürlich die Eingabematrix auch nicht mehr ganzzahlig.

Ich wollte mir eine Flasche 360 Vodka Glazed Donut bestellen, die Geschmacksrichtung ist einfach zu abgefahren, um sie nicht zu probieren. Leider gibt es fast keinen europäischen Händler, der diese Marke führt und amerikanische Händler verschicken nichts nach Europa. Also muss eine US-Adresse her, das ist aber auch leichter gesagt, als getan. Hier die ersten drei Phasen auf dem Weg zum Vodka.

Phase 1: Versand nicht Möglich

Nachdem ich vom Vodka 360° gehört hatte (nicht zu verwechseln mit Three Sixty!), wurde der Wunsch ihn zu haben schnell so groß, dass ich ihn nicht mehr ignorieren konnte.

So schwer kann das ja nicht sein… denkste! Schnell das Internet angeschmissen (nur metaphorisch), etwas gegoogelt und festgestellt: so einfach ist das doch nicht Er wird nur in den USA vertrieben (mit ausnahme eines UK-Stores, wo er aber ausverkauft war) und kein Geschäft in den USA schickt Alkohol nach Europa. Schon irgendwie verständlich, es mag ja Zoll-Probleme geben. Aber ich habe noch nicht mal einen Gefunden der Auf-eigene-Gefahr-Versand anbietet.

Nach weiterer Suche wurde auch klar, warum: zwar ist die Prohibition schon seit einiger Zeit vorbei, so richtig überwunden scheint das ganze Thema mit dem bösen Alkohol aber noch nicht, und so hat jeder Versandhändler auch eigene Listen, in welche Staaten er überhaupt Alkohol verschickt. So einfach geht das also nicht, es muss eine neue Idee her!

Phase 2: Weiterversand

Da viele Nerds eh an Gegenstände kommen müssen, die bei uns nicht verkauft werden (da wir dankenswerterweise hier hin #Neuland auch von Firmen wie Google zweitklassig behandelt und einige Produkte nicht bekommen) hatte ich schon von virtuellen Adressen gehört.

Kurze Recherche ergab drei Kandidaten: MyUS, Borderlinx und VIAdress. Letzterer fäll hauptsächlich durch Spam negativ auf, fällt also direkt raus. Borderlinx hätte zwar den Vorteil mit DHL zusammen zu Arbeiten und so die potentiellen Möglichkeit dem deutschen Zoll gut klar zu kommen, schießt sich aber durch die Restriktionen bereits ins Abseits. Dass Leichen und lebende Tiere nicht verschickt werden ist ja noch einsehbar. Aber auch Handys und Alkohol werden nicht verschickt (wichtig auch für alle Nerds!), sogar Pornos sind nicht erlaubt (wobei man die Möglichkeit ja eh nicht braucht). Also war die Entscheidung klar: MyUS sollte es werden, es wurde auch bei Awesome Drinks, dem Shop von Everyday Drinkers bzw. Common Man Cocktails für internationalen Versand empfohlen.

Phase 3: Account anlegen

Die letzte Phase sollte eigentlich recht schnell gehen. Account anlegen (kostet 10$) und fertig. Das hat sich jedoch als schwierig herausgestellt, da ich meine Kreditkartendaten nicht eingeben konnte, ausgerechnet bei einem amerikanischen Unternehmen, dabei funktioniert da doch alles mit Kreditkarten! Eine völlig neue Erfahrung. Zusätzlich zu den üblichen Informationen (Nummer, Code, …) wurde nämlich noch nach der „Issuing Bank“ und „Issuing Bank Phone Number“ gefragt.

Nun, die ausgebende Bank der Kreditkarte ist nicht unbedingt die Bank, von der man die Karte erhalten hat. Bei der Anmeldung wird immerhin der Tipp gegeben, dass diese Informationen auf der Rückseite stünden. Tatsächlich stand da bei mir auch was (eine Bank von der ich noch nie gehört habe). Die Telefonnummer steht da jedoch nicht.

Man kann jedoch einfach an diese Informationen kommen: die ersten sechs Ziffern der Kreditkartennummer, die sogenannte BIN, kodieren unter anderem die ausgebende Bank und in Online-Datenbanken wie Binbase.org kann man sich die Bank und zum Glück auch die Telefonnummer heraussuchen lassen.

Zuletzt verwendet MyUS bei der Dateneingabe einen Mechanismus, der von NoScript als gefährliche Cross-Site-Script-Attacke erkannt wird. Nach vielen Versuchen konnte ich es immerhin noch erreichen, dass meine Karte akzeptiert wurde und ich habe endlich meine Adresse in Florida .

Ob das ganze mit dem Vodka doch noch klappt, werde ich demnächst berichten.

nerdpause

Was tut ein Nerd in der Pause? (Und auch sonst!)

Archiv für den Monat: November 2013

Zufällige Matrizen generieren

Der lange Weg zur Adresse in den USA