ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
25 сообщений из 207, страница 6 из 9
  6  все
Длинная арифметика. Вопросы по реализации/оптимизации
    #38817986
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вот что получил в итоге. Но этот код плохой. Плохая работа с памятью, как минимум
Код: 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.
//Сочетания
char* la_combination(unsigned n, unsigned m)
{
	int* up = (int*)malloc(sizeof(int)*m);//числитель
	int* down = (int*)malloc(sizeof(int)*m);//знаменатель
	for (int i = 1; i <= m; ++i)
	{
		*(up + i - 1) = n - m + i;
		*(down + i - 1) = i;
	}

	//сокращаем знаменатель в один проход. Необходимо обоснование того, что это можно сделать за один проход
	for (int i = 0; i < m; ++i)
	{
		if (down[i] != 1)
		{
			for (int j = 0; j < m; ++j)
			{
				if (!(up[j] % down[i]))
				{
					up[j] /= down[i];
					down[i] = 1;//если этот алгоритм верный, то эта строчка не нужна
				}
			}
		}
	}
	char* res="1";
	for (int i = 0; i < m; ++i)
	{
		char* t = (char*)malloc(10);//обоснование числа
		sprintf(t, "%d", up[i]);
		res = la_multiplication(res, t);
	}
	return res;
}
...
Рейтинг: 0 / 0
27.11.2014, 08:02
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38817990
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
up и down - состояние (сетевых) интерфейсов, а не положение чисел в дробях. Ну или направления движения
Кроме того, хотя могу и ошибаться, но требуются очень веские причины, чтобы выделять целые в куче. Внутри функции - мне даже в голову ничего не приходит.
С числителем - да, опечатался.
...
Рейтинг: 0 / 0
27.11.2014, 08:10
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38817996
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Перепишем дробь в таком виде:
Код: sql
1.
2.
3.
(1 * 2 * ... * n)
/
( (1 * 2 * ... (n -m)) * (1 * 2 * ... m) )

Можно не перемножать числа в диапазоне от min(m, n-m) до max(m, n-m), включительно.
Но, учитывая высокую скорость рост факториала, надо взять (асимптотическую) аналитическую формулу и считать (натуральный) логарифм числа сочетаний. И потенцировать по мере надобности.
...
Рейтинг: 0 / 0
27.11.2014, 08:20
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38817997
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Basil A. Sidorov Кроме того, хотя могу и ошибаться, но требуются очень веские причины, чтобы выделять целые в куче. Внутри функции - мне даже в голову ничего не приходит

не очень понял, объясните пожалуйста.

PS Доводы по поводу up и down принимаю и буду иметь в виду. Спасибо :)
...
Рейтинг: 0 / 0
27.11.2014, 08:26
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818002
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
	char* res="1";
	char* t = (char*)malloc(10);
	for (int i = 0; i < m; ++i)
	{
		sprintf(t, "%d", up[i]);
		res = la_multiplication(res, t);
	}
	free(t);



тут немного изменил. но проблема не в этом, а в том как я работаю с res. в la_multiplication происходи malloc, и потом память не освобождается.
...
Рейтинг: 0 / 0
27.11.2014, 08:35
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818022
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Basil A. Sidorovв диапазоне от min(m, n-m) до max(m, n-m), включительноНижняя исключительно, верхняя - включительно, т.е. от (min(n, n-m) + 1) до max(n, n-m).
...
Рейтинг: 0 / 0
27.11.2014, 09:13
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818038
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
SashaMercuryне очень понял, объясните пожалуйстаЕсть регистры, статическая память, стек и куча.
Первых двух касаться не будем.
Запись:
Код: sql
1.
int* var = (int*) malloc(somesize);

даёт нам переменную для указателя на стеке и отдельно, со своими накладными расходами, область памяти для хранения целого в куче.
Возникает вопрос - зачем? Чтобы израсходовать лишнюю память на хранение, процессорные такты на выделение и косвенную адресацию, а потом ещё решать проблему утечек?
Почему нельзя делать просто:
Код: sql
1.
int var;

