Pourquoi ne puis-je pas me coucher & # 8221; une gamme d'entiers dans une moitié de la taille sans perdre d'informations?

Question

J'essaie de comprendre un article sur le traitement sans perte. compression des nombres en virgule flottante et rester bloqué sur une étape en particulier, où les auteurs mappent un nombre entier signé dans une plage allant de la moitié à la moitié de la taille, perdant ainsi les informations que je jugerais nécessaires. J'ai l'impression que les auteurs utilisent une technique standard qui est tellement évidente pour leur auditoire qu'ils ne se donnent pas la peine de l'expliquer, mais qui est complètement opaque pour moi.

La valeur qui est "pliée" est la différence entre deux entiers positifs sur 23 bits (les mantisses d'une valeur prédite et d'une valeur réelle à virgule flottante) qui est comprise entre 1 - 2 ²³ et 2 ²³ - 1. Les auteurs déplacent les nombres avec les valeurs les plus élevées (négatives et positives) "vers l'intérieur", de sorte que la plage résultante est deux fois plus petite et que chaque nombre (sauf 0) mappe sur deux valeurs possibles de la plage d'origine. Cela me fait me demander comment le processus devrait être inversé pour déterminer la valeur initiale. Dans les propres mots des auteurs:

  

Nous calculons le correcteur signé qui est le plus court modulo 2 ²³ et le nombre k qui spécifie l'intervalle le plus court (1-2 ^k , 2 ^k ) dans lequel ce correcteur tombe. Ensuite, ce nombre k , compris entre 0 et 22, est compressé [...]. Enfin, les bits significatifs k + 1 du correcteur sont compressés.

Le pseudocode correspondant est défini comme suit:

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
}

Ignorant la méthode de compression réelle, la sortie consiste en c et k . Ce que je ne comprends pas, c'est: Comment puis-je restaurer le c d'origine à partir de c et de k lorsque l'option "envelopper c dans" ; la partie ci-dessus ne fait que mapper la moitié de la plage potentielle sur l'autre moitié? J'ai essayé ceci sur papier avec 4 bits au lieu de 23 bits et je ne comprends tout simplement pas.

Answer 1

Lorsque l'auteur dit qu'il considère les significations "modulo 2 ^ 23", cela signifie que les nombres seront stockés dans des entiers de 23 bits, de sorte que les nombres qui diffèrent par des multiples de 2 ^ 23 seront "les mêmes". puisque le motif de bits est le même. (Voir http://mathworld.wolfram.com/ModularArithmetic.html )

Depuis le " emballage " le code après c = a-p ajoute ou soustrait seulement 2 ^ 23 à c, lorsque vous inverserez cela en calculant a = c + p, vous obtiendrez la bonne valeur, car le 2 ^ 23 importe peu.

Voici un exemple en binaire ...

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

alors, puisque c < = - (1 < < 22), l’emballage se produit ...

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

Ce qui est ensuite encodé. Ensuite, vous pourrez récupérer a de c et p:

a = c+p =      100000000000000000000001

mais puisque ceci est stocké dans un entier de 23 bits, cela équivaut à:

a =             00000000000000000000001

qui est l'original.