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

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

Не могу придумать формулу. Задача несколько специфическая. Предположим, что у нас есть некоторая переменная, которая может хранить число из диапазона от 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]

Аппаратно числа в регистрах процессора сохранены как двоичные числа, а сложение реализовано поразрядно с помощью таблицы истинности или элементарных операций AND, OR и т.д. Кому интересно, скажу, что подробнее эта тема раскрыта в двух хороших книжках - (Харрис) Цифровая схемотехника и архитектура компьютера и её продолжении (написанным, кстати, российскими специалистами в области проектирования цифровой схемотехники) "Цифровой синтез. Практический курс. - ДМК-Пресс".

Поэтому нужно ещё как минимум оговорить, как хранятся числа и (обязательно!) что нужно считать элементарными операциями в этой архитектуре. Иначе в самом простом случае мы можем заявить, что всё реализовано через большую таблицу истинности и задача решена.

[Trotil]

Сорри, я не заметил, что доступны битовые операции, значит я немного не на тот вопрос ответил. )))

Вопрос в определении carry.
Ну. во-первых, если вы обратитесь к рекомендованной литературе, то окажется, что carry - это обычно расширение регистра, и если переполнение случилось, то в дополнительных битах не нуль (то есть carry не вычисляют отдельной формулой), это как бы 32(64)-тый бит регистра (для вашей задачи надо взять не один дополнительный бит, а 4).

Во-вторых, битовые операции несколько странно применять для регистров емкостью не кратных степени 2. Что, например, будет означать битовая операция 5 OR 8?

Про формулу сейчас ещё подумаю.

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

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

Код написал в итоге так пока

#include <stdio.h>
#include <limits.h>

typedef unsigned int uint16;
typedef unsigned int uint;

uint carry(uint a, uint b) {
	uint sum = a, carry = 0;
	b--;
	while (b--) {
		if (sum > 9 - a) carry++;
		sum = (sum + a) % 10;
	}
	return carry;
}

uint foo(uint a, uint b) {
	
	if (a > UINT_MAX / b) {
		/* Handle error */
		printf("this is if");
		printf("\t");
	}

	return a * b;
}

int main() {

	for (uint i = 1; i < 10; i++) {
		for (uint j = 9; j > 0; j--) {
			printf("i: %u j: %u carry: %u \n", i, j, carry(i, j));
		}
		printf("\n");
	}

        return 0;
}

Работает. Как понимаю вместо девятки UINT_MAX бахнуть и всё будет работать для стандартного 32-разрядного unsigned int.
По задаче же придётся свою константу для наибольшего значения 16-разрядного числа определить насколько понимаю, UINT16_MAX какой-нибудь.

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

Trotil, проверил в деле функцию carry, работает.

#include <stdio.h>
#include <limits.h>

typedef unsigned int uint16;
typedef unsigned int uint;

uint carry_uint(uint a, uint b) {
	uint sum = a, carry = 0;
	while (b--) {
		if (sum > UINT_MAX - a) carry++;
		sum = sum + a;
	}
	return carry;
}

uint foo(uint a, uint b) {
	
	if (a > UINT_MAX / b) {
		/* Handle error */
		printf("this is if");
		printf("\n");
		printf("carry_uint: %u \n", carry_uint(a, b-1));
	}

	return a * b;
}

int main() {

	/////////////////////////////Carry test////////////////////////////////

	// uint max - (2^32-1)
	uint a = 0x10000000; // 16^7 = 2^28
	uint b = 0x0000010; // 16^1 = 2^4
	// overflow a * b = 2^32
	// 2^32 = 0x00000001 0x00000000, carry = 1
        
        foo(a, b);

	return 0;
}

Выводит

this is if
carry_uint: 1

Осталось алгоритм умножения подобрать какой-нибудь... И собрать это всё дело.

[Trotil]

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

Классический вариант решения подобной задачи - хранить такое число в массиве. Не нужно никаких carry. Или нельзя uint16[2]?

[Trotil]

> typedef unsigned int uint16;

Что это? Есть архитектурно независимый тип данных uint16_t. Используй его.

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

Trotil, можно, так и делаю потом. Про uint16_t не знал, но как переполнение обрабатывать?

[Trotil]

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

Если не хочешь глубоко вникать в эту тему, вот тебе лайфхак - реализуй на базе uint16_t арифметику восьмибитных чисел, тогда тебе не придётся вводить отдельную переменную под перенос или умножение, а 32-битное число, это массив из 4 этих чисел, где значимыми являются только последние 8 бит.

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

