Karatsuba неправильный результат

Question

Я пытаюсь реализовать алгоритм karatsuba на языке c, но, к сожалению, это дает мне неправильный результат.

Вот мой с функцией:

Real* multiplication(const Real* a, const Real* b){ 
    Real* ret; 

    ............ 

    z0=multiplication(low1, low2); 
    assert(z0!=NULL); 

    z2=multiplication(high1, high2); 
    assert(z2!=NULL); 

    z1=subtract(subtract(multiplication(add(low1, high1), add(low2, high2)), z2), z0); 
    assert(z1!=NULL); 

    assert((tmpA->taille == tmpB->taille) && (tmpA->taille%2==0)); 

    ret=add(add(powerTen(z2, tmpA->size), powerTen(z1, tmpA->size/2)), z0); 
    assert(ret!=NULL); 

    ....... 

    return ret; 
} 

Я создал структуру:

struct Real{ 
     int* nb; 
     int size; 
     int neg; //1=negative 0=positiv 
    } 

Итак, в нескольких словах, я использовал реализацию псевдо-кода из wikipedia, и функция запускает y, глядя на размер двух чисел (если есть < 2), и если он не исправляет его, выравнивая их и добавляя нуль спереди, если размер четный. Помимо этого, это в основном алгоритм псевдокода.

LOW1 и HIGH1 соответствуют нижней части и высокой части LOW2 и HIGH2 соответствует нижней части и высокой части

Заранее спасибо за весь ответ

Answer 1

Вот план о том, как вы отлаживаете.

После каждого шага WRITE DOWN, какой ответ вы ожидали от компьютера.
Затем компьютер покажет вам, какой ответ он на самом деле получил.

Ищите шаг, на котором ожидаемое вами отличается от того, что оно на самом деле получило.

Real* multiplication(const Real* a, const Real* b){ 
    Real* ret; 
    [...] 
    z0=multiplication(low1, low2); 
    assert(z0!=NULL); 
    printf("Step #1: I expected 5, but I actually got %d\n", z0); 

    z2=multiplication(high1, high2); 
    printf("Step #2: I expected 7, but I actually got %d\n", z2); 
    assert(z2!=NULL); 

    z1=subtract(subtract(multiplication(add(low1, high1), add(low2, high2)), z2), z0); 
    printf("Step #3: I expected 3, but I actually got %d\n", z1); 
    assert(z1!=NULL); 

    assert((tmpA->taille == tmpB->taille) && (tmpA->taille%2==0)); 

    ret=add(add(powerTen(z2, tmpA->size), powerTen(z1, tmpA->size/2)), z0); 
    printf("Step #4: I expected 30, but I actually got %d\n", ret); 
    assert(ret!=NULL); 
    [...]  
    return ret; 
} 

Примечание: Вы должны настроить PRINTF заявления, так как я не знаю, какие ценности ожидать, ни как печатать переменные z0, z1 и z2, потому что вы не ставили достаточно подробно в вашем вопросе.