C Programmierung - Vorlesung 15 Matrixmultiplikation in C

Matrixmultiplikation in C
Das Produkt zweier Matrizen ist nur definiert, wenn die Zahl
der Spalten des ersten Faktors mit der Zahl der Zeilen des
zweiten Faktors übereinstimmt,
für
C Programmierung - Vorlesung 15
Hochschule Regensburg
11.05.2012
Universitätsstraße 31, 93053 Regensburg
Prof. Dr. Jan Dünnweber

a0,0
 ...

A :=  ai ,0
 ...
ak,0
...
...
...
...
...
a0,j
...
ai ,j
...
ak,j
...
...
...
...
...

a0,l
.... 

ai ,l 
.... 
ak,l

b0,0
 ...

B :=  bp,0
 ...
bm,0
...
...
...
...
...
b0,q
...
bp,q
...
bm,q
...
...
...
...
...

b0,n
.... 

bp,n 
.... 
bm,n
und
also genau dann, wenn l = m
Prof. Dr. Jan Dünnweber, Folie 2 von 14
Berechnung der Elemente der Produktmatrix
Programmierung 1
Darstellung der Matrizen in C
Wir verwenden wieder unseren Listentyp
Das Produkt einer k × l Matrix A und einer l × n Matrix B ist
somit eine k × n Matrix

C := 
c0,0
...
ck,0
...
ci ,j
....

c0,k
... 
ak,n
typedef struct {
int width; int height;
list *elements;
matrix;
}
deren Elemente definiert sind als
ci ,j :=
l
P
ai ,k · bk,j
k=0
d. h. es werden zusammengehörige Spalten- bzw.
Zeilenprodukte gebildet und aufsummiert
Es ist also z. B.
5
−12
18
4
=
2
−5
3
5
−1
3

3
· 0
1
matrix.c

