Округленное разделение мощностью 2

Я реализую алгоритм квантования из учебника. Я нахожусь в том месте, где многое работает, за исключением того, что я получаю ошибки при округлении. Это то, что учебник должен сказать об этом:

Округленное деление на 2^p может быть выполнено путем добавления смещения и смещения вправо по p-разрядным позициям

Теперь я получаю бит о правильной смене, но о каком смещении они говорят?

Вот мой пример кода:

def scale(x, power2=16):
    if x < 0:
        return -((-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()

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

Мой вывод:

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

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

Ответ 1

Смещение будет усечено. Смещение - это двоичный оператор. Я использую квадратные скобки для обозначения базы здесь:

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

Для выполнения правильного округления вам нужно добавить половину своего делителя перед выполнением сдвига.

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

Ответ 2

Сдвиг на p дает деление на 2 ^ p округленное вниз (усеченное).

Если вы хотите разделить на 2 ^ p, но округлите до ближайшего целого числа, выполните:

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

В вашем коде:

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

Ответ 3

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

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

def scale(x, power2=16):
    divider = float(1<<power2)
    result = round(x/divider)
    return result

Однако мы получаем следующие ошибки:

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

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

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

Таким образом, если округленное деление - это то, что вы действительно хотите, ваш список ожидаемых значений должен быть:

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

Ответ 4

"Ожидаемые" ответы просто не согласуются с одним из возможных методов округления (вниз, ближе, вверх) и очевидны из положительных дивидендов, прежде чем мы рассмотрим осложнения, введенные отрицательными дивидендами.

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

Таким образом, down получает 6 из 8, ближайший получает 5, а вверх получает только 2.

Какой учебник? Это имя "Name'n'Shame"!

Обновить после дальнейших экспериментов:

Если вы добавите 8192 только перед тем, как выполнить деление на 65536, вы получите ожидаемые результаты. Никакая другая сила 2 в (512,..., 32768) не имеет такого же эффекта.

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

Перепишите: объект должен округлить до наибольшего целого числа, но ввести смещение к нулю (меньшие абсолютные целые числа). Округление до ближайшего будет сделано путем добавления в 32768 перед усечением деления. Использование меньшего "смещения", чем 32768, дает желаемый эффект смещения. Если смещение равно 2, например, 2 ** k, это может быть выполнено: shift k bits, add 1, shift 16-k bits.