2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Точные вычисления с проективными координатами
Сообщение19.10.2018, 09:05 
Заслуженный участник


31/12/15
922
А вот посоветуйте: мне нужно работать с четвёрками рациональных чисел с точностью до общего множителя (проективные координаты). Задавать их нужно точно. С ними делать вычисления, при которых числители и знаменатели могут расти. Следует ли их сокращать на наибольший общий делитель? Мне приходят на ум две возможности:
1) хранить четвёрку целых чисел, сократив на общий делитель всех четырёх;
2) хранить три рациональных числа, поделив три числа четвёрки на четвёртое, тогда сократить можно сильнее, но чисел больше.
Наверняка кто-то это уже делал.

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 11:18 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Зависит от алгоритма и данных - в общем случае общих делителей не будет и вряд ли что-то получится сжать, лучше будет хранить четыре рациональных числа.
Есть много работ по вычислительной линейной алгебре над рациональными числами, там много разных ухищрений.
Дайте больше конкретики, что у Вас за задача?

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 11:55 


05/09/16
11461
george66 в сообщении #1347564 писал(а):
1) хранить четвёрку целых чисел, сократив на общий делитель всех четырёх;

Четверки, наверное, будет мало. Приводите к [наименьшему] общему знаменателю и храните его, плюс четыре числителя. Итого пять чисел.
george66 в сообщении #1347564 писал(а):
2) хранить три рациональных числа, поделив три числа четвёрки на четвёртое, тогда сократить можно сильнее, но чисел больше.
Ну да, тут получается шесть чисел: три числителя и три знаменателя.

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 12:10 
Заслуженный участник
Аватара пользователя


30/01/06
72407
В $\mathbb{RP}^1$ мы можем первым способом хранить числа $(a,b),$ такие что $\gcd(a,b)=1$ (обозначим это $a\perp b$ - [Грэхем, Кнут, Паташник]). Тогда вторым способом мы должны хранить рациональное число $a/b$ (в виде числителя и знаменателя) - выигрыша нет.

В $\mathbb{RP}^2$ мы можем первым способом хранить три таких числа, что их общий $\gcd=1.$ На попарные $\gcd$ не наложено никаких условий, кроме этого, и мы их можем обозначить $a,b,c,$ тогда наши три числа будут $(ab,ac,bc),$ причём $a\perp b\perp c\perp a.$ Вторым способом мы будем хранить две дроби $(a/c,a/b).$
Затраты памяти в первом случае:
    $(\log a+\log b)+(\log a+\log c)+(\log b+\log c)=2\log a+2\log b+2\log c,$
во втором случае
    $(\log a+\log с)+(\log a+\log b)=2\log a+\log b+\log c.$
Кроме общих затрат памяти (в случае чисел произвольного размера) видно, что второй способ безопаснее от переполнения, если используются числа фиксированного размера (типа int32, int64 и т. д.)

В случае $\mathbb{RP}^3$ я не разобрался до конца в решётке, но предполагаю, что можно ввести тройственные $\gcd,$ попарно между собой простые: $a\perp b\perp c\perp d\perp a, b\perp d, a\perp c$ и тогда четыре числа будут $(abc,abd,acd,bcd),$ а хранение вторым способом - шесть чисел $(a/d,a/c,a/b).$
$(\log a+\log b+\log c)+(\log a+\log b+\log d)+(\log a+\log c+\log d)+(\log b+\log c+\log d)=3\log a+3\log b+3\log c+3\log d,$
во втором случае
    $(\log a+\log d)+(\log a+\log c)+(\log a+\log b)=3\log a+\log b+\log c+\log d.$
То есть, та же картина, что и для $\mathbb{RP}^2.$

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 12:17 


05/09/16
11461
А, ну конечно. Делим три числа на четвертое. Затем приводим частные к одному знаменателю и храним четыре числа: три числителя и общий знаменатель.

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 12:25 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Munin в сообщении #1347633 писал(а):
В $\mathbb{RP}^2$ мы можем первым способом хранить три таких числа, что их общий $\gcd=1.$ На попарные $\gcd$ не наложено никаких условий, кроме этого, и мы их можем обозначить $a,b,c,$ тогда наши три числа будут $(ab,ac,bc),$ причём $a\perp b\perp c\perp a.$

