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

[Grigoriy A. Sitkarev]

Приветствую всех.

После субботней встречи я немного подумал и решил что пожалуй 
рекурсивная схема подойдёт для решения наших задач. Ниже некоторые 
соображения по этому поводу. Я нарисовал картинку чтобы было понятнее 
почему это будет работать и составил примерный псевдокод, чтобы было 
ясно как это реализовывать.

Попробуем поставить задачу по реализации алгоритма умножения А.Карацубы.

Сперва сделаем прикидку по глубине рекурсии.

Пусть например числа закодированы 2^20 битами (1048576 бит) а базовыми 
числами примем тогда 2^5 (32 бита), что соответствует возможностям любой 
32-х разрядной машины которая будет производить умножение 32-х битных 
чисел аппаратно. Тогда для того чтобы рекурсивно дойти до базового 
умножения от верхушки до низа нам потребуется 20-5=15 рекурсий 
(lb(2^20)-lb(32)=20-5=15), что можно считать приемлемым. Насколько 
большим окажется это число в десятичном виде? Посчитаем.

    lg(2^(2^20))=2^20*lg(2) ~ 315653 десятичных разряда.

Пусть например, у нас рекурсия будет глубиной 27, это тоже приемлемо, 
тогда мы сможем умножать числа состоящие из:

    lg(2^(2^32))=2^32*lg(2) ~ 1292913986 десятичных разрядов.

Для наших практических задач этого более чем достаточно. И даже если 
потребуются числа больше, рекурсия вполне допустима глубже.

После того как будет работать рекурсивный алгоритм, можно задуматься об
оптимизации. Ясно что нужно снижать накладные затраты на промежуточные 
операции, организацию рекурсивных вызовов, оптимизировать операции 
сдвигов. Для хранения разрядов промежуточных переменных, используемых в 
вычислениях, вероятно будет целесообразным выделять память в стеке через 
alloca(3) а не через malloc(3). Тогда следует добавить флаг в структуру 
bignum, который указывает на то что не нужно высвобождать память в поле val.

Дальнейшая оптимизация будет заключаться в том чтобы устранить рекурсию 
на нижних ветвях совершенно, выполняя умножения чисел прямо в функции, 
без рекурсии. Тогда появятся функции вроде kmul_128, kmul_256, kmul_512 
и т.д. По сути это тот-же самый рекурсивный вариант но в нём будут 
отсутствовать накладные расходы на передачу аргументов в стек/регистры и 
обратно при рекурсивном вызове.

Ещё раз стоит сказать что задача оптимизации откладывается на самый 
последний момент. Сначала следует получить рабочие, надёжные и ясные 
алгоритмы с которыми можно будет делать сравнение и использовать как 
прототип.

В псевдокоде задача выглядит приблизительно так:

xy: результат умножения двух чисел, x*y
x1: указатель на разряды в верхней половине числа x
y1: указатель на разряды в верхней половине числа y
x0: указатель на разряды в нижней половине числа x
y0: указатель на разряды в нижней половине числа y
n:  количество бит из которых состоит число x и число y

Вспомогательные функции для bignum:

shift_left: осуществляет сдвиг влево (в сторону больших значений)
add3:	    суммирует три числа

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

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

	z2 = x1 * y1;
	z0 = x0 * y0;
	z1 = z2 + z0;
	
	shift_left(z2, 2*m);
	shift_left(z1, m);
	xy = add3(z0, z1, z2);
}

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 = z2 + z0;
	
	shift_left(z2, 2*m);
	shift_left(z1, m);
	xy = add3(z0, z1, z2);
}

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

Стоит дать некоторые пояснения. Здесь прибавление к x1,y1,x0,y0 целого 
числа m позволяет передать в функции половинки от значений x1,y1,x0,y0 
(в битах), как будто это смещения к указателям, но заданные в битах.

В функции kmul_recursive для промежуточных вычислений используются 
bignum, для удобства они заменены обычной арифметикой (всё-таки у нас 
псевдокод).

Жду комментариев и поправок. Я мог что-то упустить из виду.

--
Г.А.


----------- следущая часть -----------
A non-text attachment was scrubbed...
Name: kml.ps.gz
Type: application/x-gzip
Size: 50470 bytes
Desc: отсутствует
URL: <http://amplab.syktsu.ru/pipermail/lab/attachments/20110307/442dc1d7/attachment.bin>