Início / user-15270050

4DescarTes's questions

Martin Hope
4DescarTes
Asked: 2023-08-18 19:50:54 +0800 CST
  • 7

Estou tentando encontrar uma maneira mais rápida do que a multiplicação regular. Eu executo o código no vscode e, pelo que posso ver, não tenho nenhuma otimização habilitada. Eu também tentei gcc -O0 _.c -o _ mas ainda obtive o mesmo resultado. Eu também escrevo o mesmo código em M0 Assembly, mas a multiplicação regular foi novamente a mais rápida. Há algo que estou perdendo, talvez com cálculos de tempo, ou a multiplicação regular é realmente o caminho mais rápido?

#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

uint64_t karatsuba(uint64_t x, uint64_t y) {
    if (x < 10 || y < 10) {
        return x * y;
    }

    int n = max(log10(x) + 1, log10(y) + 1) / 2;

    uint64_t a = x / (uint64_t)pow(10, n);
    uint64_t b = x % (uint64_t)pow(10, n);
    uint64_t c = y / (uint64_t)pow(10, n);
    uint64_t d = y % (uint64_t)pow(10, n);

    uint64_t ac = karatsuba(a, c);
    uint64_t bd = karatsuba(b, d);
    uint64_t ad_bc = karatsuba(a + b, c + d) - ac - bd;

    return ac * (uint64_t)pow(10, 2 * n) + ad_bc * (uint64_t)pow(10, n) + bd;
}

uint64_t multiply(uint64_t x, uint64_t y) {
    uint64_t result = 0;

    while (x > 0) {
        if (x & 1) {
            result += y;
        }
        x >>= 1;
        y <<= 1;
    }

    return result;
}

int main() {
    uint64_t i = UINT64_MAX;
    uint64_t j = 10;

    clock_t t;
    clock_t m;
    clock_t l;
    int n = 9999999;

    t = clock();
    for (int k = 0; k < n; k++) {
        multiply(i, j);
    }
    t = clock() - t;
    double time_taken = ((double)t) / CLOCKS_PER_SEC;
    printf("Bit Manipulation Multiplication took %.15f seconds to execute in average\n", time_taken / n);

    m = clock();
    for (int k = 0; k < n; k++) {
        uint64_t k_result = i * j;
    }
    m = clock() - m;
    double time_taken2 = ((double)m) / CLOCKS_PER_SEC;
    printf("Regular Multiplication took %.15f seconds to execute in average\n", time_taken2 / n);

    l = clock();
    for (int k = 0; k < n; k++) {
        karatsuba(i, j);
    }
    l = clock() - l;
    double time_taken3 = ((double)l) / CLOCKS_PER_SEC;
    printf("Karatsuba Multiplication took %.15f seconds to execute in average\n", time_taken3 / n);

    printf("\nResults:\n");
    printf("Bit Manipulation Result: %llu\n", multiply(i, j));
    printf("Regular Multiplication Result: %llu\n", i * j);
    printf("Karatsuba Multiplication Result: %llu\n", karatsuba(i, j));

    return 0;
}
c