[P&AM Lab] Постановка задачи по KML

[Grigoriy A. Sitkarev]

Ещё кое-что упустил из виду. Уж простите.

Закомментировал ненужные строки в этой функции, мы же уже посчитали z0 и 
z2 на предыдущем шаге.

Добавлю ещё следующее. В функции kmul_basic() вычисление z1 уже не 
вмещается в машинную арифметику 32-х разрядной машины, т.к. x0..y1 числа 
по 32 бита, их сумма и произведение будет больше чем 64 бита. Поэтому 
там эти операции уже как с bignum должны быть сделаны. Числа z2 и z0 
вмещаются в u_int64_t, поэтому вероятно стоит какую-то функцию потом 
написать чтобы из bignum вычитать/прибавлять u_int64_t без необходимости 
представления z0 и z1 в bignum (видимо что-то вроде bignum_add_int() и 
bignum_sub_int() и т.д.).

Экономия достигается за счёт того что после того как мы посчитали z0 и 
z1 во внешней функции рекурсивной длинное умножение, чтобы получить z1, 
выполняется для чисел почти в два раза меньше порядком чем исходное. А 
т.к. у нас длинное умножение O(n^2) -- эффект будет ощущаться на очень 
больших числах.

Надо искать дальше где у нас неточности. Всё равно это только наброски.

8<--------------------------------------------------------------------

function
kmul_recursive(xy [out], x1 [in], y1 [in], x0 [in], y0 [in], n [in])
{
     temp z0, z1, z2;
     m = n / 2;

     if (m <= basic_size) {
         kmul_basic(z2, x1+m, y1+m, x1, y1, m);
         kmul_basic(z0, x0+m, y0+m, x0, y0, m);
     } else {
         kmul_recursive(z2, x1+m, y1+m, x1, y1, m);
         kmul_recursive(z0, x0+m, y0+m, x0, y0, m);
     }

     /* z2 = x1 * y1; */
     /* z0 = x0 * y0; */
     z1 = (x1 + x0)*(y1 + y0) - z2 - z0;

     shift_left(z2, 2*m);
     shift_left(z1, m);
     xy = add3(z0, z1, z2);
}

8<-------------------------------------------------------------------

--
Г.А.

07.03.2011 12:16, Grigoriy A. Sitkarev пишет:
> Заметили опечатки.
>
> Исправленный псевдо-код и портянка со схемой.
>