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

Question

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

Проблема обычная. Язык Ruby, но он поддерживается на любом языке:

f = 1829.82
=> 1829.82

f / 12.0
=> 152.485

(f / 12.0).round(2)
=> 152.48

Почему не 152,49? Потому что из-за конечной точности с плавающей точкой:

format("%18.14f", f)
=> "1829.81999999999994"

format("%18.14f", f / 12.0)
=> "152.48499999999999"

Итак, округление правильное. Теперь мой вопрос: есть ли способ получить ответ, который я хочу, в любом случае, учитывая следующие обстоятельства: существуют строгие ограничения на (число) операций, выполняемых с использованием float, необходимая точность ограничена двумя десятичными разрядами (максимум 8 цифр) в целом) и небольшое количество оставшихся «неправильных» округленных ответов приемлемо?

Ситуация такова, что пользователи могут вводить допустимые строки Ruby, такие как:

"foo / 12.0"

где foo - это число, указанное в контексте, в котором выполняется строка, но где '12 .0 '- это то, что вводит пользователь. Представьте себе электронную таблицу с некоторыми свободными полями формул. Строки просто оцениваются как Ruby, поэтому 12.0 становится Float. Я мог бы использовать гемы ruby_parser + ruby2ruby для построения дерева разбора, переноса типа данных в Bignum, Rational, что-то из библиотеки Flt, десятичных представлений с плавающей запятой или что-то-у-вас, но это сложно, так как фактические строки могут стать несколько сложнее, поэтому я предпочитаю не идти по этому пути. Я пойду по этому пути, если больше ничего не возможно, но этот вопрос специально здесь, чтобы посмотреть, смогу ли я избежать этого пути. Таким образом, тип данных 12.0 - строго Float, а результат - строго Float, и единственное, что я могу сделать, это интерпретировать окончательный ответ фрагмента и попытаться «исправить» его, если он округляет «неправильный» путь.

Единственные вычисления, которые пользователи выполняют, включают числа с точностью до двух десятичных цифр (и всего не более 8 цифр). Под «простым» я подразумеваю, что ошибки с плавающей запятой не получают шансов накапливаться: я могу добавить два из этих чисел и разделить одно на целое, но затем вычисление будет выполнено, результат округлен и сохранен, и любой последующий расчет основан на этом округленном числе. Обычно будет иметь место только одна ошибка с плавающей запятой, но я думаю, что проблема существенно не изменится, если две могут накапливаться, хотя коэффициент остаточных ошибок может быть больше по определению.

Что может сначала прийти на ум, это сначала округлить до 3 десятичных цифр, а затем до 2. Однако это не работает. Это привело бы к

152.48499999999999 => 152.485 => 152.49

но также

152.4846 => 152.485 => 152.49

это не то, что вы хотите.

Что мне пришло в голову, это добавление наименьшего возможного приращения (которое, как указывали люди, зависит от рассматриваемого значения с плавающей запятой) к плавающему значению , если , которое смещает его на 0,5 границы. Мне в основном интересно, как часто это может приводить к «ложному положительному результату»: числу, к которому добавляется наименьшее приращение, даже если тот факт, что он был чуть ниже границы .5, был вызван не ошибкой с плавающей запятой, а потому что это был просто результат расчета?

Второй вариант: просто всегда добавьте наименьшее приращение к числам, поскольку регион .5 является единственным, где он в любом случае имеет значение.

Edit: Я просто переписал вопрос, чтобы включить часть моих ответов в комментарии, как предложил cdiggins. Я наградил Иру Бакстера за его активное участие в обсуждении, хотя я еще не уверен, что он прав: Марк Рэнсом и Эмилио М. Бумачар, кажется, поддерживают мою идею о том, что исправление возможно, что на практике, возможно, в относительно большом большинстве случаев дают «правильный» результат.

Мне все еще нужно провести эксперимент, чтобы увидеть, как часто результат будет правильным, и я полностью намерен это сделать, но время, которое я могу потратить на это, несколько ограничено, поэтому я еще не дошел до этого. Эксперимент не тривиален.

Answer 1

Звучит так, будто вы хотите десятичные числа с фиксированной точностью. Хорошая библиотека, реализующая их, будет более надежной, чем хакерская сборка.

Для Ruby посмотрите библиотеку Flt .

Answer 2

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

Нет.Ошибки с плавающей запятой - единственные ошибки вашего компьютера, связанные с обработкой чисел.Если вы удалите все ошибки, по определению ваша точность будет бесконечной.

Это звучало педантично, что не было моим намерением.Я пытаюсь указать на то, что под вашей явно технической проблемой стоит большая концептуальная проблема. Нельзя правильно округлять неправильные числа, основываясь на их правильных значениях, если вы не знаете их правильные значения (т. Е. Значения с бесконечной точностью или другая форма переноса этой информации).

Ваша идея добавить небольшое число может сработать статистически, но только статистически.Я предлагаю вам написать скрипт для проверки огромного числа случаев со случайными числами не более двух десятичных знаков.(Сценарий также должен выполнять математику с бесконечной точностью, чтобы знать правильный ответ для сравнения). Таким образом, вы можете измерять исправления и ложные срабатывания.

