Почему я могу «сложить» диапазон целых чисел в половину размера без потери информации? - PullRequest
Новая
       11

Почему я могу «сложить» диапазон целых чисел в половину размера без потери информации?

3 голосов
/ 10 сентября 2009

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

Свернутое значение - это разница между двумя 23-разрядными положительными целыми числами (мантиссами предсказанного и фактического значения с плавающей запятой), которая находится между 1 - 2 23 и 2 * 1007. * 23 - 1. Авторы перемещают числа с наивысшими значениями (отрицательными и положительными) «внутрь», поэтому результирующий диапазон равен половине размера, и каждое число (кроме 0) отображается на два возможных значения из исходного диапазона , Это заставляет меня задуматься о том, как процесс должен быть полностью изменен, чтобы определить первоначальное значение. По словам авторов:

Мы вычисляем подписанный корректор, который является самым коротким по модулю 2 23 и числом k, которое задает самый короткий интервал (1-2 k , 2 k ) в который попадает этот корректор. Затем это число k, которое находится в диапазоне от 0 до 22, сжимается [...]. Наконец, k + 1 значащие биты корректора сжимаются.

Псевдокод для этого задается как: 

void comp mantissa(int expo, int a, int p) {
  // c will be within [1-2^23 ... 2^23 -1]
  int c = a - p;
  // wrap c into [1-2^22 ... 2^22 ]
  if (c <= -(1<<22)) c += 1<<23;
  else if (c > (1<<22)) c -= 1<<23;
  // find tightest [1-2^k ... 2^k ] containing c
  int k = 0;
  // loop could be replaced with faster code
  int c1 = (c < 0 ? -c : c);
  while (c1) { c1 = c1 >> 1; k++ }
  // adjust k for case that c is exactly 2k
  if (k && (c == 1<<(k-1))) k--;

  // .. further code omitted for brevity
}

Игнорируя фактический метод сжатия, вывод состоит из c и k. Что я не получаю, это: Как я могу восстановить исходные c из c и k, когда вышеприведенная часть "wrap c into" просто отображает половину потенциального диапазона на другую половину? Я попробовал это на бумаге с 4 вместо 23 бит, и я просто не понимаю.

1 Ответ

2 голосов
/ 10 сентября 2009

Когда автор говорит, что он рассматривает значения и «значения по модулю 2 ^ 23», это означает, что числа будут храниться в 23-битных целых числах, поэтому числа, которые отличаются от кратных 2 ^ 23, будут «одинаковыми», поскольку Битовый паттерн такой же. (См. http://mathworld.wolfram.com/ModularArithmetic.html)

Поскольку код «обтекания» после c = ap только добавляет или вычитает 2 ^ 23 к c, когда вы позже обращаете это обратно, вычисляя a = c + p, вы получаете правильное значение, так как 2 ^ 23 не имеет значения.

Вот пример в двоичном коде ... 

a =             00000000000000000000001
p =             10000000000000000000100
c = a-p =      -10000000000000000000011

тогда, поскольку c <= - (1 << 22), происходит обтекание ... </p> 

c = c+(1<<23) = 11111111111111111111101

Который затем кодируется. Затем позже вы можете получить обратно из c и p: 

a = c+p =      100000000000000000000001

но поскольку он хранится в 23-разрядном целом числе, это эквивалентно: 

a =             00000000000000000000001

оригинал а.

...