Формула для переноса

[Груша Вильямс]

Не могу придумать формулу. Задача несколько специфическая. Предположим, что у нас есть некоторая переменная, которая может хранить число из диапазона от 0 до 9.
Надо придумать как умножить такие переменные.
Диапазон следует представлять как замкнутую ленту из последовательных ячеек 0, 1, 2, ..., 9, таким образом если мы пишем 9+1, то попадаем в ячейку 0 (т.е. 9+1=0), и так далее вплоть до 9+9=8.

Дано:
max = 9 - это предельное значение диапазона,
a - одна переменная,
b - другая переменная
carry - переменная переноса.

Операции:
+, -, *, /
битовые |, &, ^, ! (or, and, xor, not)
% - взятие остатка
ну и любые другие можно использовать

Примеры:
a=1, b=9 => carry = 0
a=2, b=9 => carry = 1
a=4, b=8 => carry = 3

Ограничения:
переменных способных хранить числа, состоящие более, чем из одного знака, не существует. Это означает, что операция 2*9 невыполнима в стандартном понимании, так как не существует переменной способной хранить число 18, результатом операции 2*9 будет 2*9=9+9=8 как уже говорилось. Данное ограничение можно воспринимать как своеобразную архитектуру процессора, который работает только лишь с однозначными числами.

Найти:
функцию carry = f(a,b,max).

Например, при 2*9 нахождение carry=1 позволит отпечатать произведение как последовательная печать переменной carry как 1 и печать операции 2*9 как 8, итого 18.

@темы: Головоломки и занимательные задачи, Дискретная математика

Comments

[Груша Вильямс]

Trotil, по идее так же должно работать, а выдает фигню какую-то...

#include <iostream>
#include <stdint.h>


typedef uint16_t uint16;

int main() {

	uint16 a[] = { 0xffui16, 0xffui16 };  // 65535
	uint16 b[] = { 0xffui16, 0xffui16 };  // 65535

	uint16 mul[] = { 0x0ui16, 0x0ui16 };
	
	uint16 x1 = (a[0] * b[1]) >> 8;              // старший байт 1
        uint16 x2 = (a[0] * b[0]) >> 8;              // старший байт 2

	uint16 y1 = ((a[0] * b[1]) << 8) + a[1] * b[1];  // младший байт 1
        uint16 y2 = ((a[0] * b[0]) << 8) + a[1] * b[0];  // младший байт 2

        mul[0] = x1 + x2;
	mul[1] = y1 + y2;

	std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;

	return 0;
}

[Груша Вильямс]

Trotil, кажется я близок

#include <iostream>
#include <stdint.h>


typedef uint16_t uint16;

int main() {

	uint16 a[] = { 0xffui16, 0xffui16 };  // 65535
	uint16 b[] = { 0xffui16, 0xffui16 };  // 65535

	uint16 mul[] = { 0x0ui16, 0x0ui16 };
	
	uint16 x1 = (a[0] * b[1]) >> 8;              // старший байт 1
        uint16 x2 = (a[0] * b[0]) >> 8;              // старший байт 2

	uint16 y1 = ((a[0] * b[1]) << 8) + a[1] * b[1];  // младший байт 1
        uint16 y2 = ((a[0] * b[0]) << 8) + a[1] * b[0];  // младший байт 2

        mul[0] = x1 + (x2 << 8);
	mul[1] = y1 + (y2 << 8);

	std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;

	return 0;
}

Вывод
mul: fefe 1

Должно быть:
mul: fffe 1

[Груша Вильямс]

Trotil, спасибо, отдохнул чуть, попробовал снова и получилось.

#include <iostream>
#include <stdint.h>


typedef uint16_t uint16;

int main() {

	uint16 a[] = { 0xffui16, 0xffui16 };  // 65535
	uint16 b[] = { 0xffui16, 0xffui16 };  // 65535

	uint16 mul[] = { 0x0ui16, 0x0ui16 };
	
	uint16 x1 = (a[0] * b[1]) >> 8;              // старший байт 1
        uint16 x2 = (a[0] * b[0]) >> 8;              // старший байт 2

	uint16 y1 = ((a[0] * b[1]) << 8) + a[1] * b[1];  // младший байт 1
        uint16 y2 = ((a[0] * b[0]) << 8) + a[1] * b[0];  // младший байт 2

        mul[0] = x1 + (x2 << 8) + (y2 << 8);
	mul[1] = y1 + (y2 << 8);

	std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;

	return 0;
}

