Генерировать некорректные данные для проверки суммирования с плавающей запятой

Question

Я реализовал алгоритм суммирования с плавающей запятой Кахана в Java. Я хочу сравнить его со встроенным дополнением с плавающей точкой в ​​Java и дополнением с бесконечной точностью в Mathematica. Однако набор данных, который я имею, не подходит для тестирования, потому что числа близки друг к другу. (Номер условия ~= 1)

Запуск Kahan на моем наборе данных дает почти тот же результат, что и встроенный +,

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

Answer 1

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

Похоже, вы уже знаете, в чем проблема. Доберитесь до этого =)

Есть несколько вещей, которые вы захотите:

• Числа сильно различаются по величине, так что большая часть точности меньшего числа теряется при наивном суммировании.
• Числа с разными знаками и почти равными (или равными) величинами, так что происходит катастрофическая отмена.
• Числа, для которых установлены некоторые младшие биты, чтобы увеличить эффекты округления.

Для начала вы можете попробовать несколько простых трехчленных сумм, которые должны четко показать эффект:

1.0 + 1.0e-20 - 1.0

Оценивается простым суммированием, это даст 0.0; явно неверно. Вы также можете посмотреть на суммы в форме:

a0 + a1 + a2 + ... + an - b

куда b это сумма a0 + ... + an оценили наивно.

Answer 2

Вы хотите кучу высокоточных чисел? Попробуй это:

double[] nums = new double[SIZE];
for (int i = 0; i < SIZE; i++)
    nums[i] = Math.rand();

Answer 3

Мы говорим о числовых парах или последовательностях?

Если пары начинаются с 1 для обоих чисел, то в каждой итерации делите одну на 3, умножайте другую на 3. Теоретические суммы этих пар легко вычислить, и вы получите целый ряд ошибок округления. (Некоторые из деления, а некоторые из дополнения. Если вы не хотите ошибок деления, используйте 2 вместо 3.)

Answer 4

Экспериментально я обнаружил следующую закономерность:

public static void main(String[] args) {
    System.out.println(1.0 / 3 - 0.01 / 3);

    System.out.println(1.0 / 7 - 0.01 / 7);

    System.out.println(1.0 / 9 - 0.001 / 9);
}

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

    System.out.println(1.0 / 9 - 0.01 / 9);

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

    System.out.println((1.0 / 9 - 0.001 / 9) * 9000);
    if (1000 - (1.0 / 9 - 0.001 / 9) * 9000 > 1.0)
        System.out.println("Found it!");

Answer 5

Скалачек может быть чем-то для вас. Вот краткий пример:

cat DoubleSpecification.scala
import org.scalacheck._

object DoubleSpecification extends Properties ("Doubles") {
        /* 
            (a/1000 + b/1000) = (a+b) / 1000
            (a/x    + b/x   ) = (a+b) / x
        */
        property ("distributive") = Prop.forAll { (a: Int, b: Int, c: Int) => 
            (c == 0 || a*1.0/c + b*1.0/c == (a+b) * 1.0 / c)            }
}       

object Runner { 
    def main (args: Array[String]) {
        DoubleSpecification.check
        println ("...done")
    }
}

Чтобы запустить его, вам понадобится скала и банка-шалачек. Я использовал версию 2.8 (я не должен сказать, что ваш c-путь будет меняться):

 scalac -cp /opt/scala/lib/scalacheck.jar:. DoubleSpecification.scala 
 scala -cp /opt/scala/lib/scalacheck.jar:. DoubleSpecification
! Doubles.distributive: Falsified after 6 passed tests.                       
> ARG_0: 28 (orig arg: 1030341)
> ARG_1: 9 (orig arg: 2147483647)
> ARG_2: 5

Scalacheck принимает некоторые случайные значения (аргументы orig) и пытается упростить их, если тест не пройден, чтобы найти простые примеры.