powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
25 сообщений из 207, страница 2 из 9
Длинная арифметика. Вопросы по реализации/оптимизации
    #38725126
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Лучше - размер/size :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38725266
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky,

под размером обычно понимается число занимаемых байт.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38726028
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RWolfпод размером обычно понимается число занимаемых байт.
Нет такого обычая.
Размер это просто размер. В любых единицах.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38726029
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЯ могу сказать "половина сантиметра", но не могу сказать "половина символа".Вот математик может быть и не может сказать "половина символа", а тот кто изучает computer science может...
Существует единица измерения "ниббл" (nibble) которая как раз и является половиной символа.
В нынешнее время она почти не используется, но...

SashaMercuryПривел несколько доводов в пользу слова мощность.Неубедительные доводы.


SashaMercuryПросто хочу понять почему так.Термины придумываются так, чтобы наиболее точно отражать внутреннюю сущность описываемого объекта. Потом, с течением времени, могут появляться искажения терминов или смена сущности объекта, тогда термин перестает быть прямым описанием сущности и становится просто традиционным названием. И тогда остается только зазубривать его...
А еще бывают жаргонные словечки которые оказались настолько удобны что доросли до статуса терминов, при этом все уже забыли источник этого жаргонизма...

И в любом случае, прочитай совет mayton'а еще раз и прими его.


SashaMercuryПока делаю вывод: "Слово мощность подходит, но лучше использовать слово длина, в силу исторических причин". Понял. Больше на эту тему не дискутирую. Раз всем так не нравится. Возможно, дело в том что я слишком мало знаю в IT, потому так рассуждаю.Слово мощность совсем не подходит.
Я тебе уже говорил и повторю еще раз: математика и информатика это две разные науки.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38776909
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте, Сообщество C:

SS4. Где обоснование что числа в длинной арифметике нужно хранить реверсом (хотя вот тут я его не виню, может быть это очевидно для людей со степенью PhD(тут без иронии говорю))

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

Хочу увидеть классическое, грамотное решение данное задачи. Понимаю, что вы можете снова предложить погуглить(Анатолий ), но результаты этого процесса я обсуждал выше, то что я нашёл мне не понравилось, причём не понравилось обоснованно(как мне кажется).
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38777026
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЗдравствуйте, Сообщество C:

SS4. Где обоснование что числа в длинной арифметике нужно хранить реверсом (хотя вот тут я его не виню, может быть это очевидно для людей со степенью PhD(тут без иронии говорю))

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

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

gmp изучал ?

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

P.S. Мало кто понимает, но мы все (большинство европейцев) пишем слова СЛЕВА НАПРАВО, а числа -- СПРАВА НАЛЕВО, и только арабы (ну, и евреи разумеется) пишут и то, и то одинаково. Для правильного написания текста, состоящего из цифр и букв разных алфавитов придуман специальный алгоритм, именуемый BIDI, и зафиксированный в спецификации UNICODE.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38779277
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Нет, gmp не изучал. Сейчас посмотрю.
Переделал алгоритм, не то чтобы переделал, просто написал заново, смотрю на свой предыдущий код, и вижу много различий. Код стал другой. Странно. Буду разбираться.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38779279
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вы имеете ввиду систему норм и правил в отношении производства или библиотеку Си для вычислений с плавающей точкой ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790101
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Сегодня читал Спинеллиса, Анализ программного кода. Встретил описание интересных функций, memset,memcpy,memmove. Посмотрите какой код я предлагаю в качестве оптимального(на данный момент, буду рад предложениям по оптимизации) для сложения двух длинных неотрицательных чисел до использования этих функций.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
#define MAX_POW 1001+1
//сумма двух целых неотрицательных чисел s1,s2>=0
char* la_sum(const char* s0, const char* s1)
{
	int len[2] = { strlen(s0), strlen(s1) };
	int max_i = (len[0] > len[1]) ? 0 : 1; //индекс максимальной строки
	int min_i = 1 - max_i;//индекс минимальной строки
	const char* max_s = (max_i == 0) ? s0 : s1;
	const char* min_s = (min_i == 0) ? s0 : s1;

	if (len[max_i] > MAX_POW - 1)
	{
		printf("Incorrect size of the string(s).\n");
		return NULL;
	}
	
	int len_res = len[max_i] + 1 + 1;//просим на 1 Байт больше чтобы исключить вероятность повторного аллоцирования
	char* res = (char*)malloc(len_res*sizeof(char));
	for (int i = 0; i < len_res; ++i)
	{
		*(res + i) = '0';
	}


	for (int i = 0; i < len[min_i]; ++i)//пишем в конец результирующей строки минимальное число
	{
		*(res + len[max_i] - len[min_i] + i + 1) = *(min_s + i);
	}

	//основная часть алгоритма
	int d = 0;
	for (int i = len_res - 2; i > 0; i--)
	{
		int t0 = *(res + i) + *(max_s + i-1) + d - 2 * '0';
		int t1 = t0 % 10;
		*(res + i) = t1 + '0';
		d = (t0>=10) ? 1 : 0;
	}
	*(res + len_res - 1) = '\0';
	if (d == 0)//сдвиг
	{
		for (int i = 0; i < len_res-1; ++i)
		{
			*(res + i) = *(res + i + 1);
		}
	}
	else
	{
		*(res + 0) = d + '0';
	}
	return res;
}