Думаю, что ужать код ещё можно.

p.s.
хотя нет, неправильно при
uint16 b[] = { 0xaaui16, 0xffui16 }; // 43775
считает

[Груша Вильямс]

Trotil, вроде бы так

#include <iostream>
#include <stdint.h>

typedef uint16_t uint16;

int main() {
      
        uint16 a[] = { 0xffui16, 0xffui16 }; // 65535
	uint16 b[] = { 0xaaui16, 0x12ui16 }; // 43538
	
        uint16 mul[] = { 0x0ui16, 0x0ui16 };

	uint16 x1 = (a[0] * b[1]) >> 8;
	uint16 y1 = ((a[0] * b[1]) << 8) + (a[1] * b[1]);

	uint16 x2 = (a[0] * b[0]) >> 8;
	uint16 y2 = ((a[0] * b[0]) << 8) + (a[1] * b[0]);

	uint16 carry = ((y1 >> 8) + (y2 & 0x00ff)) >> 8;

	mul[0] = (x2 << 8) + (y2 >> 8) + x1 + carry;
	mul[1] = y1 + (y2 << 8);

	//       0011 ffee   x1 = 11 = 17,  y1 = ffee = 65518
	//       a9ff 5600   x2 = a9 = 169, y2 = ff56 = 65366
	//       __________
	//       aa11 55ee    
	std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;

	return 0;
}

[Trotil]

Работает, это хорошо.
Но тебя вроде просили реализовать умножение двух 32-битных чисел, а не 16-битных.

> посмотрел книги, которые вы рекомендовали,
> верилог всё же другое как по мне дк.

Сумматоры - это чисто комбинационная логика и легко переносятся на Си (в отличие от схем с предыдущем состоянии на входе - типа триггеров).
И алгоритмы в книжке самые оптимальные. Поэтому и порекомендовал.

А если её всю прочитать и проделать лабы - это ключ к сакральному знанию о том, как делается сейчас в мире в корпоративных гигантах вся современная продвинутая цифровая электроника на низком уровне.

[Груша Вильямс]

Trotil,

Работает, это хорошо.

походу не работает из-за неправильной реализации сложения, сейчас проснулся и заметил, что
случай 65535 + 1 вместо
sum: 1 0
у меня покажет
sum: 0 0,
причём я понимаю почему так, но пока не понимаю как это поправить...

#include <iostream>
#include <stdint.h>


typedef uint16_t uint16;

int main() {

	uint16 a[] = { 0xffui16, 0xffui16 }; // 65535
	uint16 b[] = { 0x0ui16,  0x1ui16 };  // 1

	uint16 sum[] = { 0x0ui16, 0x0ui16 };
	
	sum[0] = (a[0] + b[0]) >> 8;                    // старший байт
	sum[1] = ((a[0] + b[0]) << 8) + (a[1] + b[1]);  // младший байт

	std::cout << "sum: " << std::hex << sum[0] << " " << sum[1] << std::endl;

	return 0;
}

Но тебя вроде просили реализовать умножение двух 32-битных чисел, а не 16-битных.

да, всё так, но умножение 32-битных будет базироваться на сложении и умножении 16-битных, поэтому пока операции с ними и обкатываю

[Trotil]

да, всё так, но умножение 32-битных будет базироваться на сложении и умножении 16-битных, поэтому пока операции с ними и обкатываю

Ок. Но я бы сделал:

a) функцию умножения 32-битного числа на A < 256,
b) функцию сдвига 32-битного числа на b бит
с) цикл, в котором реализуется алгоритм умножения столбиком
(сложение у тебя уже есть)

Это вроде как проще запрогать, и меньше шансов запутаться и допустить ошибку.

[Trotil]

причём я понимаю почему так, но пока не понимаю как это поправить...