?
...
Рейтинг: 0 / 0
27.11.2014, 09:21
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818047
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Basil A. SidorovBasil A. Sidorovв диапазоне от min(m, n-m) до max(m, n-m), включительноНижняя исключительно, верхняя - включительно, т.е. от (min(n, n-m) + 1) до max(n, n-m).
понял вас )
В моей программе это исправляется одной строчкой
Код: plaintext
1.
2.
3.
4.
char* la_combination(unsigned n, unsigned m)
{
	m = (n - m > m) ? m : n-m;
...




SSBasil A. Sidorov Кроме того, хотя могу и ошибаться, но требуются очень веские причины, чтобы выделять целые в куче. Внутри функции - мне даже в голову ничего не приходит

не очень понял, объясните пожалуйста.

PS Доводы по поводу up и down принимаю и буду иметь в виду. Спасибо :)
...
Рейтинг: 0 / 0
27.11.2014, 09:23
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818052
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Basil A. SidorovSashaMercuryне очень понял, объясните пожалуйстаЕсть регистры, статическая память, стек и куча.
Первых двух касаться не будем.
Запись:
Код: sql
1.
int* var = (int*) malloc(somesize);

даёт нам переменную для указателя на стеке и отдельно, со своими накладными расходами, область памяти для хранения целого в куче.
Возникает вопрос - зачем? Чтобы израсходовать лишнюю память на хранение, процессорные такты на выделение и косвенную адресацию, а потом ещё решать проблему утечек?
Почему нельзя делать просто:
Код: sql
1.
int var;

?

а как я массивы буду хранить ?
...
Рейтинг: 0 / 0
27.11.2014, 09:26
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818059
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
SashaMercuryа как я массивы буду хранить ?Как-то так:
Код: sql
1.
int arr[] = {0, 0, 0, 0, 0, 0};



P.S. Я бы посмотрел на уже имеющиеся пакеты длинной арифметики прежде, чем начать изобретать собственный велосипед.
Чтобы не делать треугольных колёс.
...
Рейтинг: 0 / 0
27.11.2014, 09:31
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818061
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryСделал умножение, алгоритм мне не нравится, ибо мне кажется что он далеко не оптимален. Тут код С++, потому что мне сложно отказаться от тернарного оператора. Он мне слишком нравится, чтобы его не использовать
Саш... ну слов нет. Мне кажется чтение стандартов тебе только вредит.
Каша у тебя в голове. Пиши весь код на С++. Делай file extension на как с++.
...
Рейтинг: 0 / 0
27.11.2014, 09:34
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818068
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Сочетания в один проход не работают. Пример .
...
Рейтинг: 0 / 0
27.11.2014, 09:36
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818070
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonSashaMercuryСделал умножение, алгоритм мне не нравится, ибо мне кажется что он далеко не оптимален. Тут код С++, потому что мне сложно отказаться от тернарного оператора. Он мне слишком нравится, чтобы его не использовать
Саш... ну слов нет. Мне кажется чтение стандартов тебе только вредит.
Каша у тебя в голове. Пиши весь код на С++. Делай file extension на как с++.

