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

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

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

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

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

Изменить: я просто переписал вопрос, чтобы включить часть моих ответов в комментарии, как предложил 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=2 ==> mmmnn.nn, а затем преобразуйте строку в число с плавающей точкой). Сложение / вычитание таких дробных чисел является точным и не требует каких-либо изменений кода. Умножение и деление теряют некоторую "десятичную" точность и должны масштабироваться; код, который говорит, что x*y должен быть изменен на x*y/scale; x/y нужно изменить на x*scale/y. Вы можете округлить строку в точке шкалы и затем вывести ее.

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

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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

Answer 8

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

Объект:

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