3 ms·

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

• lmm 2y ago
  > Given an integer n, what is the number of bits required to represent every integer in the range -n..n ? (log n) + 1
  • maggit 2y ago
    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?
    • yorwba 2y ago
      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...
• maggit 2y ago
  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/math/iterlog_coding.ipynb 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))`)
  • dullcrisp 2y ago
    Yeah I think any numbers away from 0 or infinity aren’t its strong suit.