Чем меня раньше смущала такой участок кода ?
Код: plaintext
1.
2.
3.
4.
	for (int i = 0; i < len_res; ++i)
	{
		*(res + i) = '0';
	}


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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
char* la_sum2(const char* s0, const char* s1)
{
	int len[2] = { strlen(s0), strlen(s1) };
	int max_i = (len[0] > len[1]) ? 0 : 1; //индекс максимальной строки
	int min_i = 1 - max_i;//индекс минимальной строки
	const char* max_s = (max_i == 0) ? s0 : s1;
	const char* min_s = (min_i == 0) ? s0 : s1;

	if (len[max_i] > MAX_POW - 1)
	{
		printf("Incorrect size of the string(s).\n");
		return NULL;
	}

	int len_res = len[max_i] + 1 + 1;//просим на 1 Байт больше чтобы исключить вероятность повторного аллоцирования
	char* res = (char*)malloc(len_res*sizeof(char));
	memset(res, '0', len_res);//установка стартового значения
	memcpy(res + len[max_i] - len[min_i] + 1, min_s, len[min_i]);//пишем в конец результирующей строки минимальное число

	//основная часть алгоритма
	int d = 0;
	for (int i = len_res - 2; i > 0; i--)
	{
		int t0 = *(res + i) + *(max_s + i - 1) + d - 2 * '0';
		int t1 = t0 % 10;
		*(res + i) = t1 + '0';
		d = (t0 >= 10) ? 1 : 0;
	}
	*(res + len_res - 1) = '\0';
	if (d == 0)
	{
		memmove(res, res + 1, len_res - 1);//сдвиг
	}
	else
	{
		*(res + 0) = d + '0';
	}
	return res;
}



Код стал более читабелен, и нравится мне больше. Хотя вероятно я проигрываю в скорости и памяти на этом участке кода

Код: plaintext
1.
2.
3.
4.
		for (int i = 0; i < len_res-1; ++i)
		{
			*(res + i) = *(res + i + 1);
		}



ибо

Код: plaintext
1.
memmove(res, res + 1, len_res - 1);//сдвиг



известно как работает.

ISO/IEC 9899:201xThe memmove function copies n characters from the object pointed to by s2 into the
object pointed to by s1. Copying takes place as if the n characters from the object
pointed to by s2 are first copied into a temporary array of n characters that does not
overlap the objects pointed to by s1 and s2, and then the n characters from the
temporary array are copied into the object pointed to by s1.

Конечно -же я не удержался, и использовал чудесный тернарный оператор. MasterZiv, не ругайтесь пожалуйста, но разве этот код не кажется вам более компактным и более понятным ? Я согласен с вами, Си-программисты так делают редко, это возможно плохой тон. Но это так красиво, что мне порой трудно удержаться.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
char* la_sum3(const char* s0, const char* s1)
{
	int len[2] = { strlen(s0), strlen(s1) };
	int max_i = (len[0] > len[1]) ? 0 : 1; //индекс максимальной строки
	int min_i = 1 - max_i;//индекс минимальной строки
	const char* max_s = (max_i == 0) ? s0 : s1;
	const char* min_s = (min_i == 0) ? s0 : s1;

	if (len[max_i] > MAX_POW - 1)
	{
		printf("Incorrect size of the string(s).\n");
		return NULL;
	}

	int len_res = len[max_i] + 1 + 1;//просим на 1 Байт больше чтобы исключить вероятность повторного аллоцирования
	char* res = (char*)malloc(len_res*sizeof(char));
	memset(res, '0', len_res);//установка стартового значения
	memcpy(res + len[max_i] - len[min_i] + 1, min_s, len[min_i]);//пишем в конец результирующей строки минимальное число

	//основная часть алгоритма
	int d = 0;
	for (int i = len_res - 2; i > 0; i--)
	{
		int t0 = *(res + i) + *(max_s + i - 1) + d - 2 * '0';
		int t1 = t0 % 10;
		*(res + i) = t1 + '0';
		d = (t0 >= 10) ? 1 : 0;
	}
	*(res + len_res - 1) = '\0';
	(!d) ? (char)memmove(res, res + 1, len_res - 1) : *(res + 0) = d + '0';
	
	return res;
}