удобнее представлять, что у тебя 256-ричная система счисления.
попробуй на бумаге сложить и не 16-битные числа, а чё-нить подлиннее, выйдет универсальный алгоритм

Хотя мб тебе проще твоим подходом добить до конца

[Груша Вильямс]

Trotil, поправил

#include <iostream>
#include <stdint.h>

typedef uint16_t uint16;

int main() {

	uint16 a[] = { 0xffui16, 0xffui16 }; // 65535
	uint16 b[] = { 0x0ui16, 0x1ui16 };   // 1

	uint16 sum[] = { 0x0ui16, 0x0ui16 };

	sum[0] = ((a[0] + b[0]) >> 8) + ((a[1] + b[1]) >> 8); // старший байт
	sum[1] = ((a[0] + b[0]) << 8) + (a[1] + b[1]);        // младший байт

	std::cout << "sum: " << std::hex << sum[0] << " " << sum[1] << std::endl;

	uint16 mul[] = { 0x0ui16, 0x0ui16 };

	uint16 x1 = (a[0] * b[1]) >> 8;
	uint16 y1 = ((a[0] * b[1]) << 8) + (a[1] * b[1]);

	uint16 x2 = (a[0] * b[0]) >> 8;
	uint16 y2 = ((a[0] * b[0]) << 8) + (a[1] * b[0]);

	uint16 carry = ((y1 >> 8) + ((y2 & 0x00ff)) >> 8) + ((y1 & 0x00ff) >> 8);

	mul[0] = (x2 << 8) + (y2 >> 8) + x1 + carry;
	mul[1] = y1 + (y2 << 8);

	////////////////Test Multiplication////////////////////////////

	//       0011 ffee   x1 = 11 = 17,  y1 = ffee = 65518
	//       a9ff 5600   x2 = a9 = 169, y2 = ff56 = 65366
	//       __________
	//       aa11 55ee    
	std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;

	return 0;
}

Но есть сомнения в этом куске

uint16 carry = ((y1 >> 8) + ((y2 & 0x00ff)) >> 8) + ((y1 & 0x00ff) >> 8);

На примере в комментариях carry это переполнение при сложении ffee + 5600, в общем случае y1 (ffee) + y2 (ff56), но y2 будет всегда же сдвинут на байт влево по алгоритму умножения столбиком, тогда будет ffee + 5600, в общем случае y1 + (y2 << 8), причём младший байт y1 это ee, в общем случае (y1 & 0x00ff), а младший байт y2 это всегда 00, поэтому их сумма никогда не должна давать переполнения в старший байт, а тогда вроде бы достаточно просто так записать:

uint16 carry = ((y1 >> 8) + ((y2 & 0x00ff)) >> 8);

то есть не учитывать сумму ( (y1 & 0x00ff) + ((y2 << 8) & 0x00ff) ) >> 8

[Груша Вильямс]

Trotil, умножение всё-таки рабочее было по причинам описанным выше, а вот исправленное сложение (переполнение из-за младшего байта типа 65535+1) падает

#include <iostream>
#include <stdint.h>

typedef uint16_t uint16;

int main() {

	uint16 a[] = { 0xffui16, 0xffui16 }; // 65535
	uint16 b[] = { 0x99ui16, 0x99ui16 }; // 39321

	uint16 sum[] = { 0x0ui16, 0x0ui16 };

	sum[0] = ((a[0] + b[0]) >> 8) + ((a[1] + b[1]) >> 8); // старший байт
	sum[1] = ((a[0] + b[0]) << 8) + (a[1] + b[1]);        // младший байт

	std::cout << "sum: " << std::hex << sum[0] << " " << sum[1] << std::endl;

        return 0;
}

Вывод:
sum: 2 9998

Должно быть:
sum: 1 9998

То есть к переносу по старшему байту добавляет перенос по младшему байту... и получается неверный перенос

[Груша Вильямс]

Trotil, всё, зафурычило наконец-то

#include <iostream>
#include <stdint.h>

typedef uint16_t uint16;

