Округленное деление на степень 2

Question

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

Округленное деление на 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

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

Answer 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]

Answer 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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

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 ]