Answer 3

Наименьшее упоминание, которое вы упоминаете, обычно называется эпсилон. Это наименьшее значение, которое можно добавить к 1,0, чтобы внести заметные изменения. Если вы хотите добавить его к другим номерам, вы должны сначала масштабировать его: x = x + (x * epsilon).

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

Теоретически добавление значения epsilon перед округлением приведет к тому, что ошибок будет столько, сколько они исправят. На практике это не так, поскольку числа, близкие к четному десятичному числу, встречаются с гораздо большей вероятностью, чем можно предположить. Случайный случай.

Answer 4

Если вы можете контролировать количество арифметических операций (особенно умножения и деления), вы можете попробовать просто масштабировать все значения с плавающей запятой до некоторой степени шкала из десяти (скажем, шкала = 4). Вам придется изменить код ввода, вывода и умножения и деления.

Тогда масштаб = 2 десятичных дроби, таких как 5.10, сохраняются точно как 510. Входные данные должны быть введены точно; например, прочитайте строку mmm.nnnn, переместите десятичную запятую scale позиции в строке (например, для scale = 2 ==> mmmnn.nn, а затем преобразуйте строку в число с плавающей точкой). Сложение / вычитание таких дробных чисел является точным и не требует каких-либо изменений кода. Умножение и деление теряют некоторую «десятичную» точность и должны масштабироваться; код, который говорит, что x * y должен быть изменен на x * y / scale; x / y нужно изменить на x * scale / y. Вы можете округлить строку в точке шкалы и затем вывести ее.

Этот ответ является глупой версией использования реального десятичного арифметического пакета, упомянутого другим постером.

Answer 5

Я заметил, что в комментарии к одному из ответов утверждалось, что изменение типа данных было трудным. Тем не менее, я собираюсь ответить на вопрос в виде вопроса:

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

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

Answer 6

В общем случае я бы сказал, что невозможно получить правильный ответ все время. Как вы обнаружили, округление в два раза не является ответом. Вместо этого старайтесь сохранять максимальную точность как можно дольше.

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

Я бы сказал, что добавление «маленького» значения или «эпсилона», как его обычно называют, является возможным способом. Просто имейте в виду, что если исходное значение отрицательное , вам придется вычесть его , а не добавлять его. Также обратите внимание, что если вы имеете дело со всем диапазоном значений с плавающей точкой, epsilon может зависеть от значения.

Answer 7

это, к сожалению, не ваш ответ, но может помочь вам начать.

Объект:

class Object
  # Return only the methods not present on basic objects
  def local_methods
    (self.methods - Object.new.methods).sort
  end
end

Модуль обратных вызовов:

module Hooker
  module ClassMethods
  private
    def following(*syms, &block)
      syms.each do |sym| # For each symbol
        str_id = "__#{sym}__hooked__"
        unless private_instance_methods.include?(str_id)
          alias_method str_id, sym    # Backup original method
          private str_id         # Make backup private
          define_method sym do |*args|  # Replace method
            ret = __send__ str_id, *args # Invoke backup
            rval=block.call(self,       # Invoke hook
             :method => sym, 
             :args => args,
             :return => ret
            )
            if not rval.nil?
              ret=rval[:ret]
            end
            ret # Forward return value of method
          end
        end
      end
    end
  end

  def Hooker.included(base)
    base.extend(ClassMethods)
  end
end

И изменения в Float для фактического выполнения работы:

if 0.1**2 != 0.01 # patch Float so it works by default
  class Float
    include Hooker
    0.1.local_methods.each do |op|
      if op != :round
        following op do |receiver, args|
          if args[:return].is_a? Float
            ret=args[:return].round Float::DIG
            ret=Hash[:ret => ret]
          end
          ret
        end
      end
    end
  end
end

Редактировать: несколько лучше использовать Rational. Переопределение nmethods по-прежнему не всегда включено (см. Проблемы после кода):

  class Float
    include Hooker
    0.1.local_methods.each do |op|
      if op != :round
        following op do |receiver, args|
          if args[:return].is_a? Float
            argsin=[]
            args[:args].each do |c|
              argsin=c.rationalize
            end
            rval=receiver.rationalize.send(
                args[:method], 
                argsin
               )
            ret=Hash[:ret => rval.to_f]
          end
          ret
        end
      end
    end
  end

Проблемы : не все переопределения методов работают, по крайней мере, в 1.9.3p0:

pry(main)> 6543.21 % 137.24
=> 92.93
[... but ...]
pry(main)> 19.5.send(:-.to_sym, 16.8)
=> 2.7
pry(main)> 19.5 - 16.8
=> 2.6999999999999993

Answer 8

Нет, вы не можете предотвратить накопление ошибок с плавающей запятой, потому что машинная арифметика всегда округляет результаты работы, чтобы соответствовать заданному числу битов. Кроме того, примите во внимание, что результаты многих операций требуют, чтобы бесконечное число битов было представлено точно (например, 2/10 = 0,2; но для точного представления в * требуется 1001 * бесконечное число битов). база 2, с которой работают компьютеры).