Hacker News Reader

Given an integer n, what is the number of bits required to represent every integer in the range -n..n ?

Exact integers doesn't seem to be its strong suite. Can it even represent 3 exactly?

Running code from the linked notebook (https://github.com/AdamScherlis/notebooks-python/blob/main/m...), I can see that a 32 bit representation of the number 3 decodes to the following float: 2.999999983422908

(This is from running `decode(encode(3, 32))`)

Yeah I think any numbers away from 0 or infinity aren’t its strong suit.

> Given an integer n, what is the number of bits required to represent every integer in the range -n..n ?

(log n) + 1

That's true for normal binary encoding of integers, but I think we should understand the question in context of the post: What's the number of bits required in iterated log coding?

Empirically, it seems to grow more like 2*log2(n)+1. A handwavy argument can be made that the first bit serves to distinguish the positive values from the negative ones, but after that on average every second bit only adds more precision to values that are already distinguishable or out of range, but doesn't help with values whose representation has the same prefix. I don't know how to make that airtight, though...

Reply on news.ycombinator.com