Práctica 3 3/5[AA] - Daniel Cruz García

Karatsuba – Ofman.c

#include <stdlib.h>
#include <stdio.h>
#include "tiempo.h"

int maxim(int a, int b){
    if(a<b) return b;
    else return a;
}

long long int Power(int x, int y) {
    if (y == 0) return 1;
    else
        if (y == 1) return x;
        else return x*Power(x, y-1);
}
  
int Digitos (int n, int dig) {
    if (n < 10) return (dig+1);
    else {
        dig++;
        return Digitos(n/10, dig);
    }
}
 
long long int ultimos(int digitos, int numero) {
    return numero % Power(10, digitos);
}

long long int primeros(int digitos, int numero) {
    return numero/Power(10, digitos);
}
 
long long int multiplica (int u, int v) {
    int dig1=0, dig2=0;
    int numDigitos = maxim(Digitos(u, dig1), Digitos(v, dig2));

    if (numDigitos <= 3) return u*v;

    numDigitos = (numDigitos / 2) + (numDigitos % 2);
    long long int w = primeros(numDigitos, u);
    long long int x = ultimos(numDigitos, u);
    long long int y = primeros(numDigitos, v);
    long long int z = ultimos(numDigitos, v);

    long long int p=multiplica(w, y);
    long long int q=multiplica(x, z);
    long long int wMasx = w + x;
    long long int zMasy = z + y;
    
    long long int r=multiplica(wMasx, zMasy);
    return Power(10, 2*numDigitos)*p+Power(10, numDigitos)*(r-p-q)+q;
}
 
int main () {
    long long int a,b;
    double utime0, stime0, wtime0,utime1, stime1, wtime1;
    printf("Meteme dos numeros :V [46341 <- ?]\n");
    printf("Numero 1: "); scanf("%lld",&a); 
    printf("Numero 2: "); scanf("%lld",&b);
    uswtime(&utime0, &stime0, &wtime0);
    printf("Si multiplicas ambos numeros el resultado seria: %lld\n",multiplica(a,b));
    uswtime(&utime1, &stime1, &wtime1);
    printf("real (Tiempo total)  %.10f s\n",  wtime1 - wtime0);
    return 0;
}