diff options
Diffstat (limited to 'sem1/algo/mm3')
-rw-r--r-- | sem1/algo/mm3/multiply.c | 56 | ||||
-rw-r--r-- | sem1/algo/mm3/opgaver.md | 49 |
2 files changed, 0 insertions, 105 deletions
diff --git a/sem1/algo/mm3/multiply.c b/sem1/algo/mm3/multiply.c deleted file mode 100644 index e454de3..0000000 --- a/sem1/algo/mm3/multiply.c +++ /dev/null @@ -1,56 +0,0 @@ -#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/sem1/algo/mm3/opgaver.md b/sem1/algo/mm3/opgaver.md deleted file mode 100644 index a6e560c..0000000 --- a/sem1/algo/mm3/opgaver.md +++ /dev/null @@ -1,49 +0,0 @@ -# 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)) |