Неправильно. Наши три числа могут быть $(abp,acq,bcr),$ если $bp\perp cq,ap\perp cr,aq\perp br.$ (То есть, $p\perp c,q\perp b,r\perp a,p\perp q\perp r\perp p.$)
Тогда дроби $(ap/cr,aq/br),$ и в затраты памяти добавляется
    $\ldots+\log p+\log q+\log r$
    $\ldots+\log p+\log q+2\log r$
и однозначный вывод исчезает. Остаётся зависимость от конкретных вычислений.

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 13:27 
Заслуженный участник


31/12/15
922
Xaositect в сообщении #1347608 писал(а):
Зависит от алгоритма и данных - в общем случае общих делителей не будет и вряд ли что-то получится сжать, лучше будет хранить четыре рациональных числа.
Есть много работ по вычислительной линейной алгебре над рациональными числами, там много разных ухищрений.
Дайте больше конкретики, что у Вас за задача?

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

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 13:45 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Если так, то для начала я бы не парился, использовал четверки/шестерки рациональных чисел и после каждой операции (или серии операций) находил бы НОД всех числителей и НОД всех знаменателей и убирал их.

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 14:54 
Аватара пользователя


31/10/08
1244
george66 в сообщении #1347657 писал(а):
Это нужно для рисовальной программы

А зачем тогда точные? В CG алгоритмы строятся из сходя из необходимой сабпиксельной точности. Просто если брать монитор 4К, а точность нужна сабпиксельная 1/8. Помножить на количество трансформаций, которые по своей природе иерархические*. Поэтому их как бы не более 8.
$\log_2(4096*8*8)=18$ разрядов. Откуда типа single вам хватит за глаза.

Если мы проверяем пересечение, то оно должно быть не более $1/8$ Px или в мировых координатах $\Delta=M*1/(4096*8)$. M- масштабный коэффициент.

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

*) В играх там да там процессы не иерархические, а циклические и тут уже нужны доработки.

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 18:45 
Заслуженный участник


31/12/15
922
Программа для геометрических построений. Допустим, мы хотим построить плоскость по трём точкам. Перед этим надо проверить, не лежат ли они на одной прямой. По округлённым координатам это сделать нельзя.

А вот, допустим, у нас есть четвёрка
$(25, 25, 25, 50/25)$
Можно сократить числители
$(1, 1, 1, 2/25)$
а можно сократить четвёртое число
$(25, 25, 25, 2)$
Есть ли разница?

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 20:48 
Аватара пользователя


31/10/08
1244
george66
А почему вначале не сделать второе, а потом первое?
george66 в сообщении #1347741 писал(а):
Есть ли разница?

Вероятность нахождения общего делителя для 5-и числе ниже чем для 2-х чисел.

Но для задачи построения одной плоскости с 4 числами это бессмысленное занятие, так как нет параметра. А следовательно вероятность не влияет, вернее не определена.
Плюс к тому же будете дольше искать общий делитель, чем вычислять лежат точки на одной прямой.

george66 в сообщении #1347741 писал(а):
По округлённым координатам это сделать нельзя.

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

 Профиль  
                  
 
 Re: Точные вычисления с проективными координатами
Сообщение19.10.2018, 21:27 
Заслуженный участник


27/04/09
28128

(Оффтоп)

Pavia
Я так понимаю, у george66 исходные данные всё-таки понимаются как точные. И прекрасно могу понять, зачем такое может пригодиться — именно для точной проверки каких-нибудь математических фактов, к примеру. А КГ КГ рознь, даже если взять рисование, то одно дело рисовать 60 раз в секунду, а другое рисовать что-то очень приближенное к реальности, и универсальных советов, затрагивающих и то, и то, немного. Ну и с расчётами аналогично.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group