int main() {

	uint16 a[] = { 0xffui16, 0xffui16 }; // 65535
	uint16 b[] = { 0x1ui16, 0x99ui16 };  // 409

	uint16 sum[] = { 0x0ui16, 0x0ui16 };

	sum[0] = ((a[0] + b[0]) >> 8) | ((a[1] + b[1]) >> 8); // старший байт
	sum[1] = ((a[0] + b[0]) << 8) + (a[1] + b[1]);        // младший байт

	std::cout << "sum: " << std::hex << sum[0] << " " << sum[1] << std::endl;

	uint16 mul[] = { 0x0ui16, 0x0ui16 };

	uint16 x1 = (a[0] * b[1]) >> 8;
	uint16 y1 = ((a[0] * b[1]) << 8) + (a[1] * b[1]);

	uint16 x2 = (a[0] * b[0]) >> 8;
	uint16 y2 = ((a[0] * b[0]) << 8) + (a[1] * b[0]);

	uint16 carry = ((y1 >> 8) + (y2 & 0x00ff)) >> 8;

	mul[0] = (x2 << 8) + (y2 >> 8) + x1 + carry;
	mul[1] = y1 + (y2 << 8);

	////////////////Test Multiplication////////////////////////////

	//       0011 ffee   x1 = 11 = 17,  y1 = ffee = 65518
	//       a9ff 5600   x2 = a9 = 169, y2 = ff56 = 65366
	//       __________
	//       aa11 55ee    
	std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;

	return 0;
}

[Груша Вильямс]

Как-то так ... Осталось функцию mul_32() реализовать

#include <iostream>
#include <stdint.h>

typedef uint16_t uint16;

void sum_16(uint16 a[2], uint16 b[2], uint16 sum[2]) {

	sum[0] = ((a[0] + b[0]) >> 8) | ((a[1] + b[1]) >> 8); // старший байт
	sum[1] = ((a[0] + b[0]) << 8) + (a[1] + b[1]);        // младший байт

	std::cout << "sum: " << std::hex << sum[0] << " " << sum[1] << std::endl;
}

void mul_16(uint16 a[2], uint16 b[2], uint16 mul[2]) {

	uint16 x1 = (a[0] * b[1]) >> 8;
	uint16 y1 = ((a[0] * b[1]) << 8) + (a[1] * b[1]);

	uint16 x2 = (a[0] * b[0]) >> 8;
	uint16 y2 = ((a[0] * b[0]) << 8) + (a[1] * b[0]);

	uint16 carry = ((y1 >> 8) + (y2 & 0x00ff)) >> 8;

	mul[0] = (x2 << 8) + (y2 >> 8) + x1 + carry;
	mul[1] = y1 + (y2 << 8);

	std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;
}

int main() {

	uint16 a = 0xffffui16; // 65535
	uint16 b = 0xaa12ui16; // 43538

	uint16 x[] = { a >> 8, a & 0x00ff }; // 65535
	uint16 y[] = { b >> 8, b & 0x00ff }; // 43538

	//////////////////////////////////SUM////////////////////////////////////////

	uint16 sum[] = { 0x0ui16, 0x0ui16 };

	sum_16(x, y, sum);

	//////////////////////////////////MUL////////////////////////////////////////

	uint16 mul[] = { 0x0ui16, 0x0ui16 };

	mul_16(x, y, mul);

	return 0;
}

[Груша Вильямс]

Trotil, что-то не пойму, формула же по идее такая должна быть b*d + ((a*d + b*c) << 16) + (a*c << 32) ? Но сдвиг на 16 и 32 это сразу 0 ... Хотя это позиция в результирующем массиве...

int main() {

	uint16 a = 0xffffui16; // 65535
	uint16 b = 0xaa12ui16; // 43538
	uint16 c = 0x9901ui16; // 
	uint16 d = 0xaa01ui16; // 
	
	uint16 sum[] = { 0x0ui16, 0x0ui16 };
	uint16 mul[] = { 0x0ui16, 0x0ui16 };

	//uint16 x[] = { a >> 8, a & 0x00ff }; // 65535
	//uint16 y[] = { b >> 8, b & 0x00ff }; // 43538

	uint16 x[] = { a, b };
	uint16 y[] = { c, d };

	// b*d + ((a*d + b*c) << 16) + (a*c << 32)
	return 0;
}