Trotil, понимаю это, под результат и стоит массив из 4ех элементов. Я к тому, что вроде бы переполнения не избежать при любом раскладе. Допустим старшие 2 байта в элементе с индексом 0, младшие 2 байта в элементе с индексом 1. Также допустим, что реализуем алгоритм умножения столбиком, знаю что есть алгоритм карацубы, алгоритм бута, но не вникал в них ещё, поэтому первое что в голову пришло беру. При умножении столбиком вначале перемножаются единицы, в данном случае это будет res[3] = a[1] * b[1], но есть проблема переполнения, например элементы равны a[1]=b[1]=65535 = 0xffff, a мы не то что умножение, обычное сложение допустим делаем 65535+65535=65534=0xfffe, вместо 131070=0x0001 0xfffe.

[Trotil]

В варианте, который я предложил, Число 65535 размещается в массиве из двух элементов типа uint_16t, a[0]=0xff, a[1]=0xff
сложение, это b[0]=a[0]+a[0]=0x1fe, b[1]=a[1]+a[1]=0x1fe, и переносов: b[1] = (a[0] >> 8) + b[0] и сохранить b[2] перенос из b[1].

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

Trotil, арифметика 8-битных чисел на базе uint16_t не подходит потому, что тут уже два типа по факту uint8_t и его расширение до uint16_t, появляются биты для хранения числа, а значит цифры можно сдвигать операторами сдвига << или >>, а надо на базе uint8_t сделать одну операцию из арифметика 16-битных чисел, и тут операторы сдвига не помогут на первый взгляд, отя потому, что двигать некуда.

[Trotil]

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

[Trotil]

Trotil, арифметика 8-битных чисел на базе uint16_t не подходит потому, что тут уже два типа по факту uint8_t и его расширение до uint16_t, появляются биты для хранения числа, а значит цифры можно сдвигать операторами сдвига << или >>, а надо на базе uint8_t сделать одну операцию из арифметика 16-битных чисел, и тут операторы сдвига не помогут на первый взгляд, отя потому, что двигать некуда.

Я не очень понял, почему нельзя... Ну если вдруг действительно нельзя, сделай 4-ёх битные на базе 8-ми битных

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

Trotil, спасибо, дошло до меня. Фактически умышленно в элемент заносится числа наполовину меньшие максимального, тогда место есть, сдвиг работает. Тогда получается представление 32разрядного будет состоять уже не из двух, а из 4ех элементов, а результат умножения из 8 элементов.

[Trotil]

Trotil, спасибо, дошло до меня. Фактически умышленно в элемент заносится числа наполовину меньшие максимального, тогда место есть, сдвиг работает. Тогда получается представление 32разрядного будет состоять уже не из двух, а из 4ех элементов, а результат умножения из 8 элементов.

Ура.
Всё правильно, только результат умножения всё равно из 4ех элементов, старшие биты теряются, хотя в некоторых архитектурах предусмотрено сохранение результата умножения в двух регистрах, например x86 результат операции imul двух 32-битных чисел сохраняется в EAX и EDX.

Терминологически неграмотно брать массивы из 8 элементов, если арифметика 32-битная, надо аккуратнее действовать.

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

Trotil, насколько понял объявление такое:
uint16_t a_high = { 0xff, 0xff }; // 1-ое число 16-разрядное
uint16_t a_low = { 0xff, 0xff} ; // 2-ое число 16-разрядное
uint16_t a = { a_high, a_low }; // 1-ое число 32-разрядное
и
uint16_t b_high = { 0xff, 0xff }; // 3-ье число 16-разрядное
uint16_t b_low = { 0xff, 0xff} ; // 4-ое число 16-разрядное
uint16_t b = { b_high, b_low }; // 2-ое число 32-разрядное

Формула такая
a * b = 16^2 * a_high * b_high +
16 * (a_high * b_low + a_low * b_high) +
a_low * b_low

Произведение и сложение 16-разрядных реализовываем в функциях, а при программировании формулы их вызываем.

[Trotil]

Попробуй, сделай тесты.

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

Trotil, интересный, конечно, трюк, понравился. Никогда не писал подобных алгоритмов. Вы, вероятно, удивились с подходом через функцию carry, но сразу скажу, если бы читал про "сужение числа" , то этот carry в голову бы даже не пришел. Даже сейчас удивляюсь как такой велосипед придумал.

[Trotil]

Вы, вероятно, удивились с подходом через функцию carry

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

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

Trotil, понял. Часа 3 назад сел за ноут и дописал через переполнение, все случаи не проверял, просто взял пример, чтобы на каждом шаге переполнение было и проверил. Параллельно выяснилось, что вот здесь lin.in.ua/tools/numconv.html калькулятор из dec в hex число 1346878763369683037669386354688 неправильно переводит, я уж думал код криво написал.

