Expand the precision of our log10 lookup tables + add precision
authorMatt Corallo <git@bluematt.me>
Sun, 3 Apr 2022 20:16:03 +0000 (20:16 +0000)
committerMatt Corallo <git@bluematt.me>
Sun, 10 Apr 2022 21:29:33 +0000 (21:29 +0000)
commit4930af9b54840fb19e3258f70f73034eb0a003c7
treea31bb810cc2384ae9f9c5cc4d7bbd8f9033c0a8b
parent02bebee62e1a2becdc8ee71704c913e8bb367d02
Expand the precision of our log10 lookup tables + add precision

When we send values over channels of rather substantial size, the
imprecision of our log lookup tables creates a rather substantial
non-linearity between values that round up or down one bit.

For example, with the default scoring values, sending 100k sats
over channels with 1m, 2m, 3m, and 4m sats of capacity score
rather drastically differently: 3645, 2512, 500, and 1442 msat.

Here we expand the precision of our log lookup tables rather
substantially by: (a) making the multiplier 2048 instead of 1024,
which still fits inside a u16, and (b) quadrupling the size of the
lookup table to look at the top 6 bits after the most-significant
bit of an input instead of the top 4.

This makes the scores of the same channels substantially more
linear, with values of 3613, 1977, 1474, and 1223 msat.

The same channels would be scored at 3611, 1972, 1464, and 1216
msat with a non-approximating scorer.
lightning/src/routing/scoring.rs