powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Длинная арифметика. Вопросы по реализации/оптимизации
25 сообщений из 207, страница 8 из 9
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822104
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Всё получилось :)
проблема была немного в другом, впрочем, как мне кажется, с утечками проблема решена также. Всем спасибо.
Сегодня всё расскажу и покажу
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822110
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сейчас занимаюсь декомпозицией задачи, чтобы выложить её в нормальном виде. Не знаю как правильно это доделать, подскажите пожалуйста

Вот такой файл la.h

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "la.c"

#define MIN_POW (1+1)
#define SHIFT '0'

char* allocate_memory(size_t len);

int freeMemory(char* s1, char* s2, int isFreeMemory);



вот такой la.c

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
#include <stdlib.h>
//выделение 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);
		s1 = NULL;
	}
	if (isFreeMemory >= 2)
	{
		free(s2);
		s2 = NULL;
	}
	return 0;
}



тут уже косяк. Дважды подключаю stdlib.h но программа пока запускается.
Однако, когда я делаю так, sum.h
Код: plaintext
1.
2.
3.
#include "la.h"
int la_sum_inplace(char* sum, size_t p, char* s1, size_t p1, char* s2, size_t p2);
char* la_sum(char* s1, char* s2, int isFreeMemory);



и так sum.c

Код: 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.
#include "sum.h"

//СУММА
//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;
}



тут происходит вот что "Error 3 error LNK2005: _freeMemory already defined in main.obj ", в чём проблема понятно, а как исправить пока не дошло
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822116
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

SashaMercuryтут уже косяк. Дважды подключаю stdlib.h но программа пока запускается.


Саш, тебе нужно немного почитать о подключении заголовков в C, C++
в *.h файле ты цепляешь заголовки, а не код

Вот такой файл la.h
Код: plaintext
1.
2.
3.
4.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
...


вот такой la.c
Код: plaintext
1.
2.
#include "la.h"
...
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822118
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

спасибо! Не знаю почему так сделал(вроде бы сделал сначала правильно, но почему-то сборка прошла неудачно) ( Исправил и всё сразу заработало
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822120
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

c++ - Include в заголовочных файлах
ещё, что бы заголовочные файлы не включались по нескольку раз вставляют директивы препроцессора
Код: plaintext
1.
2.
3.
4.
#ifndef Point_h__
#define Point_h__
...  // это включится всего 1 раз
#endif



SashaMercury , Вот кстати тебе задачка , на неё многие ответить не могут (первый курс универа надо)
интересно, сможешь осилить или нет, ответ там простой

Графический примитив - линейно залитый цветом треугольник
Дано: 3 точки на плоскости, их цвет c1,c2,c3 , треугольник образуемый ими нужно равномерно залить цветом
Найти: формулу c(x,y) - ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822122
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),
не знаю как бы решал первый курс, а я бы решил данную задачу используя билинейную интерполяцию. Тут частный случай, потому скорее всего как-то можно использовать формулу .
PS
кстати, можно, вероятно, составить систему уравнений, и через нее выразить x y.

Подождите :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822128
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Буду использовать следующую нотацию .

Функция имеет вид , где, и коэффициенты рассчитываются по следующим формулам
,

,
,
,
.

Я бы решал так :)
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822129
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
в t3 опечатка, понятно что там минус
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822138
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

не совсем понял как у вас с зависит от x,y

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

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

оператор L зависит от (x,y). Навскидку, "серьёзные дядьки" решают аналогично способу предложенному выше :)

А вот в главный файл, что нужно включать ? все хидеры, или только la.h ?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822145
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryА вот в главный файл, что нужно включать ? все хидеры, или только la.h ?
если они у тебя описаны в la.h, то они включатся
ориентируйся на простое правило
1. если заголовки тебе нужны для описания типов параметров то включаешь в *.h
2. если используется только в реализации, то в *.cpp, *.c
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822146
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Например, у меня 5 пар хидер name.h -файл name.c
в каждом name.h подключаю la.h, а в каждом name.c подключаю name.h .
В main.c подключаю la.h

