Эвристика, чтобы определить, являются ли серии из 4 байтов кусками данных целыми числами или числами с плавающей запятой - PullRequest
Новая
       7

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

11 голосов
/ 21 марта 2010

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

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

Например, давайте возьмем последовательность 4-байтовых необработанных данных и напечатаем их сначала как целые числа, а затем как числа с плавающей запятой: 

1           1.4013e-45
10          1.4013e-44
44          6.16571e-44
5000        7.00649e-42
1024        1.43493e-42
0           0
0           0
-5          -nan
11          1.54143e-44

Очевидно, что они будут целыми числами.

Теперь еще один пример: 

1065353216  1
1084227584  5
1085276160  5.5
1068149391  1.33333
1083179008  4.5
1120403456  100
0           0
-1110651699 -0.1
1195593728  50000

Это, очевидно, будут поплавки.

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

Ответы [ 10 ]

9 голосов
/ 21 марта 2010

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

4 голосов
/ 22 марта 2010

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

Кажется достаточно прямым для реализации.

1 голос
/ 22 марта 2010

Человек может сделать это легко

Человек вообще не может этого сделать. Ergo также не может компьютер. Есть 2 ^ 32 действительных значений int. Большое количество из них также являются действительными значениями с плавающей точкой. Нет никакого способа отличить цель данных, кроме как пометить их или не попасть в такой беспорядок.

Не пытайтесь это сделать.

1 голос
/ 21 марта 2010

Если оба числа положительные, ваши числа с плавающей запятой достаточно велики (больше 10 ^ -42), а ваши числа достаточно малы (меньше 8 * 10 ^ 6), тогда проверка довольно проста. Обрабатывайте данные как float и сравнивайте с наименьшим нормализованным значением с плавающей точкой. 

union float_or_int {
    float f;
    int32_t i;
};

bool is_positive_normalized_float( float_or_int &u ) {
    return u.f >= numeric_limits<float>::min();
}

Это предполагает IEEE float и ту же бесконечность между процессором и FPU.

1 голос
/ 21 марта 2010

Вы, вероятно, можете «обнаружить» его, взглянув на старшие биты, с плавающими они обычно бывают ненулевыми, с целыми числами они будут, если вы не имеете дело с очень большим числом.Итак ... вы можете попробовать и посмотреть, вернет ли (2^30) & number 0 или нет.

0 голосов
/ 02 марта 2013

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

Я использую его в дизассемблере, чтобы определить, было ли 32-битное значение изначально целочисленным или плавающим литералом. 

public class FloatUtil {
    private static final int canonicalFloatNaN = Float.floatToRawIntBits(Float.NaN);
    private static final int maxFloat = Float.floatToRawIntBits(Float.MAX_VALUE);
    private static final int piFloat = Float.floatToRawIntBits((float)Math.PI);
    private static final int eFloat = Float.floatToRawIntBits((float)Math.E);

    private static final DecimalFormat format = new DecimalFormat("0.####################E0");

    public static boolean isLikelyFloat(int value) {
        // Check for some common named float values
        if (value == canonicalFloatNaN ||
                value == maxFloat ||
                value == piFloat ||
                value == eFloat) {
            return true;
        }

        // Check for some named integer values
        if (value == Integer.MAX_VALUE || value == Integer.MIN_VALUE) {
            return false;
        }

        // a non-canocical NaN is more likely to be an integer
        float floatValue = Float.intBitsToFloat(value);
        if (Float.isNaN(floatValue)) {
            return false;
        }

        // Otherwise, whichever has a shorter scientific notation representation is more likely.
        // Integer wins the tie
        String asInt = format.format(value);
        String asFloat = format.format(floatValue);

        // try to strip off any small imprecision near the end of the mantissa
        int decimalPoint = asFloat.indexOf('.');
        int exponent = asFloat.indexOf("E");
        int zeros = asFloat.indexOf("000");
        if (zeros > decimalPoint && zeros < exponent) {
            asFloat = asFloat.substring(0, zeros) + asFloat.substring(exponent);
        } else {
            int nines = asFloat.indexOf("999");
            if (nines > decimalPoint && nines < exponent) {
                asFloat = asFloat.substring(0, nines) + asFloat.substring(exponent);
            }
        }

        return asFloat.length() < asInt.length();
    }
}

А вот некоторые из значений, для которых он работает (и пара это не делает) 

