41.3. АРИФМЕТИКА ДВОЙНОЙ И МНОГОКРАТНОЙ ТОЧНОСТИ


    Сложение и Вычитание 
 

Сложение:
	A + B  :  result[high] = A[high] + B[high] + carry_add(A[low],B[low])
		  result[low]  = A[low]  + B[low]

Вычитание:
	A + B  :  result[high] = A[high] - B[high] - carry_sub(A[low],B[low])
		  result[low]  = A[low]  - B[low]


Для начала посмотрим на Carry Flag и команду Addition with Carry.

	Пусть EBX указывает на первое число
	Пусть ECX указывает на второе число
	Пусть EDX указывает на результат

  

	mov	eax,[ebx]
	add	eax,[ecx]
	mov	[edx],eax
	mov	eax,[ebx+4]
	adc	eax,[ecx+4]	; Вот зачем надо сложение с CF
	mov	[edx+4],eax


	mov	eax,[ebx]
	sub	eax,[ecx]
	mov	[edx],eax
	mov	eax,[ebx+4]
	sbb	eax,[ecx+4]	; Вот зачем нужно вычитание с CF
	mov	[edx+4],eax


  
  
  


Соответсвенно повторяется нужное число раз, если число большое:
  

Как мы помним для дополнительного кода сложение/вычитание одинаково для
знаковых и беззнаковых чисел.



    Умножение 
 

Умножение повышенной точности
Умножаем по частям и складываем частные результаты с учетом их позиций.
  

Беззнакое умножение - берем чисто частные произведения, знак не расширяем
  

Знаковое умножение - каждое частное произведение знаково расширяется до
максимального размера.
  

Упрошенные случаи - умножение на число половинного размера
(Количество частных произведений сокращается).
  
  

В случае если нам надо число той же разрядности что и опреанды -
имеем multiply low, во-первых одно из частных умножений делать не надо,
соответсвенно на единицу уменьшается число чаcтных сумм,
во вторых эта операция одинакова и для знаковых и для беззнаковых чисел.
  
  

Еще раз проиллюстируем важность оптимизации при умножение на числа младшего размера.

	--------------------------------------
	Operand	Operand	Result	MULS	ADDS
	--------------------------------------
	4	4	8	16	15
	4	2	8	8	7
	4	1	8	4	3
	--------------------------------------

Поэтому надо пользоваться каждым случаем для минимизации размера операндов для
умножения.
	

  
  
  



    Умножение Карацубы 
 

Смысл умножение Карацубы - сократить число вложенных умножений,
заменив их на более дешевые операции сложения/вычитания.

Пусть нам надо перемножить (A1,A0) на (B1,B0)

В обычном случае умножения столбиком:

	A*B = (A1*B1) * 2^2n  +
	      (A0*B1) * 2^n   +
	      (A1*B0) * 2^n   +
	      (A0*B0)

имеем 4 умножения.

Идея лежащая в основе метода:
Хочеться получить A0*B1 + A1*B0 сразу, как это можно сделать:

Рассмотрим произведение:
	(A0 + A1) * (B0 + B1) =

	A0 * B0 + A0 * B1 + A1 * B0 + A1 * B1
                  =======   =======

подчеркнуты части которые нам нужны.

Соответсвенно
	A0 * B1 + A1 * B0 = (A0 + A1)*(B0 + B1) - A0*B0 - A1*B1.

Но фишка в том, что в процессе умножения мы так и так вычисляем
A0 * B0  и  A1 * B1.


Рассчитаем:
	X = A0 * B0
	Y = (A0 + A1) * (B0 + B1)
	Z = X1 * Y1

Собственно результат будет:

	Z * 2^2n + (Y - Z -A)*2^n + X 


На самом деле есть ньюансы:





    Получение Carry 
 

В общем случае мы можем сделать арифметику любого размера (особенно кратного
длинне машинного слова).
Основная проблема при реализации - для сложений и вычитаний частей нам надо 
получать значения флага Carry.
На уровне машинных кодов - это тривиальная задача, поэтому один из вариантов
реализации - сделать на ассемблере функции примитивы - которые будут делать
операцию и еще возвращать в ЯВУ значение Carry Flag. Понятно что такую реализацию
надо будет портировать.

Если делать реализацию на чистом ЯВУ - то во первых надо посмотреть какая 
архитектура у платформы - совершаются ли операции точно того размера как мы хотим,
или они совершаются с sign-extended в больший размер.
Но в любом случае  при реализации на ЯВУ приходиться прибегать к ухищрениям.

(1) Использовать блоки более короткого размера чем длинна слова и всегда
    zero-extend операнды.
    При сложении вычитании смотреть выходим ли мы за пределы диапазона.

    unsigned short s1;    	// source chunk 1
    unsigned short s2;		// source chunk 2
    unsigned short result;	// resulted chunk

    unsigned long r1 = s1;
    unsigned long r2 = s2;

    unsigned long t = r1 + r2;
    result = (unsigned short) t;
    carry  = (t > 0x10000)? 1 : 0;	// если вылезло за пределы то был перенос/заем


(2) Вычислять Carry из соотношений

                          U _
	carry(X + Y) = X  > Y