[Груша Вильямс]

Трешак какой-то получается, надо думать как ужимать

int main() {

	uint16 a = 0xffffui16; //
	uint16 b = 0xabcfui16; // 
	uint16 c = 0xabcdui16; // 
	uint16 d = 0x0968ui16; // 
	
	uint16 sum[] = { 0x0ui16, 0x0ui16 };
	uint16 mul[] = { 0x0ui16, 0x0ui16 };

	 uint16 a_arr[] = { a >> 8, a & 0x00ff }; // 
	 uint16 b_arr[] = { b >> 8, b & 0x00ff }; // 
	 uint16 c_arr[] = { c >> 8, c & 0x00ff }; // 
	 uint16 d_arr[] = { d >> 8, d & 0x00ff }; // 

	uint16 x[] = { a, b };
	uint16 y[] = { c, d };

	uint16 res[] = { 0x0000ui16, 0x0000ui16, 0x0000ui16, 0x0000ui16 };

	mul_16(b_arr, d_arr, mul);
	res[3] = mul[1];
	std::cout << std::hex << "res[3]: " << res[3] << std::endl;

	uint16 carry[] = { mul[0] >> 8, mul[0] & 0x00ff };  // carry от res[3]
	
	//////////////////////////////  a * d   ////////////////////////////////

	mul_16(a_arr, d_arr, mul);
	uint16 arr_1[] = { mul[1] >> 8, mul[1] & 0x00ff };  // a*d для res[2]
	
	//////////////////////////////  b * c   ////////////////////////////////
	mul_16(b_arr, c_arr, mul);
	uint16 arr_2[] = { mul[1] >> 8, mul[1] & 0x00ff };  // b*c для res[2]

	/////////////////////////  a * d   +   b * c  //////////////////////////

	sum_16(arr_1, arr_2, sum);                          // a*d + b*c для res[2]
	uint16 arr_3[] = { sum[1] >> 8, sum[1] & 0x00ff };

	////////////////////  a * d   +   b * c  +   carry   ////////////////////

	sum_16(carry, arr_3, sum);
	res[2] = sum[1];
	std::cout << std::hex << "res[2]: " << res[2] << std::endl;

	// b*d + ((a*d + b*c) << 16) + (a*c << 32)


	return 0;
}

[Trotil]

Трешак какой-то получается

Груша Вильямс, именно поэтому придумали массивы, функции и циклы!

[Груша Вильямс]

Trotil, всю голову сломал, но так и не придумал как это в цикл обернуть, 100% в цикл оборачивают

[Груша Вильямс]

Trotil, с циклом проблема собственно какая, проблема в самом алгоритме умножения в столбик
например,
ab
cd

1) b*d и от него carry_bd и res[3]

2a) a*d и от него carry_ad и 1-ый res[2]
2б) b*c и от него carry_bc и 2-ой res[2]
2в) a*d + b*c и от него carry_ad_bc и 3-ий res[2] = 1-ый res[2] + 2-ой res[2]
2г) a*d + b*c + carry_bd и от него carry_ad_bc_carry и 4-ый res[2] = 3-ий res[2] + carry_bd

3) как и два можно сказать...

Непонятно как такую логику зацикливать, в первую очередь непонятно с переменной carry, возможно с одной переменной это провернуть или нет, по-моему с одной нельзя, напрашиваются carry_add на сложение и carry_mul на умножение, та же проблема с res[2] на разных шагах

Перепишу с carry_add и carry_mul:

1) b*d и от него carry_mul и res[3]

2a) a*d и от него новый carry_mul -- выходит, что предыдущее значение carry_mul перетирается
2б) b*c и от него новый carry_mul -- проблема как и на предыдущем шаге
2в) a*d + b*c и от него carry_add -- тут проблем нет
2г) a*d + b*c + (нужен самый первый carry_mul, тот который carry_bd, тогда получается, что carry_mul на шаге 1 и carry_mul на шаге 2 должны быть разные) и от него carry_add суммируется с предыдущим значением carry_add (т.е. carry_add += carry_add)

