+/EE312

software design

git clone https://git.julia.blue/+/EE312

Joseph RyanAdd Project 1 and start Project 2f830e85

master
19.3 KiB644 linesraw
1#include <assert.h>
2#include <math.h>
3#include <stdint.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7
8#include "MatrixMultiply.h"
9
10
11void generateIdentityMatrix(double a[], const uint32_t rows,
12                            const uint32_t cols);
13
14void generateIdentityMatrixPtr(double **a, const uint32_t rows,
15                               const uint32_t cols);
16
17void perturbMatrix(double a[], const uint32_t rows, const uint32_t cols,
18                   uint32_t src_row[], double perturb_values[],
19                   const uint32_t num_perturbations);
20
21void perturbMatrixPtr(double **a, const uint32_t rows, const uint32_t cols,
22                      uint32_t src_row[], double perturb_values[],
23                      const uint32_t num_perturbations);
24
25void generateRandomMatrix(double a[], const uint32_t rows,
26                          const uint32_t cols);
27
28void generateRandomMatrixPtr(double** a, const uint32_t rows,
29                             const uint32_t cols);
30
31
32int assertEqualMatrices(double a[], double b[], const uint32_t rows,
33                        const uint32_t cols);
34
35int assertEqualMatricesPtr(double** a, double** b, const uint32_t rows,
36                           const uint32_t cols);
37
38void copyMatrix(double dest[], double src[], const uint32_t rows,
39                const uint32_t cols);
40
41void copyMatrixPtr(double** dest, double** src, const uint32_t rows,
42                   const uint32_t cols);
43
44void printMatrix(double a[], const uint32_t rows, const uint32_t cols);
45
46void printMatrixPtr(double** a, const uint32_t rows, const uint32_t cols);
47
48void memoryRelease(double** ptr, int length);
49
50void generateIdentityMatrix(double a[], const uint32_t rows,
51                            const uint32_t cols) {
52    uint32_t i, j; // two loop variables, uninteresting in all respects.
53    i = 0;
54    while (i < rows) {
55        j = 0;
56        while (j < cols) {
57            if (i == j) {
58                a[(i * cols) + j] = 1.0;
59            } else {
60                a[(i * cols) + j] = 0;
61            }
62            j += 1;
63        }
64        i += 1;
65    }
66}
67
68void generateIdentityMatrixPtr(double **a, const uint32_t rows,
69                               const uint32_t cols) {
70    uint32_t i, j; // two loop variables, uninteresting in all respects.
71    i = 0;
72    while (i < rows) {
73        j = 0;
74        while (j < cols) {
75            if (i == j) {
76                a[i][j] = 1.0;
77            } else {
78                a[i][j] = 0;
79            }
80            j += 1;
81        }
82        i += 1;
83    }
84}
85
86void perturbMatrix(double a[], const uint32_t rows, const uint32_t cols,
87                   uint32_t src_row[], double perturb_values[],
88                   const uint32_t num_perturbations) {
89    uint32_t i, k;    // two loop variables, uninteresting in all respects.
90    uint32_t dst_row; // index of the row being written into
91    i = 0;
92    while (i < num_perturbations) {
93        assert(src_row[i] < rows);
94        /* apply perturbation i to every row (except to itself) */
95        dst_row = 0;
96        while (dst_row < rows) {
97            if (dst_row != src_row[i]) {
98                /* take the src row, and scale it by the perturbation value
99                 * and add the resulting row to the destination row */
100                k = 0;
101                while (k < cols) {
102                    a[(dst_row * cols) + k] +=
103                    perturb_values[i] * a[(src_row[i] * cols) + k];
104                    k += 1;
105                } // end for each element in a row
106            }   // end if dst_row != src_row
107            dst_row += 1;
108        } // end for each dst_row in the matrix
109        i += 1;
110    } // end for each perturbation
111}
112
113void perturbMatrixPtr(double **a, const uint32_t rows, const uint32_t cols,
114                      uint32_t src_row[], double perturb_values[],
115                      const uint32_t num_perturbations) {
116    uint32_t i, k;    // two loop variables, uninteresting in all respects.
117    uint32_t dst_row; // index of the row being written into
118    i = 0;
119    while (i < num_perturbations) {
120        assert(src_row[i] < rows);
121        /* apply perturbation i to every row (except to itself) */
122        dst_row = 0;
123        while (dst_row < rows) {
124            if (dst_row != src_row[i]) {
125                /* take the src row, and scale it by the perturbation value
126                 * and add the resulting row to the destination row */
127                k = 0;
128                while (k < cols) {
129                    a[dst_row][k] += perturb_values[i] * a[src_row[i]][k];
130                    k += 1;
131                } // end for each element in a row
132            }   // end if dst_row != src_row
133            dst_row += 1;
134        } // end for each dst_row in the matrix
135        i += 1;
136    } // end for each perturbation
137}
138
139/*
140 * generate a matrix with random elements.
141 * the matrix should be stored in array a in row-major order
142 * the parameters 'rows' and 'cols' specify the size of the matrix
143 */
144void generateRandomMatrix(double a[], const uint32_t rows,
145                          const uint32_t cols) {
146    const int max_value = 100; // maximum scale factor to apply to a row
147    const int perturbations = 7;
148    uint32_t src_rows[7];
149    double perturb_values[7];
150    int k; // an unininteresting loop variable
151    
152    /* randomly perturb the matrix seven times, that should scramble things pretty
153     * well */
154    generateIdentityMatrix(a, rows, cols);
155    
156    k = 0;
157    while (k < perturbations) {
158        src_rows[k] = rand() % rows;
159        perturb_values[k] = max_value - (rand() % (2 * max_value));
160        k += 1;
161    }
162    
163    perturbMatrix(a, rows, cols, src_rows, perturb_values, perturbations);
164}
165
166void generateRandomMatrixPtr(double **a, const uint32_t rows,
167                             const uint32_t cols) {
168    const int max_value = 100; // maximum scale factor to apply to a row
169    const int perturbations = 7;
170    uint32_t src_rows[7];
171    double perturb_values[7];
172    int k; // an unininteresting loop variable
173    
174    /* randomly perturb the matrix seven times, that should scramble things pretty
175     * well */
176    generateIdentityMatrixPtr(a, rows, cols);
177    
178    k = 0;
179    while (k < perturbations) {
180        src_rows[k] = rand() % rows;
181        perturb_values[k] = max_value - (rand() % (2 * max_value));
182        k += 1;
183    }
184    
185    perturbMatrixPtr(a, rows, cols, src_rows, perturb_values, perturbations);
186}
187
188int assertEqualMatrices(double a[], double b[], const uint32_t rows,
189                        const uint32_t cols) {
190    uint32_t i, j; // two loop variables, uninteresting in all respects.
191    
192    i = 0;
193    while (i < rows) {
194        j = 0;
195        while (j < cols) {
196            double difference = fabs(a[(i * cols) + j] - b[(i * cols) + j]);
197            if (difference > 1.0e-6) {
198                fprintf(stderr, "Sorry, matrices do not match, first difference at row "
199                        "%d and col %d\n",
200                        i, j);
201                return false;
202            }
203            j += 1;
204        }
205        i += 1;
206    }
207    return true;
208}
209
210int assertEqualMatricesPtr(double **a, double **b, const uint32_t rows,
211                           const uint32_t cols) {
212    uint32_t i, j; // two loop variables, uninteresting in all respects.
213    
214    i = 0;
215    while (i < rows) {
216        j = 0;
217        while (j < cols) {
218            double difference = fabs(a[i][j] - b[i][j]);
219            if (difference > 1.0e-6) {
220                fprintf(stderr, "Sorry, matrices do not match, first difference at row "
221                        "%d and col %d\n",
222                        i, j);
223                return false;
224            }
225            j += 1;
226        }
227        i += 1;
228    }
229    return true;
230}
231
232void copyMatrix(double dest[], double src[], const uint32_t rows,
233                const uint32_t cols) {
234    uint32_t i = 0;
235    while (i < rows) {
236        uint32_t j = 0;
237        while (j < cols) {
238            dest[(i * cols) + j] = src[(i * cols) + j];
239            j += 1;
240        }
241        i += 1;
242    }
243}
244
245void copyMatrixPtr(double **dest, double **src, const uint32_t rows,
246                   const uint32_t cols) {
247    uint32_t i = 0;
248    while (i < rows) {
249        uint32_t j = 0;
250        while (j < cols) {
251            dest[i][j] = src[i][j];
252            j += 1;
253        }
254        i += 1;
255    }
256}
257
258void printMatrix(double a[], const uint32_t rows, const uint32_t cols) {
259    uint32_t i = 0;
260    while (i < rows) {
261        uint32_t j = 0;
262        while (j < cols) {
263            printf("%g, ", a[(i * cols) + j]); // %g is just like %f, only better
264            j += 1;
265        }
266        printf("\n");
267        i += 1;
268    }
269}
270
271void printMatrixPtr(double **a, const uint32_t rows, const uint32_t cols) {
272    uint32_t i = 0;
273    while (i < rows) {
274        uint32_t j = 0;
275        while (j < cols) {
276            printf("%g, ", a[i][j]); // %g is just like %f, only better
277            j += 1;
278        }
279        printf("\n");
280        i += 1;
281    }
282}
283
284
285void memoryRelease(double** ptr, int length) {
286    for(int i =0; i < length ; i++) {
287        free(*(ptr + i));
288    }
289    free(ptr);
290}
291
292/* ---------------------------------------- */
293
294void testMultiplyMatrixA(void) {
295    double a[100];
296    double b[100];
297    double c[100];
298    
299    generateRandomMatrix(a, 10, 10);
300    generateIdentityMatrix(b, 10, 10);
301    multiplyMatrices(a, 10, 10, b, 10, c);
302    printf("Stage 1 test testMultiplyMatrixA:...");
303    if (!assertEqualMatrices(a, c, 10, 10)) {
304        return;
305    }
306    printf("passed! :-)\n");
307}
308
309void testMultiplyMatrixB(void) {
310    double a[100];
311    double b[100];
312    double c[100];
313    
314    generateRandomMatrix(a, 10, 10);
315    generateIdentityMatrix(b, 10, 10);
316    multiplyMatrices(b, 10, 10, a, 10, c);
317    printf("Stage 1 test testMultiplyMatrixB:...");
318    if (!assertEqualMatrices(a, c, 10, 10)) {
319        return;
320    }
321    printf("passed! :-)\n");
322}
323
324void testMultiplyMatrixC(void) {
325    double a[100];
326    double b[100];
327    double c[100];
328    
329    /* these arrays are used only for test C */
330    uint32_t perturb_rows[5] = {2, 4, 6, 1, 7};
331    double perturb_vals[5] = {1.0, -1.0, 2.0, -2.5, 3.0};
332    double expected[] = {
333        1, -10, 0, 0, 18, 0, -12, 3, 0, 0, 0, -6.5, 0, 0, 10.5, 0, -7,  3, 0, 0,
334        0, -10, 0, 0, 18, 0, -12, 3, 0, 0, 0, -10,  0, 1, 18,   0, -12, 3, 0, 0,
335        0, -10, 1, 0, 20, 0, -12, 3, 0, 0, 0, -10,  0, 0, 18,   1, -12, 3, 0, 0,
336        0, -10, 0, 0, 20, 0, -13, 3, 0, 0, 0, -2.5, 0, 0, 4.5,  0, -3,  1, 0, 0,
337        0, -10, 0, 0, 18, 0, -12, 3, 1, 0, 0, -10,  0, 0, 18,   0, -12, 3, 0, 1};
338    
339    generateIdentityMatrix(a, 10, 10);
340    generateIdentityMatrix(b, 10, 10);
341    
342    perturbMatrix(a, 10, 10, perturb_rows, perturb_vals, 5);
343    copyMatrix(a, b, 10, 10);
344    perturbMatrix(b, 10, 10, perturb_rows, perturb_vals, 5);
345    
346    multiplyMatrices(a, 10, 10, b, 10, c);
347    
348    printf("Stage 1 test testMultiplyMatrixC:...");
349    
350    if (!assertEqualMatrices(c, expected, 10, 10)) {
351        return;
352    }
353    printf("passed! :-)\n");
354}
355
356//added test case, try with non-square matrices and decimal points
357void testMultiplyMatrixD(void) {
358    double a[20] = {
359        0.00, 0.05, -0.04, 0.67,
360        -0.26, 0.75, 0.38, 0.43,
361        0.00 , -0.48, 0.07, 0.16,
362        0.65, 0.28, 0.43, 0.24,
363        0.20, 0.00, 0.00 , 1.00};
364    double b[8] = {
365        0.06, 0.00,
366        0.00, 0.34,
367        -0.49, 0.71,
368        -0.44, 0.00};
369    double expected[10] = {
370        -0.275200, -0.011400,
371        -0.391000, 0.524800,
372        -0.104700, -0.113500,
373        -0.277300, 0.400500,
374        -0.428000, 0.000000};
375    double c[10];
376    
377    multiplyMatrices(a, 5, 4, b, 2, c);
378    printf("Stage 1 test testMultiplyMatrixD:...");
379    if (!assertEqualMatrices(c, expected, 5, 2)) {
380        return;
381    }
382    printf("passed! :-)\n");
383}
384
385void testStage1(void) {
386    testMultiplyMatrixA();
387    testMultiplyMatrixB();
388    testMultiplyMatrixC();
389    testMultiplyMatrixD();
390    
391}
392
393/* ---------------------------------------- */
394
395void testMultiplyMatrixPtrA(void) {
396    double **a;
397    double **b;
398    double **c;
399    
400    a = (double **)malloc(sizeof(double *) * 10);
401    for (int i = 0; i < 10; i++) {
402        *(a + i) = (double *)malloc(sizeof(double) * 10);
403    }
404    b = (double **)malloc(sizeof(double *) * 10);
405    for (int i = 0; i < 10; i++) {
406        *(b + i) = (double *)malloc(sizeof(double) * 10);
407    }
408    generateRandomMatrixPtr(a, 10, 10);
409    generateIdentityMatrixPtr(b, 10, 10);
410    c = multiplyMatricesPtr(a, 10, 10, b, 10);
411    printf("Stage 2 testMultiplyMatrixPtrA:...");
412    if (!assertEqualMatricesPtr(a, c, 10, 10)) {
413        return;
414    }
415    memoryRelease(a, 10);
416    memoryRelease(b, 10);
417    memoryRelease(c, 10);
418    
419    printf("passed! :-)\n");
420}
421
422void testMultiplyMatrixPtrB(void) {
423    double **a;
424    double **b;
425    double **c;
426    
427    a = (double **)malloc(sizeof(double *) * 10);
428    for (int i = 0; i < 10; i++) {
429        *(a + i) = (double *)malloc(sizeof(double) * 10);
430    }
431    b = (double **)malloc(sizeof(double *) * 10);
432    for (int i = 0; i < 10; i++) {
433        *(b + i) = (double *)malloc(sizeof(double) * 10);
434    }
435    
436    generateRandomMatrixPtr(a, 10, 10);
437    generateIdentityMatrixPtr(b, 10, 10);
438    c = multiplyMatricesPtr(b, 10, 10, a, 10);
439    
440    printf("Stage 2 testMultiplyMatrixPtrB:...");
441    
442    if (!assertEqualMatricesPtr(a, c, 10, 10)) {
443        return;
444    }
445    
446    memoryRelease(a, 10);
447    memoryRelease(b, 10);
448    memoryRelease(c, 10);
449    
450    printf("passed! :-)\n");
451}
452
453void testMultiplyMatrixPtrC(void) {
454    double **a;
455    double **b;
456    double **c;
457    double **expected_ptr;
458    
459    /* these arrays are used only for test C */
460    uint32_t perturb_rows[5] = {2, 4, 6, 1, 7};
461    double perturb_vals[5] = {1.0, -1.0, 2.0, -2.5, 3.0};
462    double one[10] = {1, -10, 0, 0, 18, 0, -12, 3, 0, 0};
463    double two[10] = {0, -6.5, 0, 0, 10.5, 0, -7, 3, 0, 0};
464    double three[10] = {0, -10, 0, 0, 18, 0, -12, 3, 0, 0};
465    double four[10] = {0, -10, 0, 1, 18, 0, -12, 3, 0, 0};
466    double five[10] = {0, -10, 1, 0, 20, 0, -12, 3, 0, 0};
467    double six[10] = {0, -10, 0, 0, 18, 1, -12, 3, 0, 0};
468    double seven[10] = {0, -10, 0, 0, 20, 0, -13, 3, 0, 0};
469    double eight[10] = {0, -2.5, 0, 0, 4.5, 0, -3, 1, 0, 0};
470    double nine[10] = {0, -10, 0, 0, 18, 0, -12, 3, 1, 0};
471    double ten[10] = {0, -10, 0, 0, 18, 0, -12, 3, 0, 1};
472    
473    double *expected[] = {one, two, three, four, five,
474        six, seven, eight, nine, ten};
475    
476    expected_ptr = expected;
477    
478    a = (double **)malloc(sizeof(double *) * 10);
479    for (int i = 0; i < 10; i++) {
480        *(a + i) = (double *)malloc(sizeof(double) * 10);
481    }
482    b = (double **)malloc(sizeof(double *) * 10);
483    for (int i = 0; i < 10; i++) {
484        *(b + i) = (double *)malloc(sizeof(double) * 10);
485    }
486    
487    generateIdentityMatrixPtr(a, 10, 10);
488    perturbMatrixPtr(a, 10, 10, perturb_rows, perturb_vals, 5);
489    
490    generateIdentityMatrixPtr(b, 10, 10);
491    copyMatrixPtr(a, b, 10, 10);
492    perturbMatrixPtr(b, 10, 10, perturb_rows, perturb_vals, 5);
493    c = multiplyMatricesPtr(a, 10, 10, b, 10);
494    
495    printf("Stage 2 testMultiplyMatrixPtrC:...");
496    
497    if (!assertEqualMatricesPtr(c, expected_ptr, 10, 10)) {
498        return;
499    }
500    
501    memoryRelease(a, 10);
502    memoryRelease(b, 10);
503    memoryRelease(c, 10);
504    
505    printf("passed! :-)\n");
506}
507
508void testStage2(void) {
509    testMultiplyMatrixPtrA();
510    testMultiplyMatrixPtrB();
511    testMultiplyMatrixPtrC();
512}
513
514/* ---------------------------------------- */
515
516void testTransposeA(void) {
517    double **result;
518    double **input_ptr;
519    double **expected_ptr;
520    
521    double one_a[2] = {1, 2};
522    double two_a[2] = {3, 4};
523    double *input_a[] = {one_a, two_a};
524    input_ptr = input_a;
525    
526    double one_trans_a[2] = {1, 3};
527    double two_trans_a[2] = {2, 4};
528    
529    double *expected_a[] = {one_trans_a, two_trans_a};
530    expected_ptr = expected_a;
531    
532    
533    printf("Stage 3 testTransposeA:...");
534    result = transposeMatrix(input_ptr, 2, 2);
535    
536    if (!assertEqualMatricesPtr(result, expected_ptr, 2, 2)) {
537        return;
538    }
539    
540    memoryRelease(result, 2);
541    printf("passed! :-)\n");
542}
543
544void testTransposeB(void) {
545    double **result;
546    double **input_ptr;
547    double **expected_ptr;
548    
549    double one_b[3] = {1, 2, 3};
550    double two_b[3] = {4, 5, 6};
551    double three_b[3] = {7, 8, 9};
552    double *input_b[] = {one_b, two_b, three_b};
553    input_ptr = input_b;
554    
555    double one_trans_b[3] = {1, 4, 7};
556    double two_trans_b[3] = {2, 5, 8};
557    double three_trans_b[3] = {3, 6, 9};
558    
559    double *expected_b[] = {one_trans_b, two_trans_b, three_trans_b};
560    expected_ptr = expected_b;
561    
562    printf("Stage 3 testTransposeB:...");
563    result = transposeMatrix(input_ptr, 3, 3);
564    if (!assertEqualMatricesPtr(result, expected_ptr, 3, 3)) {
565        return;
566    }
567    
568    memoryRelease(result, 3);
569    printf("passed! :-)\n");
570}
571
572void testTransposeC(void) {
573    double **result;
574    double **input_ptr;
575    double **expected_ptr;
576    
577    double one_c[3] = {1, 2, 3};
578    double two_c[3] = {4, 5, 6};
579    double *input_c[] = {one_c, two_c};
580    input_ptr = input_c;
581    
582    double one_trans_c[2] = {1, 4};
583    double two_trans_c[2] = {2, 5};
584    double three_trans_c[2] = {3, 6};
585    
586    double *expected_c[] = {one_trans_c, two_trans_c, three_trans_c};
587    expected_ptr = expected_c;
588    
589    printf("Stage 3 testTransposeC:...");
590    result = transposeMatrix(input_ptr, 2, 3);
591    if (!assertEqualMatricesPtr(result, expected_ptr, 3, 2)) {
592        return;
593    }
594    
595    memoryRelease(result, 3);
596    
597    printf("passed! :-)\n");
598}
599
600void testStage3(void) {
601    testTransposeA();
602    testTransposeB();
603    testTransposeC();
604}
605
606int main(int argc, char **argv) {
607    int i;
608    
609    /** Run only a specific test */
610    for (i = 1; i < argc; i++) {
611        if (strcmp("testMultiplyMatrixA", argv[i]) == 0) {
612            testMultiplyMatrixA();
613        } else if (strcmp("testMultiplyMatrixB", argv[i]) == 0) {
614            testMultiplyMatrixB();
615        } else if (strcmp("testMultiplyMatrixC", argv[i]) == 0) {
616            testMultiplyMatrixC();
617        } else if (strcmp("testMultiplyMatrixD", argv[i]) == 0) {
618            testMultiplyMatrixD();
619        } else if (strcmp("testTransposeA", argv[i]) == 0) {
620            testTransposeA();
621        } else if (strcmp("testTransposeB", argv[i]) == 0) {
622            testTransposeB();
623        } else if (strcmp("testTransposeC", argv[i]) == 0) {
624            testTransposeC();
625        } else if (strcmp("testMultiplyMatrixPtrA", argv[i]) == 0) {
626            testMultiplyMatrixPtrA();
627        } else if (strcmp("testMultiplyMatrixPtrB", argv[i]) == 0) {
628            testMultiplyMatrixPtrB();
629        } else if (strcmp("testMultiplyMatrixPtrC", argv[i]) == 0) {
630            testMultiplyMatrixPtrC();
631        } else {
632            printf("ERROR: Incorrect test name %s\n", argv[i]);
633            exit(1);
634        }
635    }
636    
637    if (argc == 1) {
638        testStage1();
639        testStage2();
640        testStage3();
641    }
642    
643    return 0;
644}