Посмотрим на примере 2 битовых чисел
                                _
	X	Y	X+Y	Y	C
	00	00	0.00	11	0	
	00	01	0.01	10      0
	00	10	0.10	01      0
	00	11	0.11	00      0
	01	00	0.01	11      0
	01	01	0.10	10      0
	01	10	0.11	01      0
	01	11	1.00	00      1
	10	00	0.10	11      0
	10	01	0.11	10      0
	10	10	1.00	01      1
	10	11	1.01    00      1
	11	00	0.11    11      0
	11	01	1.00    10      1
	11	10	1.01    01      1
	11	11	1.10    00      1

Попробуем написать формулу для carry(X - Y)
она вообще очень проста и естественна

                          U
	 carry(X - Y) = X < Y

	                                            _             U   _       
	carry(X + Y) = carry(X - (-Y)) = carry(X - (Y + 1)) =  X  <  (Y + 1) 



    Умножение чисел со знаком 
 

  

В случае программной реализации умножение чисел повышенной точности, расширять
частные произведения до полного размера знаком очень дорогая операция, поэтому
используют следующий подход: преобразуют числа к беззнаковым, умножают, а потом
меняют знак у результата если надо:

	---------------------
	A	B	A*B
	---------------------
	+	+	+
	+	-	-
	-	+	-
	-	-	+
	---------------------

Собсвенно sign(A*B) = sign(A) xor sign(B)



    Деление чисел со знаком 
 

Для программной реализации имеет смысл делать преобразование к числам без знака
а потом корректировать результат и остаток.

	-------------------------------
	A	B	A/B	A%B
	-------------------------------
	 7	 5	 1	 2
	 7	-5	-1	 2
	-7	 5	-1	-2
	-7	-5	 1	-2
	-------------------------------

Таким образом знак частного (quotient) положительный если знаки делимого (dividend)
и делителя (divisor) совпадают, и отрицательный в других случаях.

	sing(quotient) = sign(dividend) xor sign(divisor)

А знак остатка (remainder) совпадает со знаком делимого (dividend).

	sign(remainder) = sign(dividend)




    Сравнения 
 

Описанные ниже правила для сравнения чисел многократной точности, действуют и в
случае знаковых и в случае беззнаковых чисел, но понятное дело, что частные сравнения
между кучочками для знаковых и беззнаковых чисел различны.

  

	A == B :  if (A[high] == B[high])
		  {
			if (A[low] == B[low]) then true
		  }
		  false
  
	A != B :  if (A[high] != B[high]) then true
		  if (A[low]  != B[low])  then true
		  false


  
	A > B  :  if (A[high] > B[high]) then true
		  if (A[high] == B[high])
		  {
			if (A[low] > B[low]) then true
		  }
		  false

  
	A >= B  : if (A[high] > B[high]) then true
		  if (A[high] == B[high])
		  {
			if (A[low] >= B[low]) then true
		  }
		  false

  
  





    Побитовые логические операции 
 

Побитовые логические операции выполняются над каждой из частей отдельно


	A & B  :  result[high] = A[high] & B[high]
		  result[low]  = A[low]  & B[low]


	A | B  :  result[high] = A[high] | B[high]
		  result[low]  = A[low]  | B[low]
	
	A ^ B  :  result[high] = A[high] ^ B[high]
		  result[low]  = A[low]  ^ B[low]

	~A     :  result[high] = ~A[high]
		  result[low]  = ~A[low]

Кстати имейте в виду что операцию NEG то есть -X, для чисел многократной точности
удобнее минимизировать через -X =  ~A + 1,  это быстрее чем как  0-X
так как для операции +1, можно прооптимизировать время выполнения следя за
carry flag в процессе. Если он неустановлен для какой то частной суммы, то для всех
старший частных сумм - операцию можно уже не делать.



    Псевдовекторные операции 
 

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

Сложение:
  

Смысл техники - мы маскируем старший бит у элемента вектора и складываем
                такие части - они никак не вылезут за пределы вектора.
 		Затем сверху накладываем сумму для старшего бита, поскольку
		нас не интересует carry, то мы просто делаем xor

Addition:

	t    = (x & 0x7f7f7f7f) + (y & 0x7f7f7f7f)
	sum  = ((x xor y) & 0x80808080) xor t)

Subtraction:
	t    = (x & 0x7f7f7f7f) - (y & 0x7f7f7f7f)
	sum  = ((x xor y) | 0x7f7f7f7f) eqv t
	

Multiply Low:
  

Negate:
  

Shift Left:
  

Constant to Vector:
  

Constant to Vector:
  

Compare patrial unsigned:
  

Compare partial signed:
  
  




Сложности псевдовекторных операций
(представленны для векторов длинны 4):

	-------------------------------------------
	Сложение		1	сложение
				5	логических 
	-------------------------------------------
	Умножение на скаляр     2	умножения
				5	логических      
	-------------------------------------------
	Сдвиг			1	сдвиг
				1	логическая
	-------------------------------------------
	Negate (-X)		1	вычитание
				3	логических
	-------------------------------------------
	Логические              1	логическая
	-------------------------------------------
	Сравнение (беззнаковое)	1	сравнение
				2	логических     
	-------------------------------------------
	Сравнение (знаковое)	1	сравнение
 			       (2	сдвига)
				2	логических
	-------------------------------------------
Index Prev Next