]> git.sesse.net Git - narabu/commit
Add support for optimal renormalization.
authorSteinar H. Gunderson <sgunderson@bigfoot.com>
Sun, 27 Aug 2017 18:44:04 +0000 (20:44 +0200)
committerSteinar H. Gunderson <sgunderson@bigfoot.com>
Sat, 16 Sep 2017 13:53:50 +0000 (15:53 +0200)
commit062abd7f7c940204d34c496f765aeb143d2d8e6c
tree2fc7d1583a41abc99f7140cc76787296a3cc0fa7
parent8cca8db811c7888058c6093d2f1ae5ae4f00cccc
Add support for optimal renormalization.

The current code for rounding probabilities down to a fixed resolution
is a bit too crude when resolution is low; whether it's optimal to round
up or down depends on the other frequencies, and the code for stealing
slots from other symbols also doesn't take this into account (as the
comment rightfully points out). These effects only really show up when
getting down to lower resolution, e.g. prob_bits = 10, but there, they
can be quite pronounced.

Add a function (0-clause BSD licensed for optimal usefulness, ie. public
domain without potential difficulty about whether private persons can put
anything in the public domain) to calculate the optimal distribution of
encoding slots, basically through brute force plus some memoization.
For e.g. the basic example (main.cpp), the number of bytes for prob_bits = 10
goes down from 440895 to 437590 bytes. (At the default prob_bits = 14, the
difference is very low; from 435113 to 435093 bytes.)

For main_alias.cpp, which has prob_bits = 16, I've kept the existing code,
so that it's not lost to the mists of time in case someone wants something
that's nearly even cheaper in terms of startup cost.
ryg_rans/Makefile
ryg_rans/main.cpp
ryg_rans/main64.cpp
ryg_rans/main_simd.cpp
ryg_rans/renormalize.cpp [new file with mode: 0644]
ryg_rans/renormalize.h [new file with mode: 0644]