Pertanyaan Pembulatan divisi dengan kekuatan 2


Saya menerapkan algoritma kuantisasi dari buku teks. Saya berada di titik di mana banyak hal yang berhasil, kecuali saya mendapatkan kesalahan satu per satu saat pembulatan. Inilah yang harus dikatakan oleh buku teks tentang hal itu:

Pembulatan dibulatkan oleh 2^p dapat dilakukan dengan menambahkan offset dan pengalihan kanan dengan posisi p bit

Sekarang, saya mendapatkan sedikit tentang pergeseran yang tepat, tetapi offset apa yang mereka bicarakan?

Berikut ini contoh kode saya:

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()

Saya sedang memeriksa masukan negatif karena bit menggeser bilangan bulat negatif tampaknya tergantung pada implementasi.

Keluaran saya:

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

Apa offset yang disebutkan dalam buku teks, dan bagaimana saya bisa menggunakannya untuk menyingkirkan kesalahan ini?


12
2018-05-26 07:30


asal


Jawaban:


Pergeseran akan terpotong. Pergeseran adalah operasi operator biner. Saya menggunakan tanda kurung siku untuk menunjukkan basis di sini:

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

Untuk melakukan pembulatan yang benar, Anda perlu menambahkan separuh pembagi Anda sebelum melakukan pergantian.

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

9
2018-05-26 07:46



Pergeseran oleh p memberikan pembagian dengan 2 ^ p dibulatkan ke bawah (terpotong).

Jika Anda ingin membagi dengan 2 ^ p tetapi bulat ke bilangan bulat terdekat, lakukan:

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

Dalam kode Anda:

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

3
2018-05-26 07:54



Seperti yang diduga, algoritma Anda sebenarnya tidak bulat, tetapi memotong divisi. Terlebih lagi, ada kesalahan dalam buku teks Anda. Jadi bahkan jika Anda memperbaiki algoritma Anda, Anda tidak akan mendapatkan hasil yang diharapkan.

Untuk memastikan bahwa hasilnya benar-benar salah, Anda dapat mencoba menjalankan kode Anda dengan fungsi divisi bulat bulat yang benar dan berbasis float:

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

Namun kita mendapatkan kesalahan berikut:

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

Dengan menghitung hasil yang benar untuk pembulatan divisi, kita dapat mengkonfirmasi bahwa harapan ini, pada kenyataannya, salah:

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

Jadi, jika divisi yang dibulatkan adalah yang benar-benar Anda inginkan, daftar nilai harapan Anda seharusnya:

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

1
2018-05-26 09:44



Jawaban "yang diharapkan" tidak konsisten dengan salah satu metode pembulatan yang mungkin (turun, terdekat, naik) dan itu jelas dari dividen positif, sebelum kita mempertimbangkan komplikasi yang diperkenalkan oleh dividen negatif.

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

Jadi turun mendapat 6 dari 8, yang terdekat mendapat 5, dan naik hanya mendapat 2.

Buku teks apa? Ini adalah waktu "Nama'n'Shame"!

Memperbarui setelah eksperimen lebih lanjut:

Jika Anda menambahkan 8192 tepat sebelum Anda melakukan pembagian terpotong sebesar 65536, Anda mendapatkan hasil "yang diharapkan". Tidak ada kekuatan lain 2 dalam (512, ..., 32768) memiliki efek yang sama.

Menggambarkan ini sebagai menambahkan offset ke bias pembulatan ke bawah agak disayangkan.

Penulisan ulang: Objek adalah untuk membulatkan ke integer TERDEKAT, tetapi memperkenalkan bias terhadap nol (integer mutlak lebih kecil). Pembulatan ke terdekat akan dilakukan dengan menambahkan di 32768 sebelum divisi truncating. Menggunakan "offset" yang lebih kecil daripada 32768 memberikan efek bias yang diinginkan. Jika offset adalah kekuatan 2 mis. 2 ** k, itu dapat dilakukan dengan: shift k bit, tambahkan 1, shift 16-k bit.


1
2018-05-26 11:46