3) как и два можно сказать...

[Груша Вильямс]

Trotil, как бы общий какой-то цикл могу, конечно, написать, что-то типа этого

int main() {

	uint16 a = 0xffffui16; 
	uint16 b = 0xabcfui16;  
	uint16 c = 0xabcdui16;  
	uint16 d = 0x0968ui16; 

	uint16 x[] = { a, b };
	uint16 y[] = { c, d };
        
        uint16 arr_1[] = { 0x0ui16, 0x0ui16 };
	uint16 arr_2[] = { 0x0ui16, 0x0ui16 };

	uint16 res[] = { 0x0000ui16, 0x0000ui16, 0x0000ui16, 0x0000ui16 };
        
        uint16 sum[] = { 0x0ui16, 0x0ui16 };
	uint16 mul[] = { 0x0ui16, 0x0ui16 };

	for (int i = 1; i >= 0; i--) {
		for (int j = 1; j >= 0; j--) {
                        // итерации x[i] * y[j]
			// 11 - b*d
                        // 10 - b*c 
                        // 01 - a*d
                        // 00 - a*c
                        
                        // аналоги
                        // uint16 a_arr[] = { a >> 8, a & 0x00ff }; 
	                // uint16 b_arr[] = { b >> 8, b & 0x00ff }; 
	                // uint16 c_arr[] = { c >> 8, c & 0x00ff }; 
	                // uint16 d_arr[] = { d >> 8, d & 0x00ff }; 

			arr_1[] = { x[i] >> 8, x[i] & 0x00ff };  // b, b, a, a
			arr_2[] = { y[j] >> 8, y[j] & 0x00ff };  // d, c, d, c
		}
	}

	return 0;
}

а дальше собственно ступор...

[Trotil]

завтра подкину мыслей.

[Груша Вильямс]

Trotil, спасибо
xx98
xx76
______
xx48
x56
x54
63
_______
из-за того, что 54 не сдвинуто на знак относительно предыдущего частичного произведения 56, получается, что общая логика рушится, то есть для элементов a[1]*b[0] и a[0]*b[1] будет немного другая логика, без смещения на знак, в этом и проблема основная как мне кажется. Но каждое из частичных произведений (48, 56, 54 и 63) является числом типа uint16, которое легко получить через ту же функцию mul_16(). В принципе в цикле легко собрать массив этих частичных произведений, а потом уже как-то с ним там работать. Вроде как это упрощение задачи уже будет, как минимум переход от умножения к сложению произошёл.

[Груша Вильямс]

Trotil, попутно выяснилось, что функция mul_16() неправильно работает -- отталкивался как вы и говорили от умножения на число, собственно умножение на число и реализовал неправильно

Пример

void mul_16(uint16 a[2], uint16 b[2], uint16 mul[2]) {
	
	// 0088 94c3 вместо 0089 94c3
	//uint16 x1 = (a[0] * b[1]) >> 8;                  // 88ef >>   8 = 0088
	uint16 y1 = ((a[0] * b[1]) << 8) + (a[1] * b[1]);  // ef00 + a5c3 = 0001 94c3 - overflow
	uint16 x1 = ((a[0] * b[1]) >> 8) + (y1 >> 16);        // 0088 + 0000 = 0088 - fail    
	
	uint16 x2 = (a[0] * b[0]) >> 8;
	uint16 y2 = ((a[0] * b[0]) << 8) + (a[1] * b[0]);

	uint16 carry = ((y1 >> 8) + (y2 & 0x00ff)) >> 8; // 0194 + 45

	mul[0] = (x2 << 8) + (y2 >> 8) + x1 + carry;     // 7200 + 00c3 + 8800 + carry = fac3 + carry
	mul[1] = y1 + (y2 << 8);

	// { 0xab, 0xcf } * { 0xab, 0xcd }

	//      0089 94c3    x1 = 0x89,  y1 = 0x94c3
	//      72c3 4500    x2 = 0x72,  y2 = 0xc345
        //      _________
	//      734c d9c3

	//std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;
}

Надо переполнение при подсчёте y1 как-то отловить, оно возникает как раз при сложении...