почему каша ?( мне просто очень нравится этот оператор :(
...
Рейтинг: 0 / 0
27.11.2014, 09:37
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818079
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercurymaytonпропущено...

Саш... ну слов нет. Мне кажется чтение стандартов тебе только вредит.
Каша у тебя в голове. Пиши весь код на С++. Делай file extension на как с++.

почему каша ?( мне просто очень нравится этот оператор :(
Тернарный оператор был изначально в "C". Это замечание к твоей фразе
о выборе С или С++. (я надеюсь третьего варианта здесь нет).
...
Рейтинг: 0 / 0
27.11.2014, 09:46
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818084
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonSashaMercuryпропущено...


почему каша ?( мне просто очень нравится этот оператор :(
Тернарный оператор был изначально в "C". Это замечание к твоей фразе
о выборе С или С++. (я надеюсь третьего варианта здесь нет).

В Си тернарный оператор используется только для присваивания, а не для того, как я люблю его использовать.
...
Рейтинг: 0 / 0
27.11.2014, 09:52
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818087
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вот ещё скриншот
...
Рейтинг: 0 / 0
27.11.2014, 09:55
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818092
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercury
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
	char* res="1";
	char* t = (char*)malloc(10);
	for (int i = 0; i < m; ++i)
	{
		sprintf(t, "%d", up[i]);
		res = la_multiplication(res, t);
	}
	free(t);



тут немного изменил. но проблема не в этом, а в том как я работаю с res. в la_multiplication происхомди malloc, и потом память не освобождается.
Атомарные типы на стеке удаляются автоматом при выходе из функции. Например если ты написал
функцию int sum(int x,int y) которая просто складывает два числа и возвращает резалт - то ты
имеешь замечательную возможность использовать рекуррентные формы такие как:

Код: plaintext
1.
sum(x,0);



Код: plaintext
1.
sum(x,sum(y,0));



То-же самое для char* это сделать сложно т.к. мы теряем результата второго каллбэка sum(..)
и он утекает вникуда до тех пор пока ОС не завершит процесс. Вобщем получаем мемори лик.

Это дефект или артефакт "C"-like декларации функции которая должна ВЕРНУТЬ строку. И ему уже 100 лет
в обед. Здесь сам Бог или Страуструп велит использовать С++/STD с шаблонами строк или чисел.

Опять же странно что ты здесь не использовал возможности С++.
...
Рейтинг: 0 / 0
27.11.2014, 10:00
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818097
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercury, по поводу присваивания - ОК. Убедил. Но не злоупотребляй синтаксисом.
Знавал я перцев которые тело цикла for переносили в выражение for. Код работал
но при этом был аццки нечитабелен. Были красавцы которые любят ВЛОЖЕННЫЙ
тернарный оператор или пытаются КАЖДЫЙ if в коде разложить в тернарность.
Где-то получается. Где-то нет. Разумеется читать код - невозможно. Хочется
руки оторвать.
...
Рейтинг: 0 / 0
27.11.2014, 10:04
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818103
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonТо-же самое для char* это сделать сложно т.к. мы теряем результата второго каллбэка sum(..)
и он утекает вникуда до тех пор пока ОС не завершит процесс. Вобщем получаем мемори лик.

Это дефект или артефакт "C"-like декларации функции которая должна ВЕРНУТЬ строку. И ему уже 100 лет
в обед. Здесь сам Бог или Страуструп велит использовать С++/STD с шаблонами строк или чисел.

Опять же странно что ты здесь не использовал возможности С++.

создам реплику той функции, которая будет освобождать память для аргументов перед выходом. Не использовал возможности, потому что не знаю их.
maytonSashaMercury, по поводу присваивания - ОК. Убедил C:
...
Рейтинг: 0 / 0
27.11.2014, 10:08
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818116
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryА вот сейчас делаю сочетания, может быть кто-нибудь подскажет как обосновать что этот алгоритм будет работать за один проход ? Либо обратное ?

По поводу расчёта сочетаний. Алгоритм не смотрел пока. Ничего не скажу. Для опровержения
его нужно тестить. Для доказательства - х.з. Можно взять канонический и через эквивалентные
преобразования доказать равенство. Но впрочем в процессе преобразований можно наломать боков.
Так что... путь долгий.

По поводу прямой формулы. Она редко используется для больших чисел. В числителе и знаменателе - аццки
огромные числа хотя впрочем частное не такое великое. Разумеется математи середины 20 века не имели
технически возможности посчитать большой факториал. ПОэтому обычно берут приближённый
расчёт через Пуассончик. Интеграл Пуассона. Он даёт вполне приемлемую точность. Поскольку
Пуассончик - неберущийся то обычно используют его табличное задание. А в софте - интеграл методом
прямоугольников.

Если функция С(m,n) будет стоять под оптимизацией то можно использовать Треугольник Паскаля как кеш
или частичную мемоизацию. Суть в том что если вы раньше расчитали С(m-1,n), C(m,n-1) то С(m,n) можно
получить просто сложением от ранее расчитанного.
...
Рейтинг: 0 / 0
27.11.2014, 10:17
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818119
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryНе использовал возможности, потому что не знаю их.
Да што там. Подключ std::string и используй их как хранилище целых чисел вместо char *.
Заодно и утечки уйдут.
...
Рейтинг: 0 / 0
27.11.2014, 10:20
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818121
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
maytonПодключ std::string и используй их как хранилище целых чиселБолее логичным выглядит vector<int> или как его там.
Это, опять-таки, если изобретать велосипед.
...
Рейтинг: 0 / 0
27.11.2014, 10:23
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818130
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Не... ему символы блихе IMHO.
...
Рейтинг: 0 / 0
27.11.2014, 10:25
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818132
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Марк, мне нужно точное значение.
За один проход не сработает. Нужно думать как делать иначе.
Проще всего взять готовую реализацию, готовую библиотеку и использовать её. Если я когда-нибудь буду работать программистом С++, то вероятно буду делать так. Но мне нравится программировать, и нравится думать, потому я буду делать это так, как начал делать. Без использования того, что уже реализовано, и не смотря на то, как где-то сделано
...
Рейтинг: 0 / 0
27.11.2014, 10:27
| Ответить | Цитировать | Написать  
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818135
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonНе... ему символы блихе IMHO.

это правда :) я лучше чувствую то с чем работаю
...
Рейтинг: 0 / 0
27.11.2014, 10:28
| Ответить | Цитировать | Написать  
25 сообщений из 207, страница 6 из 9
  6  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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