Вроде бы правильно всё(хотя мне так не кажется), но снова аналогичная ошибка
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822151
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)что бы заголовочные файлы не включались по нескольку раз вставляют директивы препроцессора
Код: plaintext
1.
2.
3.
4.
#ifndef Point_h__
#define Point_h__
...  // это включится всего 1 раз
#endif


можно проще: первой строчкой в .h написать
Код: plaintext
1.
#pragma once
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822157
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, надо так
la.h
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN_POW (1+1)
#define SHIFT '0'
char* allocate_memory(size_t len);
int freeMemory(char* s1, char* s2, int isFreeMemory);


la.c
Код: plaintext
1.
2.
#include "la.h"
...



sum.h
Код: plaintext
1.
2.
3.
#include "la.h"
int la_sum_inplace(char* sum, size_t p, char* s1, size_t p1, char* s2, size_t p2);
char* la_sum(char* s1, char* s2, int isFreeMemory);


sum.c
Код: plaintext
1.
2.
#include "sum.h"
...



main.c
Код: plaintext
1.
2.
#include "sum.h"
...
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822180
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так и делаю :(
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822216
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)Графический примитив - линейно залитый цветом треугольник
Дано: 3 точки на плоскости, их цвет c1,c2,c3 , треугольник образуемый ими нужно равномерно залить цветом
Найти: формулу c(x,y) - ?
В графическом и геометрическом моделировании ГиГМ никто такую формулу не ищет.
Треугольник (в общем случае не коллинеарный оси OX в системе координат)
режут на 2 под-треугольника. По средней точке по вертикали OY. Для полученных треугольников
ищут уравнения боковых отрезков и делают итератор по алгоритму Брезенхема
или используют линейную зависимость в fix-point арифметике на целых числах.
Находят 2 точки и заполняют отрезок наиболее быстрым образом (не setPixel)
чаще всего черед прямой доступ к памяти графического контекста.

Для старинных API использовался доступ к видеопамяти через различные
хитрые ухищрения.

Для DirectX/OpenGL треугольник fillitся встроенными функциями, которые
работают очень быстро и рисуют миллион треугольников в секунду.

Та общая формула которая находит принадлежность точки треугольнику - нужна в других
задачах но не в fill polyline.

Кстати предлагаю подумать над порядком точек. Возможен вариант когда треугольник
"вывернут наизнанку" и мы определям обратную формулу.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822225
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryТак и делаю :(
Как так? давай подробнее и с сообщением об ошибке.

Это убрал из la.h ?
Код: plaintext
1.
#include "la.c"
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822338
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВ графическом и геометрическом моделировании ГиГМ никто такую формулу не ищет.
Треугольник (в общем случае не коллинеарный оси OX в системе координат)
режут на 2 под-треугольника. По средней точке по вертикали OY. Для полученных треугольников
ищут уравнения боковых отрезков и делают итератор по алгоритму Брезенхема
или используют линейную зависимость в fix-point арифметике на целых числах.
Находят 2 точки и заполняют отрезок наиболее быстрым образом (не setPixel)
чаще всего черед прямой доступ к памяти графического контекста.

вопрос не в том как находятся координаты периметра треугольника, а по какой формуле находится цвет внутри него для точки с координатами (x,y) (т.е. уже известно что она лежит внутри треугольника)
цвета точек c1,c2,c3 и их координаты соответственно (x1,y1),(x2,y2),(x3,y3)
mayton
Для DirectX/OpenGL треугольник fillitся встроенными функциями, которые
работают очень быстро и рисуют миллион треугольников в секунду.

Та общая формула которая находит принадлежность точки треугольнику - нужна в других
задачах но не в fill polyline.

то, что кто-то реализовал эти методы за/до вас, не значит что формулы не используются
кстати, для перспективной проекции формула будет другая
maytonКстати предлагаю подумать над порядком точек. Возможен вариант когда треугольник
"вывернут наизнанку" и мы определям обратную формулу.

порядок точек не важен
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822344
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TSashaMercuryТак и делаю :(
Как так? давай подробнее и с сообщением об ошибке.

Это убрал из la.h ?
Код: plaintext
1.
#include "la.c"


SashaMercury, покажи лучше начала всех файлов которые у тебя есть в проекте
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822414
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)вопрос не в том как находятся координаты периметра треугольника, а по какой формуле находится цвет внутри него для точки с координатами (x,y) (т.е. уже известно что она лежит внутри треугольника)
цвета точек c1,c2,c3 и их координаты соответственно (x1,y1),(x2,y2),(x3,y3)

ОК. Как будет угодно. Я-бы предложил вынести это в пятничные задачи.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822453
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonkealon(Ruslan)вопрос не в том как находятся координаты периметра треугольника, а по какой формуле находится цвет внутри него для точки с координатами (x,y) (т.е. уже известно что она лежит внутри треугольника)
цвета точек c1,c2,c3 и их координаты соответственно (x1,y1),(x2,y2),(x3,y3)

ОК. Как будет угодно. Я-бы предложил вынести это в пятничные задачи.
да ладно, уравнение плоскости через три точки даже на кофе-брейк не тянет
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822556
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)maytonпропущено...