p.s. реализация функции mul() не нравится, хотелось бы как-то покомпактнее её записать, но ничего в голову не пришло...

Solution 1
// Result and overflow

#include <stdio.h>
#include <limits.h>

typedef unsigned int uint;

uint carry_add(uint a, uint b) {
	return a > UINT_MAX - b ? 1 : 0;
}

uint carry_mul(uint a, uint b) {
	uint sum = a, carry = 0;
	if (a > UINT_MAX / (b+1)) {
		while (b--) {
			if (sum > UINT_MAX - a) carry++;
			sum = sum + a;
		}
	}
	return carry;
}

void mul(uint a[], uint b[], uint res[]) {
	uint carry = 0;
	uint mul = 0;

	mul = a[1] * b[1];
	res[3] = mul + carry;
	carry = carry_mul(a[1], b[1] - 1) + carry_add(mul, carry);

	mul = a[0] * b[1] + a[1] * b[0];
	res[2] = mul + carry;
	carry = carry_mul(a[0], b[1] - 1) + carry_add(mul, carry);
	carry += carry_mul(a[1], b[0] - 1) + carry_add(mul, carry);
	
	mul = a[0] * b[0];
	res[1] = mul + carry;
	carry = carry_mul(a[0], b[0] - 1) + carry_add(mul, carry);

	res[0] = carry;

	printf("0x%x 0x%x 0x%x 0x%x \n", res[0], res[1], res[2], res[3]);
}

int main() {

	/////////////////////////////Carry test////////////////////////////////

	uint u[] = { 0x10000000u, 0x10000000u }; //               16^15 + 16^7 = 1 152 921 504 875 282 432
	uint v[] = { 0x00000110u, 0x00000110u }; // 16^10 + 16^9 + 16^2 + 16^1 = 1 168 231 104 784
	
	// u*v = 1 346 878 763 369 683 037 669 386 354 688
	// u*v = { 0x00000011 0x00000022 0x00000011 0x00000000 }

	/*calculate*/

	// u[1] * v[1] = 73 014 444 032 =                          0x00000011  0x00000000, carry = 17
	// u[0] * v[1] = 73 014 444 032 =              0x00000011  0x00000000            , carry = 17
	// u[1] * v[0] = 73 014 444 032 =              0x00000011  0x00000000            , carry = 17
	// u[0] * v[0] = 73 014 444 032 =  0x00000011  0x00000000                        , carry = 17
	
	//    result                    =    res[0]      res[1]      res[2]      res[3]
	
	
	
	uint res[] = { 0x00000000u, 0x00000000u, 0x00000000u, 0x00000000u }; // 0

	printf("//carry array test \n");

	mul(u, v, res);

	return 0;
}

Сейчас буду пробовать через усечение

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

Ещё один тест

	/////////////////////////////Carry test////////////////////////////////

	uint u[] = { 0x10010010u, 0x10001110u }; // 16^15 + 16^12 + 16^9 + 16^7 + 16^3 + 16^2 + 16^1
	uint v[] = { 0x00000100u, 0x01000110u }; // 16^10 + 16^6 + 16^2 + 16^1
	
	// u*v = 1 267 979 508 941 376 151 651 292 946 688
	// u*v = { 0x00000011 0x00000022 0x00000011 0x00000000 }

	// u*v = { 0x00000010 0x01121101 0x11312122 0x10122100 }
	//       { 0x00000010 0x01101121 0x11312122 0x10122100 }

	/*calculate*/

	// u[1] * v[1] = 4 503 745 925 882 112                        =                           0x00100022 0x10122100 , carry = 0x00100022
	// u[0] * v[1] = 19 347 850 304 467 579 472 707 584           =                0x00100111 0x11101100 0x00000000 , carry = 0x00100111
	// u[1] * v[0] = 295 152 707 846 142 951 424                  =                0x00000010 0x00111000 0x00000000 , carry = 0x00000010
	// u[0] * v[0] = 1 267 960 160 795 914 472 479 751 405 568    =     0x00000010 0x01001000 0x00000000 0x00000000 , carry = 0x00000010
	
	//    result                                                  =      res[0]      res[1]      res[2]    res[3]
	
	//                                                                { 0x00000010 0x01101121 0x11312122 0x10122100 }

Работает, поэтому заключу, что всё работает.

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

Код выше крашился в функции mul(), неправильно перенос считал при a[0]*b[1] + a[1]*b[0]. Исправленная окончательная версия.

#include <stdio.h>
#include <limits.h>
#include <stdint.h>