@Test
public void isLikelyFloatTest() {
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(1.23f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(1.0f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(Float.NaN)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(Float.NEGATIVE_INFINITY)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(Float.POSITIVE_INFINITY)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(1e-30f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(1000f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(1f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(-1f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(-5f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(1.3333f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(4.5f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(.1f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(50000f)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(Float.MAX_VALUE)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits((float)Math.PI)));
    Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits((float)Math.E)));

    // Float.MIN_VALUE is equivalent to integer value 1. this should be detected as an integer
    // Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(Float.MIN_VALUE)));

    // This one doesn't quite work. It has a series of 2 0's, but we only strip 3 0's or more
    // Assert.assertTrue(FloatUtil.isLikelyFloat(Float.floatToRawIntBits(1.33333f)));

    Assert.assertFalse(FloatUtil.isLikelyFloat(0));
    Assert.assertFalse(FloatUtil.isLikelyFloat(1));
    Assert.assertFalse(FloatUtil.isLikelyFloat(10));
    Assert.assertFalse(FloatUtil.isLikelyFloat(100));
    Assert.assertFalse(FloatUtil.isLikelyFloat(1000));
    Assert.assertFalse(FloatUtil.isLikelyFloat(1024));
    Assert.assertFalse(FloatUtil.isLikelyFloat(1234));
    Assert.assertFalse(FloatUtil.isLikelyFloat(-5));
    Assert.assertFalse(FloatUtil.isLikelyFloat(-13));
    Assert.assertFalse(FloatUtil.isLikelyFloat(-123));
    Assert.assertFalse(FloatUtil.isLikelyFloat(20000000));
    Assert.assertFalse(FloatUtil.isLikelyFloat(2000000000));
    Assert.assertFalse(FloatUtil.isLikelyFloat(-2000000000));
    Assert.assertFalse(FloatUtil.isLikelyFloat(Integer.MAX_VALUE));
    Assert.assertFalse(FloatUtil.isLikelyFloat(Integer.MIN_VALUE));
    Assert.assertFalse(FloatUtil.isLikelyFloat(Short.MIN_VALUE));
    Assert.assertFalse(FloatUtil.isLikelyFloat(Short.MAX_VALUE));
}
0 голосов
/ 02 июня 2010

Упрощая то, что сказал Алан, я бы посмотрел ТОЛЬКО на целочисленную форму.и скажем, если число больше, чем 99999999, то это почти наверняка с плавающей точкой.

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

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

В любом случае, это эвристика, так что это ДОЛЖНО быть полным дерьмом, и не всегда работать в любом случае ...

Измерьте с помощью микрометра, отметьте мелом, порежьте топором.

0 голосов
/ 02 июня 2010

Я предполагаю следующее:

  • что вы имеете в виду числа с плавающей точкой одинарной точности IEEE 754.
  • что знаковый бит с плавающей запятой сохраняется в MSB целого числа.

Итак, поехали: 

static boolean probablyFloat(uint32_t bits) {
  bool sign = (bits & 0x80000000U) != 0;
  int exp = ((bits & 0x7f800000U) >> 23) - 127;
  uint32_t mant = bits & 0x007fffff;

  // +- 0.0
  if (exp == -127 && mant == 0)
    return true;

  // +- 1 billionth to 1 billion
  if (-30 <= exp && exp <= 30)
    return true;

  // some value with only a few binary digits
  if ((mant & 0x0000ffff) == 0)
    return true;

  return false;
}

int main() {
  assert(probablyFloat(1065353216));
  assert(probablyFloat(1084227584));
  assert(probablyFloat(1085276160));
  assert(probablyFloat(1068149391));
  assert(probablyFloat(1083179008));
  assert(probablyFloat(1120403456));
  assert(probablyFloat(0));
  assert(probablyFloat(-1110651699));
  assert(probablyFloat(1195593728));
  return 0;
}
0 голосов
/ 21 марта 2010

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

0 голосов
/ 21 марта 2010

Вы будете смотреть на старшие 8 или 9 бит. Вот где знак и мантисса значения с плавающей запятой. Значения 0x00 0x80 и 0xFF здесь довольно редки для правильных данных с плавающей точкой.

В частности, если все старшие 9 битов равны 0, то это, вероятно, будет действительным значением с плавающей запятой, только если все 32 бита равны 0. Другой способ сказать, что если показатель степени равен 0, мантисса также должна быть равна нулю , Если старший бит равен 1, а следующие 8 битов равны 0, это допустимо, но также вряд ли будет действительным. Он представляет -0.0, что является допустимым значением с плавающей запятой, но бессмысленным.

Чтобы выразить это в числовом выражении. если старший байт равен 0x00 (или 0x80), то значение имеет величину самое большее 2,35e-38. Постоянная Планка составляет 6,62e-34 м2кг / с, что на 4 порядка больше. Расчетный диаметр протона намного больше, чем этот (оценивается в 1.6e-15 метров). Наименьшее ненулевое значение для аудиоданных составляет около 2,3e-10. Вы вряд ли увидите, что значения с плавающей точкой являются допустимыми измерениями чего-либо реального, которое меньше, чем 2.35e-38, но не ноль.

Если двигаться в другом направлении, если старший байт равен 0xFF, то это значение равно либо бесконечности, либо NaN, либо больше по величине, чем 3,4e + 38. Возраст Вселенной оценивается в 1,3e + 10 лет (1,3e + 25 фемтосекунд). Наблюдаемая вселенная имеет примерно e + 23 звезды, число Авагадро - 6.02e + 23. Еще раз значения с плавающей запятой, большие чем e + 38, редко обнаруживаются в допустимых измерениях.

Это не означает, что FPU не может загружать или производить такие значения, и вы непременно увидите их в промежуточных значениях вычислений, если вы работаете с современными FPU. Современный FPU будет загружать значение с плавающей запятой, имеющее показатель степени 0, но другие биты не равны 0. Они называются денормализованными значениями. Вот почему вы видите, что маленькие положительные целые числа отображаются как значения с плавающей точкой в ​​диапазоне e-42, хотя нормальный диапазон значений с плавающей точкой уменьшается только до e-38

Показатель всех 1 представляет Бесконечность. Вы, вероятно, не найдете бесконечности в своих данных, но вы знаете лучше, чем я. -Infinity равно 0xFF800000, + Infinity равно 0x7F800000, любое значение, кроме 0 в мантиссе Infinity, искажено. искаженные бесконечности используются в качестве NaN.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...