Как «проверить» массив шумных чисел с плавающей точкой?

Question

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

например, у меня есть два алгоритма, которые должны (теоретически, с бесконечнымточность) вывести тот же массив.Но они работают по-разному, и поэтому ошибки с плавающей точкой будут накапливаться по-разному, хотя длины массивов должны быть точно такими же.Я хотел бы быстрый и простой способ проверить, не выглядят ли массивы одинаковыми.Конечно, я мог бы сравнить числа попарно и сообщить о максимальной ошибке;но один алгоритм на C ++, а другой на Mathematica, и я не хочу беспокоиться о записи чисел в файл или вставке их из одной системы в другую.Вот почему я хочу простую контрольную сумму.

Я мог бы просто сложить все числа в массиве.Если длина массива равна N, и я могу допустить ошибку 0,0001 в каждом числе, то я бы проверил, если abs(sum1-sum2)<0.0001*N.Но эта упрощенная «контрольная сумма» не является надежной, например, с ошибкой +10 в одной записи и -10 в другой.(И в любом случае, теория вероятности говорит, что ошибка, вероятно, возрастает как sqrt (N), а не как N.) Конечно, любая контрольная сумма является низкоразмерной суммой данных, поэтому она пропустит некоторые ошибки, если не большинство ... но простые контрольные суммы, тем не менее, полезны для поиска не вредоносных ошибок типа ошибок.

Или я мог бы создать двухмерную контрольную сумму, [sum(x[n]), sum(abs(x[n]))].Но самое лучшее, что я могу сделать, то есть есть ли другая функция, которую я мог бы использовать, которая была бы "более ортогональной" к sum(x[n])?И если бы я использовал некоторые произвольные функции, например, [sum(f1(x[n])), sum(f2(x[n]))], то как мой «грубый допуск к ошибкам» должен переводиться в «допуск к ошибкам контрольной суммы»?

Я программирую на C ++, но рад видетьответы на любом языке.

Answer 1

У меня такое ощущение, что то, что вы хотите, может быть возможно с помощью чего-то вроде кодов серого .если бы вы могли перевести свои значения в серые коды и использовать какую-то контрольную сумму, которая могла бы исправить n битов, вы могли бы определить, были ли эти два массива одинаковыми, за исключением n-1 битов ошибок, верно?(каждый бит ошибки означает, что число «отклоняется на единицу», где отображение было бы таким, чтобы это было изменение в младшей значащей цифре).

, но точные детали за мной - особенно для плавающегозначения точек.

Я не знаю, помогает ли это, но то, что решают серые коды, - это проблема патологического округления.округление звучит так, как будто это решит проблему - наивное решение может округлить, а затем - контрольную суммуно простое округление всегда имеет патологические случаи - например, если мы используем слово floor, то 0.9999999 и 1 различны.Подход с использованием серого кода, по-видимому, решает эту проблему, поскольку соседние значения всегда находятся на расстоянии одного бита, поэтому контрольная сумма на основе битов будет точно отражать «расстояние».

[update:] более точно, что вы хотите, это контрольная суммаэто дает оценку расстояния Хэмминга между вашими закодированными в серый цвет последовательностями (и закодированной в серый цвет частью легко, если вы просто заботитесь о 0,0001, поскольку вы можете умножить все на 10000 и использовать целые числа).

и кажется, что такие контрольные суммы существуют : Любой код, исправляющий ошибки, может использоваться для обнаружения ошибок.Код с минимальным расстоянием Хэмминга, d, может обнаруживать до d - 1 ошибок в кодовом слове.Использование кодов, исправляющих ошибки на основе минимального расстояния, для обнаружения ошибок может быть целесообразным, если требуется строгое ограничение на минимальное количество обнаруживаемых ошибок.

, поэтому на всякий случай неясно:

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

но я все еще не уверен, что это правильно.Вы все еще получаете патологическое округление при преобразовании из числа с плавающей точкой в ​​целое число.поэтому кажется, что вам нужно минимальное расстояние Хэмминга, равное 1 + len (данные) (наихудший случай, с ошибкой округления для каждого значения).это возможно?вероятно, не для больших массивов.

может быть, спросить еще раз с лучшими тегами / описанием теперь, когда возможно общее направление?или просто добавить теги сейчас?нам нужен кто-то, кто делает это для жизни.[я добавил пару тегов]

Answer 2

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

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

Однакоочень простая рандомизированная схема должна работать нормально.Сгенерируйте псевдослучайную строку S из алфавита {+ 1, -1} и вычислите csx = sum (X_i * S_i) и csy = sum (Y_i * S_i), где X и Y - мои исходные массивы чисел с плавающей запятой.Если мы моделируем ошибки как независимые нормальные случайные величины со средним значением 0, тогда легко вычислить распределение csx-csy.Мы могли бы сделать это для нескольких строк S, а затем провести проверку гипотезы о том, что средняя ошибка равна 0. Число строк S, необходимых для теста, является фиксированным, оно не растет линейно по размеру массивов, поэтому оно удовлетворяетмоя потребность в "низкоразмерном резюме".Этот метод также дает оценку стандартного отклонения ошибки, что может быть удобно.

Answer 3

Попробуйте это:

#include <complex>
#include <cmath>
#include <iostream>

// PARAMETERS
const size_t no_freqs = 3;
const double freqs[no_freqs] = {0.05, 0.16, 0.39}; // (for example)

int main() {
    std::complex<double> spectral_amplitude[no_freqs];
    for (size_t i = 0; i < no_freqs; ++i) spectral_amplitude[i] = 0.0;
    size_t n_data = 0;
    {
        std::complex<double> datum;
        while (std::cin >> datum) {
            for (size_t i = 0; i < no_freqs; ++i) {
                spectral_amplitude[i] += datum * std::exp(
                    std::complex<double>(0.0, 1.0) * freqs[i] * double(n_data)
                );
            }
            ++n_data;
        }
    }
    std::cout << "Fuzzy checksum:\n";
    for (size_t i = 0; i < no_freqs; ++i) {
        std::cout << real(spectral_amplitude[i]) << "\n";
        std::cout << imag(spectral_amplitude[i]) << "\n";
    }
    std::cout << "\n";
    return 0;
}

Возвращает только несколько произвольных точек преобразования Фурье всего набора данных.Это, так сказать, нечеткая контрольная сумма.

Answer 4

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