ОК. Как будет угодно. Я-бы предложил вынести это в пятничные задачи.
да ладно, уравнение плоскости через три точки даже на кофе-брейк не тянет
Тогда давай вернёмся к длинной арифметке. Топик ибо.
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822609
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonТогда давай вернёмся к длинной арифметке. Топик ибо.
а что там возвращаться, у автора проблемы больше с С++
по сути :
1. если в продакшене, то - GMP, как ему уже советовали
2. если самому разобраться
сложить,вычесть - столбиком наверное пойдёт

алгоритмы умножения: Метод умножения Шёнхаге — Штрассена , умножение Карацубы , Алгоритм Фюрера

деление, остаток от деления - столбиком хватит наверное через вычитание для начала

операция k^n mod m - Алгоритм Монтгомери

но скорее всего он пока не осилит этого ...

SashaMercury, ты в каком классе учишься?
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822632
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)SashaMercury, ты в каком классе учишься?
если, вы читали Лабиринт отражений/Фальшивые зеркала, то вы наверное знаете, что не всегда на такие вопросы можно получить ответы.

Всё что вы привели выше, уверен? реализовать смогу. Но я чувствую разницу между прочитать алгоритм и реализовать его(тут и дворник справится), и между самому решить эту задачу(пусть даже для этой задачи уже есть решение). Когда я задаю вопросы, то задаю их не ради получения личной выгоды в виде решения лабораторных, устранения косяков на работе, smth else. Мне это нравится, в первую очередь, нравится думать, писать программы на Си, и видеть результат.

Что касается треугольника, то решения уже приведено выше, и оно правильное. Не понимаю почему на хабре ради такой ерунды создавали топик. Решение единственное, и не имеет вариаций. В том смысле, что это равносильно созданию топика о том, как найти определитель матрицы 3x3
...
Рейтинг: 0 / 0
Длинная арифметика. Вопросы по реализации/оптимизации
    #38822634
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)maytonТогда давай вернёмся к длинной арифметке. Топик ибо.
а что там возвращаться, у автора проблемы больше с С++

Да нет у него проблем. Просто изучает. В плане оптимизации сложения
у меня есть свои мысли. В техникуме на курсе ЦУМПС (цифровые устр.
и мк.системы) мы изучали оптимизацию сложения через аппаратные
кодеры-декодеры или шифраторы-дешифраторы (не помню точно).
Суть - в двоичной системе счисления биты группируются на группы
по 4 штуки (тетрада). И для каждой тетрады строится булевая функция.
8+1 входов и 4+1 выхода. Оптимизируется и хардкодится. 5-й выход - это бит
переноса. Можно и группировать (наверное) и по 5 битов и более но
это вызовет скорее всего резкое усложнение сумматора.

Далее полученные аппаратные сумматоры тетрад объединяются в каскады.

Полученное устройство и будет максимально оптимизировано. Далее - сколько
не разгоняй - всё равно каскады работают последовательно. Но быстрее чем
по 1 биту складывать.

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


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