División redondeada por potencia de 2.

Estoy implementando un algoritmo de cuantización de un libro de texto. Estoy en un punto en el que las cosas funcionan bastante bien, excepto que recibo errores off-by-one al redondear. Esto es lo que el libro de texto tiene que decir al respecto:

La división redondeada por 2^p se puede llevar a cabo agregando un desplazamiento y un desplazamiento a la derecha mediante p posiciones de bit

Ahora, entiendo el cambio correcto, pero ¿de qué compensación están hablando?

Aquí está mi código de muestra:

 def scale(x, power2=16): if x > power2) else: return x >> power2 def main(): inp = [ 12595827, -330706, 196605, -387168, -274244, 377496, -241980, -545272, -196605, 24198, 196605, 193584, 104858, 424683, -40330, 41944 ] expect = [ 192, -5, 3, -6, -4, 5, -3, -8, -3, 0, 3, 3, 1, 6, 0, 0 ] actual = map(scale, inp) for i in range(len(expect)): if actual[i] == expect[i]: continue print 'inp: % 8d expected: % 3d actual: % 3d err: %d' % (inp[i], expect[i], actual[i], expect[i] - actual[i]) if __name__ == '__main__': main() 

Estoy comprobando la entrada negativa, ya que el desplazamiento de bits de un entero negativo parece ser dependiente de la implementación.

Mi salida:

 inp: 196605 expected: 3 actual: 2 err: 1 inp: -387168 expected: -6 actual: -5 err: -1 inp: -196605 expected: -3 actual: -2 err: -1 inp: 196605 expected: 3 actual: 2 err: 1 inp: 193584 expected: 3 actual: 2 err: 1 

¿Cuál es el desplazamiento que se menciona en el libro de texto y cómo puedo usarlo para deshacerme de este error?

El cambio se truncará. El cambio es un operador binario operativo. Estoy usando corchetes para denotar la base aquí:

 196605[10] = 101111111111111111[2] 101111111111111111[2] >> 16[10] = 10[2] = 2[10] 

Para realizar el redondeo correcto, debe agregar la mitad de su divisor antes de hacer el cambio.

 101111111111111111[2] + 1000000000000000[2] >> 16[10] = 110111111111111111[2] >> 16[10] = 11[2] = 3[10] 

Desplazar por p da una división por 2 ^ p redondeada hacia abajo (truncada).

Si desea dividir por 2 ^ p pero redondear al entero más cercano, haga:

 shift-right by (p-1) add 1 shift-right 1 

En su código:

 def scale(x, power2=16): if x < 0: return -((((-x) >> (power2-1)) + 1) >> 1) else: return ((x >> (power2-1)) + 1) >> 1 

Como se sospechaba, su algoritmo no está realmente redondeado, sino truncando la división. Lo que es más es que también hay errores en tu libro de texto . Así que incluso si arreglas tu algoritmo, no obtendrás los resultados esperados.

Para confirmar que los resultados son de hecho defectuosos, puede intentar ejecutar su código con una función de división redondeada basada en flotación correcta:

 def scale(x, power2=16): divider = float(1< 

Sin embargo, tenemos los siguientes errores:

 inp: 377496 expected: 5 actual: 6 err: -1 inp: -241980 expected: -3 actual: -4 err: 1 inp: 104858 expected: 1 actual: 2 err: -1 inp: -40330 expected: 0 actual: -1 err: 1 inp: 41944 expected: 0 actual: 1 err: -1 

Al calcular los resultados correctos para la división de redondeo, podemos confirmar que estas expectativas, de hecho, son erróneas:

 377496 / 65536 = 5,7601 -> should round to 6 104858 / 65536 = 1,600 -> should round to 2 -241980 / 65536 = -3,692 -> should round to -4 104858 / 65536 = 1,600 -> should round to 2 -40330 / 65536 = -0,6154 -> should round to -1 41994 / 65536 = 0,641 -> should round to 1 

Por lo tanto, si lo que realmente desea es una división redondeada, su lista de valores esperados debe ser:

 expect = [ 192, -5, 3, -6, -4, 6, -4, -8, -3, 0, 3, 3, 2, 6, -1, 1 ] 

Las respuestas “esperadas” simplemente no son consistentes con uno de los posibles métodos de redondeo (abajo, más cerca, arriba) y eso es obvio a partir de los dividendos positivos, antes de considerar las complicaciones introducidas por los dividendos negativos.

 dividend exp float div 24198 0 0.3692322 DN 41944 0 0.6400146 D 104858 1 1.6000061 D 193584 3 2.9538574 NU 196605 3 2.9999542 NU 377496 5 5.7601318 D 424683 6 6.4801483 DN 12595827 192 192.1970673 DN 

Así que abajo obtiene 6 de 8, el más cercano obtiene 5, y arriba obtiene solo 2.

¿Qué libro de texto? ¡Es hora de “Name’n’Shame”!

Actualización después de una nueva experimentación:

Si agrega 8192 justo antes de realizar la división truncada por 65536, obtiene los resultados “esperados”. Ninguna otra potencia de 2 en (512, …, 32768) tiene el mismo efecto.

Describir esto como agregar un desplazamiento al redondeo de sesgo hacia abajo es algo desafortunado.

Reescribir: el objeto es redondear al entero más CERCANO, pero introducir un sesgo hacia cero (enteros absolutos más pequeños). El redondeo al más cercano se haría agregando 32768 antes de la división de truncamiento. Usando un “desplazamiento” más pequeño que 32768 se obtiene el efecto de polarización deseado. Si el desplazamiento es una potencia de 2, por ejemplo, 2 ** k, puede hacerse mediante: shift k bits, add 1, shift 16-k bits.