powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
25 сообщений из 207, страница 7 из 9
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818262
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати. Подумай над библиотекой рациональных чисел. Так чтобы 1/3 + 2/3 точно равнялось 1.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818460
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovSashaMercuryа как я массивы буду хранить ?Как-то так:
Код: sql
1.
int arr[] = {0, 0, 0, 0, 0, 0};



P.S. Я бы посмотрел на уже имеющиеся пакеты длинной арифметики прежде, чем начать изобретать собственный велосипед.
Чтобы не делать треугольных колёс.

массив формируется динамически, я не могу хранить его в таком виде.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818464
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonКстати. Подумай над библиотекой рациональных чисел. Так чтобы 1/3 + 2/3 точно равнялось 1.

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

https://ru.wikipedia.org/wiki/Алгоритм_Евклида

Если взять более общий случай (знаменатели разные) то тебе понадобиться
приведение к общему знаменателю. Я в этой задаче пошёл по самому длинному пути.
Я раскладывал числа на множители. Для этого мне нужны были все primes в диапазоне
знаменателей. Потом я делал булевы операции над primes и получал НОК.

Делал сложение числителей с учотов весов. И ... хопа. Снова нужно сокращать.
Раскладывал полученый числитель на множители ну вобщем трахомозг.

Вобщем я отказался от разложения на primes по одной простой причине. Алгоритм
Евклида позволил сделать сокращение дроби без разложения на множители.
Это воистину полезный и замечательный алгоритм. Как говоится из серии must have.

А от приведения к общ знаменателю я отказался. Я просто множил оба знаменателя.
Один хрен.. Евклид работал быстрее любого разложения. И его фаза была финальной
в обоих вариантах. Вобщем НОК оказался не нужен.

P.S. Попытка разлагать числа на primes вызвала у меня много часов безсонницыт
и несколько килобайт букв на этом форуме. Вобщем к этой задаче я еще вернусь.
Если будет интересно. Эффективный алго prime-gen я так и не создал. Но гораздо ценнее
были практические знания из теории чисел которые я получил в процессе.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38818945
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, так у вас работают сочетания ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38819057
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если честно я еще не смотрел. А что?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38819346
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Наведи порядок в сорцах. У тебя аллоцирование памяти "C"-like, а циклы используешь от С++.

Вобщем сделай нормальное приложение. С точкой входа в программу.

Давай удачи.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38819368
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonУ тебя аллоцирование памяти "C"-like, а циклы используешь от С++.
Уже 15 лет как в С можно объявлять переменную прямо в цикле :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38819416
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ох увы мне увы. Сижу на старых Сях.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821006
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Подскажите пожалуйста, имеет место быт такой код ? Меня больше интересуют моменты касаемо isFreeMemory

Код: 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.
53.
54.
//выделение len Байт
char* allocate_memory(size_t len)
{
	return (char*)malloc(len*sizeof(char));
}

//освобождение памяти
int freeMemory(char* s1,char* s2,int isFreeMemory)
{
	if (isFreeMemory >= 1)
		free(s1);
	if (isFreeMemory >= 2)
		free(s2);
	return 0;
}



//СУММА
//s1>=s2
int la_sum_inplace(char* sum, size_t p, char* s1, size_t p1, char* s2, size_t p2)
{
	memset(sum, '0', p); *(sum + p - 1) = '\0';//установка стартового значения
	memcpy(sum + p1 - p2 + 1, s2, p2-1);//пишем в конец результирующей строки минимальное число
	int d = 0;
	for (int i = p - 2; i > 0; i--)
	{
		int t0 = *(sum + i) + *(s1 + i - 1) + d - 2 * SHIFT;
		int t1 = t0 % 10;
		*(sum + i) = t1 + '0';
		d = (t0 >= 10) ? 1 : 0;
	}
	if (!d && p!=2)
		memmove(sum, sum + 1, p - 1);
	else
		*(sum + 0) = d + '0';
	return 0;
}

//s1+s2      s1,s2>=0
char* la_sum(char* s1, char* s2, int isFreeMemory)
{
	size_t p[2] = { strlen(s1)+1, strlen(s2)+1 };
	int max_i = (p[0] > p[1]) ? 0 : 1; //индекс максимальной строки
	int min_i = 1 - max_i;//индекс минимальной строки
	char* max_s = (max_i == 0) ? s1 : s2;
	char* min_s = (min_i == 0) ? s1 : s2;

	int p_res = p[max_i] + 1;//просим на 1 Байт больше чтобы исключить вероятность повторного аллоцирования
	char* res = allocate_memory(p_res);
	la_sum_inplace(res, p_res, max_s, p[max_i], min_s, p[min_i]);	// calculate in-place	
	freeMemory(s1, s2, isFreeMemory);
	return res;
}
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821007
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Разбираюсь с этой memory leak .. Пока что она меня бьёт больше чем я её
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821022
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Возьми себе за правило устанавливать указатель в NULL после освобождения памяти. Тогда отлаживать проще будет.
Схематично так
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
char* p = NULL;
....
if(p) {
   ... память уже выделена
} else {
   p = malloc(...);
}
... работаем с p
free(p);
p = NULL;
...
if(p) {
  ... память не освобождена
}
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821072
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
//освобождение памяти
int freeMemory(char* s1,char* s2,int isFreeMemory)
{
	if (isFreeMemory >= 1)
		free(s1);
	if (isFreeMemory >= 2)
		free(s2);
	return 0;
}

