====== Solution C pour l'algorithme de Karatsuba ======

[[nsi:tds:maths:karatsuba|TD décrivant l'algorithme.]]

<code c>
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // pour strlen

#define N 1000

typedef unsigned char* Kdigits;
typedef struct Knumber {
    char signe;
    Kdigits pdigits;
    unsigned long size;
} Knumber;

/* déclaration entêtes */
Knumber* creer_kempty();
void append(Knumber* k, unsigned char c);
Knumber* from_str(char* strvalue);
void free_knumber(Knumber* k);
void transfert_in(Knumber* source, Knumber* cible);
Knumber* copy(Knumber* k);
void change_sign(Knumber* k);
char isgreater(Knumber* k1, Knumber* k2);
void upsize(Knumber* k, unsigned long newsize);
void egalize_size(Knumber* k1, Knumber* k2);
void sub_digits(Kdigits pd1, Kdigits pd2, unsigned long size);
unsigned char add_digits(Kdigits pd1, Kdigits pd2, unsigned long size);
void add(Knumber* k1, Knumber* k2);
void sub(Knumber* k1, Knumber* k2);
void lshift(Knumber* k, unsigned long s);
void rshift(Knumber* k, unsigned long s);
Knumber* MSB(Knumber* k, unsigned long m);
Knumber* LSB(Knumber* k, unsigned long m);
Knumber* mult_rec(Knumber* k1, Knumber* k2);
Knumber* mult(Knumber* k1, Knumber* k2);
void kdisplay(Knumber* k);

/* déclaration des contenues des fonctions */

Knumber* creer_kempty()
{
    /* crée un pointeur sur Knumber non initialisé */
    Kdigits pdigits = malloc(N*sizeof(*pdigits));
    if (pdigits == NULL)
    {
        printf("creer_empty: erreur création Kdigits.\n");
        exit(1);
    }
    Knumber* k = malloc(sizeof(Knumber));
    if (k == NULL)
    {
        printf("creer_empty: erreur création Knumber.\n");
        exit(1);
    }
    k->signe = 0;
    k->pdigits = pdigits;
    k->size = 0;
    return k;
}

void append(Knumber* k, unsigned char c)
{
    /* ajoute c au bout de k.digits, augmentant k.size de 1*/
    if (k->size >= N)
    {
        printf("append: dépassement de capacité.\n");
        exit(1);
    }
    k->pdigits[k->size] = c;
    k->size = k->size + 1;
}

Knumber* from_str(char* strvalue)
{
    /* transforme la strvalue en Knumber */
    unsigned long n = strlen(strvalue);
    Knumber* k = creer_kempty();
    for (unsigned long i=n; i>0; i--){
        unsigned char d = strvalue[i-1] - '0';
        append(k, d);
    }
    return k;
}

void free_knumber(Knumber* k)
{
    /* libère la mémoire occupée par le Knumber k */
    if (k->pdigits != NULL)
    {
        free(k->pdigits);
        k->pdigits = NULL;
    }
}

void transfert_in(Knumber* source, Knumber* cible)
{
    /* déplace le contenu de source vers cible et libère source */
    free(cible->pdigits);
    cible->pdigits = source->pdigits;
    cible->signe = source->signe;
    cible->size = source->size;
    source->pdigits = NULL;
    free_knumber(source);
}


Knumber* copy(Knumber* k)
{
    /* crée un Knumber copie de k*/
    Knumber* h = creer_kempty(k->size);
    h->size = k->size;
    h->signe = k->signe;
    for (unsigned long i =0; i<k->size; i++){
        h->pdigits[i] = k->pdigits[i];
    }
    return h;
}

void change_sign(Knumber* k)
{
    /* change le signe */
    k->signe = 1-k->signe;
}

char isgreater(Knumber* k1, Knumber* k2)
{
    /* renvoie 1 si |k2| >= |k1|, 0 sinon */
    if (k1->size > k2->size)
    {
        for (unsigned long i = k1->size-1; i>=k2->size; i--)
        {
            if (k1->pdigits[i] > 0)
            {
                return 1;
            }
        }
    } else  if (k1->size < k2->size)
    {
        for (unsigned long i = k2->size-1; i>=k1->size; i--)
        {
            if (k2->pdigits[i] > 0)
            {
                return 0;
            }
        }
    }
    for (unsigned long i = k1->size; i>0; i--)
    {
        char d1 = k1->pdigits[i-1];
        char d2 = k2->pdigits[i-1];
        if (d1 > d2)
        {
            return 1;
        }
        if (d2 > d1)
        {
            return 0;
        }
    }
    /* cas d'égalité */
    return 1;
}

void upsize(Knumber* k, unsigned long newsize)
{
    /* augmente la taille de k en remplissant par des 0 */
    if (newsize < k->size)
    {
        printf("upsize : newsize doit être >= k.size.\n");
        exit(1);
    }
    for (unsigned long i =k->size; i<newsize; i++){
        k->pdigits[i] = 0;
    }
    k->size = newsize;
}

void egalize_size(Knumber* k1, Knumber* k2)
{
    /* aligne la taille de la plus petite sur la plus grande */
    if (k1->size < k2->size)
    {
        upsize(k1, k2->size);
    }
    else if (k1->size > k2->size)
    {
        upsize(k2, k1->size);
    }
}

void sub_digits(Kdigits pd1, Kdigits pd2, unsigned long size)
{
    /* modifie pd1 pour qu'il reçoive la différence *pd1 - *pd2 */
    unsigned char retenue = 0;
    for (unsigned long i=0; i<size; i++)
    {
        retenue = retenue + pd2[i];
        if (pd1[i] < retenue)
        {
            pd1[i] = 10 + pd1[i] - retenue;
            retenue = 1;
        }
        else
        {
            pd1[i] = pd1[i] - retenue;
            retenue = 0;
        }
    }
}

unsigned char add_digits(Kdigits pd1, Kdigits pd2, unsigned long size)
{
    /* modifie pd1 pour qu'il reçoive la somme *pd1 + *pd2*/
    unsigned char retenue = 0;
    for (unsigned long i=0; i<size; i++)
    {
        retenue = pd1[i] + pd2[i] + retenue;
        pd1[i] = retenue % 10;
        retenue = retenue / 10;
    }
    return retenue;
}

void add(Knumber* k1, Knumber* k2)
{
    /* Modifie k1 pour qu'il contienne k1 + k2 */
    if (k1->size != k2->size){
        egalize_size(k1, k2);
    }

    
    if (k1->signe != k2->signe)
    {
        if (isgreater(k1, k2) == 1)
        {
            sub_digits(k1->pdigits, k2->pdigits, k1->size);
        }
        else
        {
            Knumber* h = copy(k2);
            sub_digits(h->pdigits, k1->pdigits, h->size);
            transfert_in(h, k1);
        }
    } else {
        unsigned char r = add_digits(k1->pdigits, k2->pdigits, k1->size);
        if (r > 0)
        {
            append(k1, r);
        }
    }       
}

void sub(Knumber* k1, Knumber* k2)
{
    /* modifie k1 qui contiendra k1 - k2 */
    if (k1->size != k2->size){
        egalize_size(k1, k2);
    }
    if (k1->signe == k2->signe)
    {
        if (isgreater(k1, k2) == 1)
        {
            sub_digits(k1->pdigits, k2->pdigits, k1->size);
        }
        else
        {
            Knumber* h = copy(k2);
            sub_digits(h->pdigits, k1->pdigits, h->size);
            transfert_in(h, k1);
            change_sign(k1);
        }
    } else {
        unsigned char r = add_digits(k1->pdigits, k2->pdigits, k1->size);
        append(k1, r);
    }
}

void lshift(Knumber* k, unsigned long s)
{
    /* correspond à multiplier par 10^s */
    if (s == 0)
    {
        return;
    }
    unsigned long newsize = k->size + s;
    if (newsize > N)
    {
        printf("lshift: dépassement de capacité.\n");
        exit(1);
    }
    for (unsigned long i=newsize - 1; i >= s; i--){
        k->pdigits[i] = k->pdigits[i-s];
    }
    for (unsigned long i=0; i < s; i++){
        k->pdigits[i] = 0;
    }
    k->size = newsize;
}

void rshift(Knumber* k, unsigned long s)
{
    /* correspond à diviser par 10^s */
    if (s > k-> size)
    {
        k->size = 0;
        return;
    }
    unsigned long newsize = k->size - s;
    for (unsigned long i=0; i<newsize; i++){
        unsigned long ips = i + s;
        k->pdigits[i] = k->pdigits[ips];
    }
    k->size = newsize;
}

Knumber* MSB(Knumber* k, unsigned long m)
{
    /* crée une copie en tronquant les m digits LSB */
    if (m > k->size)
    {
        printf("MSB : m doit être <= à k.size.\n");
        exit(1);
    }
    Knumber* a = creer_kempty();
    a->size = k->size - m;
    for (unsigned long i=0; i<a->size; i++){
        a->pdigits[i] = k->pdigits[i+m];
    }
    return a;
}

Knumber* LSB(Knumber* k, unsigned long m)
{
    /* crée une copie ne gardant que les m digits LSB */
    if (m > k->size)
    {
        printf("LSB : m doit être <= à k.size.\n");
        exit(1);
    }
    
    Knumber* a = creer_kempty();
    for (unsigned long i=0; i<m; i++)
    {
        a->pdigits[i] = k->pdigits[i];
    }
    a->size = m;
    return a;
}

Knumber* mult_rec(Knumber* k1, Knumber* k2)
{
    char signe;
    if (k1->signe == k2->signe)
    {
        signe = 0;
    }
    else
    {
        signe = 1;
    }
    if (k1->size == 1){
        Knumber* h = creer_kempty();
        h->signe = signe;
        unsigned char p = k1->pdigits[0] * k2->pdigits[0];
        h->pdigits[0] = p % 10;
        h->pdigits[1] = p / 10;
        h->size = 2;
        return h;
    }
    unsigned long m = k1->size / 2;
    Knumber* a = MSB(k1, m);
    Knumber* b = LSB(k1, m);
    Knumber* c = MSB(k2, m);
    Knumber* d = LSB(k2, m);

    Knumber* ac = mult_rec(a, c);
    Knumber* bd = mult_rec(b, d);

    sub(a, b); // a contient a - b
    sub(d, c); // d contient d - c
    free_knumber(b);
    free_knumber(c);
    Knumber* crossed = mult_rec(a, d);
    free_knumber(a);
    free_knumber(d);
    add(crossed, ac);
    add(crossed, bd);
    lshift(crossed, m);
    lshift(ac, 2*m);
    add(crossed, ac);
    free_knumber(ac);
    add(crossed, bd);
    free_knumber(bd);
    if (signe == 1)
    {
        change_sign(crossed);
    }
    return crossed;
}

Knumber* mult(Knumber* k1, Knumber* k2)
{
    /* produit le Knumber k1*k2 par l'algo de Karastuba */
    egalize_size(k1, k2);
    return mult_rec(k1, k2);
}

void kdisplay(Knumber* k)
{
    if (k->size == 0)
    {
        printf("0\n");
        return;
    }
    if (k->signe == 1)
    {
        printf("-");
    }
    unsigned char started = 0;
    for (unsigned long i=k->size-1; i>=1; i--)
    {
        if (k->pdigits[i] > 0)
        {
            started = 1;
        }
        if (started > 0)
        {
            printf("%d", k->pdigits[i]);
        }
    }
    printf("%d\n", k->pdigits[0]);
}


int main(int argc, char *argv[])
{
    if (argc != 3) {
        printf("Vous devez préciser deux entiers.nExemple : %s 42536452 97524242\n", argv[0]);
        exit(1);
    }
    
    Knumber* a = from_str(argv[1]);
    Knumber* b = from_str(argv[2]);
    Knumber* p = mult(a, b);
    kdisplay(p);
    free_knumber(a);
    free_knumber(b);
    free_knumber(p);
    exit(0);
}
</code>