typedef uint16_t uint16;

uint16 carry_add(uint16 a, uint16 b) {
	return a > UINT16_MAX - b ? 1 : 0;
}

uint16 carry_mul(uint16 a, uint16 b) {
	uint16 sum = a, carry = 0;
	if (a > UINT16_MAX / (b+1)) {
		while (b--) {
			if (sum > UINT16_MAX - a) carry++;
			sum = sum + a;
		}
	}
	return carry;
}

void mul(uint16 a[], uint16 b[], uint16 res[]) {
	uint16 carry = 0;
	uint16 mul = 0;

	mul = a[1] * b[1];
	res[3] = mul + carry;
	carry = carry_mul(a[1], b[1] - 1) + carry_add(mul, carry);

	mul = a[0] * b[1] + a[1] * b[0];
	res[2] = mul + carry;
	carry = carry_add(a[0] * b[1], a[1] * b[0]) + carry_add(mul, carry);
	carry += carry_mul(a[0], b[1] - 1) + carry_mul(a[1], b[0] - 1);

	mul = a[0] * b[0];
	res[1] = mul + carry;
	carry = carry_mul(a[0], b[0] - 1) + carry_add(mul, carry);

	res[0] = carry;

	printf("0x%x 0x%x 0x%x 0x%x \n", res[0], res[1], res[2], res[3]);
}

int main() {

	/////////////////////////////Test////////////////////////////////

	uint16 u[] = { 0xffffu, 0xabcfu }; // 15*16^7 + 15*16^6 + 15*16^5 + 15*16^4 + 
	                                   // 10*16^3 + 11*16^2 + 12*16^1 + 15 = 4 294 945 743

	uint16 v[] = { 0xabcdu, 0x0968u }; // 10*16^7 + 11*16^6 + 12*16^5 + 13*16^4 + 
	                                   // 9*16^2 + 6*16^1 + 8 = 2 882 341 224
	
	uint16 res[] = { 0x0000u, 0x0000u, 0x0000u, 0x0000u }; // 0

	// u[1] * v[1] = 105 911 064   =                  0x0650  0x1318
	// u[0] * v[1] = 157 808 280   =          0x0967  0xf698
	// u[1] * v[0] = 1 934 416 323 =          0x734c  0xd9c3
	// u[0] * v[0] = 2 882 294 835 =  0xabcc  0x5433

	// res                         =  0xabcc  0xd0e7  0xd6ab  0x1318

	printf("//carry array test \n");

	mul(u, v, res);

	return 0;
}

[Trotil]

Я бы сделал следующий тест:

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

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

Trotil,

В варианте, который я предложил, Число 65535 размещается в массиве из двух элементов типа uint_16t, a[0]=0xff, a[1]=0xff
сложение, это b[0]=a[0]+a[0]=0x1fe, b[1]=a[1]+a[1]=0x1fe, и переносов: b[1] = (a[0] >> 8) + b[0] и сохранить b[2] перенос из b[1].

пробую написать сложение, но никак не получается.

Вот код

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


typedef uint16_t uint16;

int main() {

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

	uint16 sum[] = { 0x0ui16, 0x0ui16, 0x0ui16 };
	
	sum[0] = a[0] + b[0];                 // старший байт

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


	std::cout << "sum: " << std::hex << sum[2] << " " << sum[0] << " " << sum[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 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;
}

Вывод
sum: 1 fffe

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

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 };
	
	mul[0] = (a[0] * b[0]) >> 8;                    // старший байт
	mul[1] = ((a[0] * b[0]) << 8) + (a[1] * b[1]);  // младший байт

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

	return 0;
}

[Trotil]

Попробуй сначала разобраться с умножением на число 0xff.

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

Trotil, посмотрел книги, которые вы рекомендовали, Харриса оказывается знаю, мы это в универе проходили, верилог всё же другое как по мне дк.

p.s.
вообще думал мне задание на ООП кинут, а тут чистый сишник, как увидел, так сразу плохо стало
само задание сдал, но спортивный интерес остался, хочу через битовые сдвиги запилить
прогуглил интернет и что странно, эта тема как-то криво раскрыта в сети, как бы код есть, но не тот, который хотелось бы увидеть.

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

Trotil,

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


typedef uint16_t uint16;

int main() {

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

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

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

	return 0;
}

Вывод:
mul: fe ff01

Правильно работает, хм

[Trotil]

А дальше схема, как при умножении в столбик: взять второй байт, умножить, сдвинуть результат (на сколько?), сложить с результатом, полученным на первом шаге, взять третий байт и т.д. Вроде несложно.