Rename and cleanup

2 files changed, 105 insertions, 0 deletions

diff --git a/sem3/algo/mm3/multiply.c b/sem3/algo/mm3/multiply.c
new file mode 100644
index 0000000..e454de3
--- /dev/null
+++ b/sem3/algo/mm3/multiply.c
@@ -0,0 +1,56 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <time.h>
+
+uint64_t mult(uint64_t x, uint64_t y, unsigned int bits) {
+	/* Check if they expect more than 64 bits. */
+	if( bits > 64 ) {
+		printf("Sorry we cant handle higher than 64 bits\n");
+		exit(1);
+	} else if(bits <= 1) {
+		return x && y;
+	}
+
+	unsigned int newBits = bits >> 1;
+
+#if DO_PRINT == 1
+	printf("\n\n bits: %u, New bits: %u\n", bits, newBits);
+#endif 
+
+	/* Split up into to */
+	uint32_t halvMask = ((uint64_t)1 << newBits) - 1;
+#if DO_PRINT == 1
+	printf("Using mask 0x%08X\n", halvMask);
+#endif 
+	uint32_t a = (x >> (newBits)) & halvMask;
+	uint32_t b = x & halvMask;
+	uint32_t c = (y >> (newBits)) & halvMask;
+	uint32_t d = y & halvMask;
+
+#if DO_PRINT == 1
+	printf("A: 0x%08X, B: 0x%08X, C: 0x%08X, D: 0x%08X\n", a, b, c, d);
+#endif 
+
+	return (mult(a, c, newBits) << bits) + ((mult(a, d, newBits) + mult(b, c, newBits)) << newBits) + mult(b, d, newBits);
+
+}
+
+
+int main(void) {
+
+	uint32_t a = 0xFFFFFF;
+	uint8_t  b = 55;
+	uint64_t res;
+
+	clock_t begin = clock();
+	res = mult(a, b, 64);
+	clock_t end = clock();
+
+	printf("Result: %lld\n", res);
+
+	clock_t diff = end - begin;
+	printf("Took %d which is %f s\n", diff, (double)diff/CLOCKS_PER_SEC);
+	
+	return 0;
+}
diff --git a/sem3/algo/mm3/opgaver.md b/sem3/algo/mm3/opgaver.md
new file mode 100644
index 0000000..a6e560c
--- /dev/null
+++ b/sem3/algo/mm3/opgaver.md
@@ -0,0 +1,49 @@
+# Opgave 1
+
+## Exercise 9.2
+
+**T(n) = 3T(n/2) + n**
+
+a = 3
+b = 2
+d(n) = n
+
+a ? d(b) -> 3 > 2
+
+Svaret er derfor O(n^log2(3)) = O(n^1.59)
+
+**T(n) = 3T(n/2) + n^2**
+
+3 ? 2^2 -> 3 < 4
+
+d(n) = n^2 hvilket betyder at O(n^2)
+
+**T(n) = 8T(n/2) + n^2**
+
+8 ? 2^3 -> 8 = 8
+
+d(n) = n^3 hvilket betyder at O(n^3 log2(n))
+
+## Evercise 9.3
+
+**T(n) = 4T(n/3) + n**
+
+a = 4
+b = 3
+d(n) = n
+
+4 ? 3 -> 4 > 3
+
+Derfor er svaret O(n^log3(4)) = O(n^1.26)
+
+**T(n) = 4T(n/3) + n^2**
+
+4 ? 3^2 -> 4 < 9
+
+d(n) = n^2 hvilket betyder at O(n^2)
+
+**T(n) = 9T(n/3) + n^2**
+
+9 ? 3^2 -> 9 = 9
+
+d(n) = n^2 hvilket betyder at O(n^2 log2(n))