2
4 
−2
matrix *createMatrix(int x, int y) {
register i, j;
matrix *newMatrix = (matrix *)malloc(sizeof(matrix));
newMatrix−>width = x, newMatrix−>height = y;
newMatrix−>elements = createList();
for (i = 0; i < x; ++i)
for (j = 0; j < y; ++j) {
double *value = (double *)malloc(sizeof(double));
*value = 0.0L;
insertElement(newMatrix−>elements, value);
}
return newMatrix;
}
intern sind die Element linear organisiert
Prof. Dr. Jan Dünnweber, Folie 3 von 14
Programmierung 1
Prof. Dr. Jan Dünnweber, Folie 4 von 14
Programmierung 1
Zugriff auf einzelne Matrixelemente
Matrizen strukturiert ausgeben
Zugriff mittels Indizes (Koordinaten) via get & set
Zur Kontrolle unserer Berechnungen verwenden wir folgende
printMatrix-Funktion
getValue
printMatrix
double getValue(matrix *source, int x, int y) {
node *position = getNode( source−>elements,
y * source−>width + x );
return *(double *)position−>element;
}
void printMatrix(matrix *m) {
register z, s;
for (z = 0; z < m−>width; ++z) {
for (s = 0; s < m−>height; ++s)
printf("%.1d ", (float)getValue(m, z, s));
printf("\n");
}
}
Beim Speichern neuer Werte ist auf korrektes
Speichermanagement (malloc & free) zu achten
setValue
void setValue(matrix *target, int x, int y, double value)
double *vp = malloc(sizeof(double));
*vp = value;
node *position = getNode( target−>elements,
y * target−>width + x );
position−>element = vp;
}
Prof. Dr. Jan Dünnweber, Folie 5 von 14
{
Programmierung 1
Berechnung des Produkts in C
Die Formel von Folie 3 lässt sich direkt in den Code
übernehmen:
Auslesen der Werte mittels getValue (→ Folie 5)
Beachte: Die Quellmatrix muss durch den Parameter m
wieder explizit angegeben werden!
Prof. Dr. Jan Dünnweber, Folie 6 von 14
Programmierung 1
Anwendung: Computergrafik - Berechnung einer Drehung
Rotationsmatrix
Die Rotationsmatrix für eine Drehung um den Ursprung ist im
euklidischen Raum definiert als:
Die mult-Funktion
matrix *mult(matrix *m1, matrix *m2) {
register i, j;
matrix *product = createMatrix(m1−>width, m2−>height);
for (i = 0; i < product−>width; ++i)
for (j = 0; j < product−>height; ++j) {
register k; double sum = 0.0;
for (k = 0; k < m1−>height; ++k)
sum = sum + getValue(m1, i, k) * getValue(m2, k, j);
setValue(product, i, j, sum);
}
return product;
}
Alternative: Algorithmus von V. Strassen
(’69, → Wikipedia)
Prof. Dr. Jan Dünnweber, Folie 7 von 14
Die Ausgabe der einzelnen Elemente erfolgt auf eine
Nachkommestelle genau
Programmierung 1
Rα :=
cosα −sinα
sinα cosα
Für eine Drehung um einen beliebigen Punkt ist vorher und
nachher je eine Translation durchzuführen
Wir verwenden diese Matrix nun testweise,
um ein Rechteck zu rotieren
Prof. Dr. Jan Dünnweber, Folie 8 von 14
Programmierung 1
Darstellung der Grafik: Die XWindow-Bibliothek
Die Standardtechnologie für grafische Benutzerobeflächen ist
unter UNIX das 1984 am MIT entwickelte XWindow-System
Für das Setup sind folgende Aufrufe notwendig:
1
2
3
4
XOpenDisplay → liefert Display-Handle zu $DISPLAY
createSimpleWindow → öffnet ein Fenster
createGC → liefert GraphicContext
... und los geht’s: XMapWindow, XSync, XDraw...
Dokumentation aller XLib-Routinen
http://users.actcom.co.il/~choo/lupg/tutorials/xlib-programming
Wir verwenden die libxhelper-Funktionen von der
Vorlesungs-Homepage und vertiefen Windows nicht weiter
(reale GUIs verwenden ohnehin higher-level Frameworks,
z. B. CDE, QT, ..)
Übersetzen von Code der XLib verwendet:
gcc test.c -o prog -L/usr/X11/lib -lX11
Prof. Dr. Jan Dünnweber, Folie 9 von 14
Programmierung 1
Funktionen mit ...-Parametern, z. B. beliebig viele Punkte
Wir verwenden die Makros va start, va arg und va list
(alle sind in stdarg.h definiert) wie folgt:
Beispiel: beliebig viele Zahlen addieren
#include <stdarg.h>
int add(int zahlen, ...) {
va_list zeiger;
int zahl;
va_start(zeiger,zahlen);
do {
zahl = va_arg(zeiger,int);
zahlen += zahl;
} while(zahl != 0);
va_end(zeiger);
return zahlen;
}
Die Rotationsfunktion
Die Darstellung unseres gedrehten Rechtecks berechnen wir
Ecke-für-Ecke:
rotateRect
XPoint *rotateRect(int x, int y, int w, int h, int a) {
static XPoint points[5];
points[0].x = x; points[0].y = y;
points[1].x = x + w; points[1].y = y;
points[2].x = x + w; points[2].y = y + h;
points[3].x = x; points[3].y = y + h;
points[4].x = x; points[4].y = y;
rotate( 5, a, &points[0], &points[1], &points[2], &points[3],
&points[4], &points[5] );
return points;
}
Die Funktion rotate projiziert dabei eine beliebige Menge
von Punkten (Typ: XPoint aus XLib)
⇒ Wir sehen uns die Verarbeitung der variablen
Parameterliste genauer an
Prof. Dr. Jan Dünnweber, Folie 10 von 14
Programmierung 1
Anwendung der Matrix und Grafik-Bibliotheksfunktionen
Berechnung der Rotation
void rotate(int n, int a, ...) {
va_list varpoints; auto i; XPoint *point;
va_start(varpoints, a);
for (i = 0; i < n; ++i) {
XPoint *point = va_arg(varpoints, XPoint *);
matrix *vector = createMatrix(1, 2),
*rotation = createMatrix(2, 2), *projection;
setValue(vector, 0, 0, point−>x);
setValue(vector, 0, 1, point−>y);
setValue(rotation, 0, 0, cos((double)a * M_PI / 180));
setValue(rotation, 1, 0, −sin((double)a * M_PI / 180));
setValue(rotation, 0, 1, sin((double)a * M_PI / 180));
setValue(rotation, 1, 1, cos((double)a * M_PI / 180));
projection = mult(vector, rotation);
point−>x = getValue(projection, 0, 0);
point−>y = getValue(projection, 0, 1);
}
va_end(varpoints); }
Aufruf z. B. mittels
printf("%d\n",add(11,12,13,0));
Es gilt aber: mind. ein Parameter muss bekannt sein
Prof. Dr. Jan Dünnweber, Folie 11 von 14
Programmierung 1
Da Winkel in Radiant (Bogenmaß) angegeben werden, müssen
diese vor Aufruf der trigonometrischen Funktionen noch mit
π/180 multipliziert werden
Prof. Dr. Jan Dünnweber, Folie 12 von 14
Programmierung 1
Das Hauptprogramm zur Darstellung des Rechecks
Das Hauptprogramm stellt das gedrehte Rechteck dar:
main
int main(int argc, char* argv[]) {
Display* display = XOpenDisplay(getenv("DISPLAY")); ...
if (argc < 2) { printf("specify an angle...\n"); exit(1); }
win = createSimpleWindow(display, width, height, 0, 0);
gc = createGC(display, win, 0); ... XMapWindow (display, win);
... angle = atoi(argv[[1]);
XDrawLines( display, win, gc,
rotateRect(140, 30, width / 4, height / 3, angle),
5, CoordModeOrigin );
XFlush(display); XSync(display, False);
getchar( ); XCloseDisplay(display);
return 0;
}
Mit atoi wird der ASCII Parameter zu int konvertiert
Prof. Dr. Jan Dünnweber, Folie 13 von 14
Programmierung 1
Zusammenfassung
Was haben wir gelernt?
Die Matrixmultiplikation ist nur für bestimmte Matrizen
definiert (z. B. quadratische, orthogonale, ...)
Die Implementierung in C kann mittels unterschiedlicher
Verbundtypen realisiert werden (z. B. Arrays oder Listen)
Die Multiplikation (aber auch jeder einzelne Zugriff und die
Ausgabe von Werten) erfordern auf die verwendeten
Datentypen angepasste Funktionen (im Beispiel getValue,
setValue, printMatrix, mult, ...)
Sollen einzelne Funktionen variable Paramterlisten haben, so
kann darauf mittels der Makros aus stdargs zugegriffen
werden (va start, va arg und va list)
Anwendungen ergeben sich z. B. (in Kombination mit der
XLib) in der Grafikprogrammierung
Für die Zusammenfassung der nicht-Standard Funktionen
bietet sich wieder benutzerdefinierte Bibliotheken an
Prof. Dr. Jan Dünnweber, Folie 14 von 14
Programmierung 1