Используете ли вы функции которые я сегодня встретил ? Не проигрываю ли я в скорости при их использовании(кроме memmove) ?
Правильно ли я понял, memmove лучше не использовать ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790679
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Алгоритм использующий malloc не может быть оптимальным :)
Начните с того что отделите выделение памяти от собственно вычислений.
Всегда можно сделать функцию поверх них, которая их совместит.

memmove в вашем алгоритме не нужна, т.к. нет пересекающихся областей памяти, memcpy - быстрее в теории.

Ну и если речь зашла про оптимальность, то хранить и обрабатывать числа в виде десятичных цифр - это далеко не оптимально. Храните в виде 32- или 64-битных двоичных цифр размером в машинное слово.
В этом случае ускорятся вычисления, но затормозится отображение (что практически никогда не является критичным)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790738
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyНу и если речь зашла про оптимальность, то хранить и обрабатывать числа в виде десятичных цифр - это далеко не оптимально. Храните в виде 32- или 64-битных двоичных цифр размером в машинное слово.
В этом случае ускорятся вычисления, но затормозится отображение (что практически никогда не является критичным)
Если стоит задача делать финансовые расчёты и часто-часто делать конверсию BIN=>DEC=>BIN для публикации то
я-бы предложил BCD.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790751
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

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

ЗЫ. Не говоря уже о том что для финрасчетов никакая длинная арифметика не нужна :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790764
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати Oracle хранит мантиссу числа Number в виде цифры 100-ричной системы в двоичном виде в каждом байте.
Никакого преимущества при отображении по сравнению с хранением по словам этот формат не дает. И так и так надо в цикле получать остатки для перевода в десятичную систему.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790774
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky, согласен насчёт агрегаций и прочей другой аналитики.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790801
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyКстати Oracle хранит мантиссу числа Number в виде цифры 100-ричной системы в двоичном виде в каждом байте.
Никакого преимущества при отображении по сравнению с хранением по словам этот формат не дает. И так и так надо в цикле получать остатки для перевода в десятичную систему.
Зачем? одна 100-ричная цифра это ровно две десятичных.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790816
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RWolfЗачем? одна 100-ричная цифра это ровно две десятичных.
Вот вам одна 100-ричная цифра в двоичном виде: 01011000
Отобразите ее в десятичной системе без деления :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790819
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотя я допускаю, что я что-то неверно помню, и оракл хранит все-таки в BCD - по 10-ичной цифре в каждых 4 разрядах.
В этом случае конечно не требуется никаких особых действий для отображения.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790838
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyВот вам одна 100-ричная цифра в двоичном виде: 01011000
Отобразите ее в десятичной системе без деления :)
Код: sql
1.
printf("%2.2d", 0b01011000);


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790850
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov0b01011000
Жалко что С/С++ такого не умеют
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790875
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyЖалко что С/С++ такого не умеют
Умеют. Это документация про такую фичу не знает.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790885
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovУмеют. Это документация про такую фичу не знает.
Че, прямо все умеют?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790901
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyЧе, прямо все умеют?
Мелкомягкое поделие - не умеет. Но от него никто и не может ожидать соответствия
стандартам или спецификациям K&R.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790906
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyRWolfЗачем? одна 100-ричная цифра это ровно две десятичных.
Вот вам одна 100-ричная цифра в двоичном виде: 01011000
Отобразите ее в десятичной системе без деления :)
В чём проблема?
01011000 / 10 = 8
01011000 % 10 = 8
результат: 88
Заметьте, мне не пришлось искать остаток от деления всего числа на 10, я ограничился одной цифрой. А мог вообще обойтись таблицей на 100 входов.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790957
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RWolfА мог вообще обойтись таблицей на 100 входов.
Да, это оно.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38790967
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyОтобразите ее в десятичной системе без деления :)
Деление на вычитание в цикле можно заменить, только еще медленнее будет.
...
Рейтинг: 0 / 0
25 сообщений из 207, страница 2 из 9
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]