Если есть две точки (X1,Y1) и (X2,Y2) через которые проходит некоторая прямая, то узнать значение X для заданного Y чтобы точка оказалась на прямой можно по формуле:Сообщение от Destr
X=X1+(Y-Y1)/(Y2-Y1)*(X2-X1), то есть фактически задача сводится к вычислению D=A*B/C. Далее некоторые рассуждения на тему того, как эти операции можно выполнить вместе без увеличения разрядности, но пока у алгоритма есть существенные ограничения по диапазону корректно обрабатываемых величин.
В развёрнутом алгоритме деления используется остаток S, который сдвигается с добавлением по 1 биту из A, если S<0, то к нему добавляется С, иначе вычитается, после чего частное сдвигается и к нему добавляется 1 если S>=0.
Для алгоритма умножения можно сдвигать B и если в перенос попадает 1, то добавлять к произведению A (здесь требуется увеличение разрядности).
Если объединить добавление A и С(или вычитание) из этих двух алгоритмов, то получается 4(на счёт 2х я ошибся) параллельные ветки по 8 итераций:
S<0, B>=128, нужно добавлять A+C
S<0, B<128, нужно добавлять С
S>=0, B<128, нужно добавлять -С
S>=0, B>=128, нужно добавлять A-C
Одна итерация в каждой ветке выглядит так:
сдвигаем B и затягиваем в него перенос полученный после сложения в качестве бита частного
если требуется, делаем переход в другую ветку
удваиваем сумму(из-за этого шага алгоритм деления не может работать с числами более 2^7, а использование A+C в суммировании уменьшает их диапазон вдвое)
добавляем константу соответствующую данной ветке
делаем переход в другую ветку, если знак суммы поменялся
Не факт что это будет особенно полезно применительно к отрезкам, но может у кого-то появятся другие идеи где это можно использовать.
Ответить с цитированием