[Груша Вильямс]

Trotil, mul_16() поправил

void mul_16(uint16 a[2], uint16 b[2], uint16 mul[2]) {
	uint16 sum[] = { 0x0ui16, 0x0ui16 };
	
	//uint16 x1 = (a[0] * b[1]) >> 8;                    // 88ef >>   8 = 0088
	//uint16 y1 = ((a[0] * b[1]) << 8) + (a[1] * b[1]);  // ef00 + a5c3 = 0001 94c3 - overflow

	uint16 p = a[0] * b[1];
	uint16 p_arr[] = { p & 0x00ffui16, 0x0ui16 };

	uint16 q = a[1] * b[1];
	uint16 q_arr[] = { q >> 8, q & 0x00ffui16 };

	sum_16(p_arr, q_arr, sum);
	uint16 x1 = (p >> 8) + sum[0];
	uint16 y1 = sum[1];

	/////////////////////////////////////////////////////////////////////////////////////


	//uint16 x2 = (a[0] * b[0]) >> 8;
	//uint16 y2 = ((a[0] * b[0]) << 8) + (a[1] * b[0]);

	p = a[0] * b[0];
	p_arr[0] = p & 0x00ffui16; p_arr[1] = 0x0ui16;

	q = a[1] * b[0];
	q_arr[0] = q >> 8; q_arr[1] = q & 0x00ffui16;

	sum_16(p_arr, q_arr, sum);
	uint16 x2 = (p >> 8) + sum[0];
	uint16 y2 = sum[1];

	///////////////////////////////////////////////////////////////////////////////////////

	uint16 carry = ((y1 >> 8) + (y2 & 0x00ffui16)) >> 8; 

	mul[0] = (x2 << 8) + (y2 >> 8) + x1 + carry;
	mul[1] = y1 + (y2 << 8);

	// { 0xab, 0xcf } * { 0xab, 0xcd }

	//      0088 94c3    x1 = 0x89,  y1 = 0x94c3
	//      72c3 4500    x2 = 0x72,  y2 = 0xc345
        //      _________
	//      734c d9c3

	//std::cout << "mul: " << std::hex << mul[0] << " " << mul[1] << std::endl;
}

частичные произведения написал

int main() {

	uint16 a = 0xffffui16; 
	uint16 b = 0xabcfui16;
	uint16 x[] = { a, b };

	uint16 c = 0xabcdui16; 
	uint16 d = 0x0968ui16; 
	uint16 y[] = { c, d };

	uint16 sum[] = { 0x0ui16, 0x0ui16 };
	uint16 mul[] = { 0x0ui16, 0x0ui16 };

	uint16 res[] = { 0x0000ui16, 0x0000ui16, 0x0000ui16, 0x0000ui16 };

	uint16 part[4][2] = { 
							{ 0x0ui16, 0x0ui16 },
							{ 0x0ui16, 0x0ui16 },
							{ 0x0ui16, 0x0ui16 },
							{ 0x0ui16, 0x0ui16 }
	                    };

	// b*d, b*c, a*d, a*c
	for (int i = 1; i >= 0; i--) {
		for (int j = 1; j >= 0; j--) {
			uint16 arr_1[] = { x[i] >> 8, x[i] & 0x00ff }; // b, b, a, a
			uint16 arr_2[] = { y[j] >> 8, y[j] & 0x00ff }; // d, c, d, c
			
			mul_16(arr_1, arr_2, mul); 
			part[2 * i + j][0] = mul[0];
			part[2 * i + j][1] = mul[1];
		}
	}

	std::cout << "test partial: " << std::endl;

	for (int i = 3; i >= 0; i--) {
		for (int j = 0; j < 2; j++) {
			std::cout << std::hex << part[i][j] << " ";
		}
		std::cout << std::endl;
	}

	return 0;
}

[Trotil]

За час набросал идею, которую я советовал: ideone.com/CdQR8z
Вроде работает.
Если нажать fork, можно редактировать и запускать старый код там.

P.S. Через ООП получилось бы компактнее, но ведь нужно было на Си.

[Trotil]

Какой подход к решению задачи лучше на твой взгляд?