s2 никогда не освободится, есичё ))
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821077
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TВозьми себе за правило устанавливать указатель в NULL после освобождения памяти. Тогда отлаживать проще будет.а лучше взять себе за правило использовать для каждой задачи свою локальную переменную, тогда отлаживать будет ещё проще, особенно, если давать им имена чуть более осмысленные, чем "р", "с" и прочие "ab" )))
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821083
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, и почему бы не инициализировать переменную прямо по месту её объявления.
Схематично так
Код: plaintext
1.
2.
3.
char* p = malloc(...);
... работаем с p
free(p);
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821114
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychDima T, и почему бы не инициализировать переменную прямо по месту её объявления.
Схематично так
Код: plaintext
1.
2.
3.
char* p = malloc(...);
... работаем с p
free(p);


Когда так можно сделать, то и проблем нет.

Я общий случай описал.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821126
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychSashaMercury
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
//освобождение памяти
int freeMemory(char* s1,char* s2,int isFreeMemory)
{
	if (isFreeMemory >= 1)
		free(s1);
	if (isFreeMemory >= 2)
		free(s2);
	return 0;
}

s2 никогда не освободится, есичё ))глупость я написал, освободится, конечно
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821137
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TegorychDima T, и почему бы не инициализировать переменную прямо по месту её объявления.
Схематично так
Код: plaintext
1.
2.
3.
char* p = malloc(...);
... работаем с p
free(p);


Когда так можно сделать, то и проблем нет.

Я общий случай описал.если сразу проектировать программу в этом стиле, то он и будет общим случаем, с 95% вероятностью
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821267
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychDima Tпропущено...

Когда так можно сделать, то и проблем нет.

Я общий случай описал.если сразу проектировать программу в этом стиле, то он и будет общим случаем, с 95% вероятностью
На вкус и цвет ...
Задачи разные бывают. У меня на С в основном DLL-ки вспомогательные, которые грузятся всегда, а задействованы могут быть пару раз в году. Какой смысл напрягать проц лишними операциями при загрузке?
Поэтому лично я предпочитаю инициализировать NULL, а при необходимости память выделить.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821345
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryРазбираюсь с этой memory leak .. Пока что она меня бьёт больше чем я её
Саш. А ты себя позиционируешь как Windows-C++ разработчик? Или есть другие варианты?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821723
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TУ меня на С в основном DLL-ки вспомогательные, которые грузятся всегда, а задействованы могут быть пару раз в году. Какой смысл напрягать проц лишними операциями при загрузке?что бы это значило? в коде char *prt = malloc(...); процессор напрягается в момент исполнения этой строчки кода, если ptr - не глобальный объект. Если функция из dll используется 2 раза в год, то и такая строчка исполнится 2 раза в год, при загрузке библиотеки только DllMain исполняется автоматом.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821945
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Интересные темы обсуждаете господа, даже поиграть забыл ...
maytonSashaMercury, даю подсказку. В сложении дробей помогает алгоритм Евклида.

https://ru.wikipedia.org/wiki/Алгоритм_Евклида

Если взять более общий случай (знаменатели разные) то тебе понадобиться
приведение к общему знаменателю. Я в этой задаче пошёл по самому длинному пути.
Я раскладывал числа на множители. Для этого мне нужны были все primes в диапазоне
знаменателей. Потом я делал булевы операции над primes и получал НОК.

Делал сложение числителей с учотов весов. И ... хопа. Снова нужно сокращать.
Раскладывал полученый числитель на множители ну вобщем трахомозг.

Вобщем я отказался от разложения на primes по одной простой причине. Алгоритм
Евклида позволил сделать сокращение дроби без разложения на множители.
Это воистину полезный и замечательный алгоритм. Как говоится из серии must have.

А от приведения к общ знаменателю я отказался. Я просто множил оба знаменателя.
Один хрен.. Евклид работал быстрее любого разложения. И его фаза была финальной
в обоих вариантах. Вобщем НОК оказался не нужен.

Жёстко ...
a*b = НОК(a,b) * НОД(a,b) - спасибо моему учителю, долгих ему лет здоровья

mayton, а что там с СС Фибоначи, так интересно начиналось?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821965
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У, как у вас тут интересно...
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38821993
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну вобщем Фибоначчи я задумывал как один из способов организации кеша Primes.
В отличие от кодов Левеншнтейна код Фибоначчи подкупает своей простотой.
Но развивая идею я думал о реализации основных 4-х арифметических операциях.
И хотя для задачи cachePrimes сложение и вычитание не является необходимостью
я просто обобщал и решил а "почему-бы и нет". В мохнатые времена один Росиянин
создавал ЭВМ работающую на "троичной" арифметике. Вобщем полёту фантазии нет
предела.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822089
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.

Дмитрий, спасибо, я попробую сейчас, исправлю кое-что:)


maytonSashaMercuryРазбираюсь с этой memory leak .. Пока что она меня бьёт больше чем я её
Саш. А ты себя позиционируешь как Windows-C++ разработчик? Или есть другие варианты?

Марк, Нет конечно, какой из меня Программист, или Разработчик. Уже говорил свою позицию по значению слова Программист (Разработчик). Позиционирую себя изучающим язык программирования Си
...
Рейтинг: 0 / 0
25 сообщений из 207, страница 7 из 9
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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