Дан список вещественных чисел типа double. Необходимо найти общую часть у данных вещественных чисел. Как это сделать побыстрее? Можно ли как-то через битовые операции?
Пример 1.
число 0 = 15.0123567
число 1 = 15.0123593
общая часть = 15.01235, так как отличия идут с 6 знака после запятой
Пример 2.
число 0 = 0.000123
число 1 = 102.00123
общая часть = 0.0, так как отличия идут сразу
Пример 3.
число 0 = 1.234578e-10
число 1 = 1.234567e-10
общая часть = 1.2345e-10, так как отличия после цифры 5
Если кому интересно откуда возникла данная задачка. Нужно было найти площадь полигона на плоскости, который задан множеством точек (x_i, y_i) i = 0...N. Использовал формулу площади Гаусса. Начал гонять тесты и получил интересную картину, когда координаты точек были очень сильно близки к друг другу. Например 1.1234567891***** (то есть отличаются где стоят *), то площадь получалась отрицательной... хотя на самом деле площадь была положительной если использовать числа с большей точностью. Отсюда возникла идея того, как исправить данную проблему, так это сместить координаты точек так чтобы из 1.1234567891***** стало бы *.****00000000000e-11. Я знаю и другое решение, но я вообще не понимаю как оно работает, дело в том, что если умножить все координаты скажем на 1e6, потом найти площадь по формуле Гаусса, затем разделить площадь на 1e12, то получим положительную площадь.
если же имелось в виду .00, то я бы нашел длину минимальную разрядность до и после точки, дальше в цикле по разрядности циклы, в них получаем значение текущего разряда и если цифры совпали, то ставим флаг и если дальше тоже совпало, то добавляем. ну, короче, как-то так.
если же имелось в виду .00, то я бы нашел длину минимальную разрядность до и после точки, дальше в цикле по разрядности циклы, в них получаем значение текущего разряда и если цифры совпали, то ставим флаг и если дальше тоже совпало, то добавляем. ну, короче, как-то так.
Вадим Мамонов, не так понял.
тогда да, надо либо в стоку переводить. либо делать цикл по цифрам.
только с экспоненциальной записью не очевидно, конечно
Леонид Николаев, Я еще слышал, что можно умножать координаты точек на большое число. Так я взял свой набор точек умножил их на 1e6, затем использовал алгоритм для поиска площади, после разделил площадь на 1e12 (там используются векторные произведения, поэтому так), в итоге получил положительную площадь. Но я не понимаю как умножение помогает. На счет смещения понятно, что поможет, а вот умножение.
Через битовые операции вы ничего не сделаете, потому что у вас, судя по всему, надо найти общие цифры в десятичной системе счисления. Вообще найти десятичные цифры у вещественных чисел - весьма сложная операция.
Я думаю, вам остается только вывести оба числа в строки в каком-нибудь фиксированном формате и дальше сравнивать посимвольно.
Понятно. Жалко конечно, мне нужно этот алгоритм нужно постоянно использовать, если алгоритм будет медленно работать, то вся программа в целом будет медленно работать.
Вадим Мамонов, Ну, во-первых, вам же не важно, совпадают ли первые числа в десятичной или двоичной записи. Вам важно, что числа очень близки. Тут можно просто проверять, что относительная разность (|a-b|/b) достаточно мала. Ну, на крайний случай, можно творить битовую магию с мантиссой и экспонентой. Тогда вы получите количество одинаковых двоичных цифр.
Во-вторых, сама ваша идея не правильная. Может получиться отрицательная площадь, если точки заданы не против часовой стрелки, а по. Тогда можно просто взять модуль площади в самом конце. От того, что точки очень близкие у вас отрицательных числ возникать не должно. Кроме того, в процессе вычисления площади по формуле Гаусса часть слагаемых может быть отрицательными - это нормально.
Вадим Мамонов, Я думаю вы не все рассказали. Вы там точки как-то сортируете перед формулой гаусса? Может, выпуклую оболочку строите? Тогда умножение на 10^6 может помочь в точности сортировки (из-за плохого алгоритма сортировки). Поэтому знак ответа и меняется. Опять же, проблема не в формуле Гаусса и вообще искать близкие точки тут не надо.
Wataru, На счет магии ничего сказать не могу)) не волшебник.
А на счет второго. Модуль брать точно нельзя, так как мне нужно отлавливать те моменты когда контур перевернулся, ну и все моменты когда площадь стала отрицательной. На счет отрицательных слагаемых в курсе. Я думал делать смещение относительно любой точки полигона, да думаю так и надо делать, тогда у общая часть уйдет.
