Точные вычисления с проективными координатами

[george66]

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

[Xaositect]

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

[wrest]

george66 в сообщении #1347564 писал(а):

1) хранить четвёрку целых чисел, сократив на общий делитель всех четырёх;

Четверки, наверное, будет мало. Приводите к [наименьшему] общему знаменателю и храните его, плюс четыре числителя. Итого пять чисел.

george66 в сообщении #1347564 писал(а):

2) хранить три рациональных числа, поделив три числа четвёрки на четвёртое, тогда сократить можно сильнее, но чисел больше.

Ну да, тут получается шесть чисел: три числителя и три знаменателя.

[Munin]

В $\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.$

[wrest]

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

[Munin]

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$

и однозначный вывод исчезает. Остаётся зависимость от конкретных вычислений.

[george66]

Xaositect в сообщении #1347608 писал(а):

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

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

[Xaositect]

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

[Pavia]

george66 в сообщении #1347657 писал(а):

Это нужно для рисовальной программы

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

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

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

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

[george66]

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

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

[Pavia]

george66
А почему вначале не сделать второе, а потом первое?

george66 в сообщении #1347741 писал(а):

Есть ли разница?

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

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

george66 в сообщении #1347741 писал(а):

По округлённым координатам это сделать нельзя.

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

[arseniiv]

(Оффтоп)

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