How feasible is it to do arithmetic directly in this representation?
That's exactly the crux. Addition and subtraction in log space is not exactly straight-forward.
Iterated Log Coding
11–20 of 40 posts
Re: Iterated Log Coding
#12It's a neat encoding but the writeup is needlessly confusing. The introduction would really benefit from a graph or two. Or even just a textual sequence showing how the value evolves as you iterate on it.
Similarly, while the end result is quite elegant the consequences of the choices made to get there aren't really explained. It's quite a bit of extra effort to reason out what would have happened if things had been done differently.
Re: Iterated Log Coding
#13It reminds me of schemes like https://en.wikipedia.org/wiki/Elias_delta_coding , https://en.wikipedia.org/wiki/Elias_omega_coding
As well as https://en.wikipedia.org/wiki/Levenshtein_coding which also encodes iterated lengths.
Re: Iterated Log Coding
#14Earlier quoted context omitted.
> 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...
Re: Iterated Log Coding
#15This feels like you can use e (or I guess any number) for the logarithm base rather than 2. I wonder if that’d make it a bit more uniform in some sense.
Re: Iterated Log Coding
#16Given 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))`)
Re: Iterated Log Coding
#17> Any value representable in n bits is representable in n+1 bits
> [1 1 1 1 1 1 1] 2.004e+19728
Does that mean that the 8 bits version has numbers larger than this? Doesn't seem very useful for 10^100 is already infinity for all practical purposes.
Re: Iterated Log Coding
#18Given 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.
Re: Iterated Log Coding
#19> Any value representable in n bits is representable in n+1 bits > [1 1 1 1 1 1 1] 2.004e+19728 Does that mean that the 8 bits version has numbers larger than this? Doesn't seem very useful for 10^100 is already infinity for all practical purposes.
Who said anything about practical purposes?
Re: Iterated Log Coding
#20> Any value representable in n bits is representable in n+1 bits > [1 1 1 1 1 1 1] 2.004e+19728 Does that mean that the 8 bits version has numbers larger than this? Doesn't seem very useful for 10^100 is already infinity for all practical purposes.
> Does that mean that the 8 bits version has numbers larger than this?
Yes. Not just a bit larger but an even more ridiculous leap. Notice that you're iterating exponents. That last one (7 bits) was 2^65536 so the next one (8 bits) will be 2^2^65536.
Python objects to 2^65536 complaining that the base 10 string to represent the integer contains more than 4300 digits so it gave up.
> Doesn't seem very useful
By that logic we should just use fixed point because who needs to work with numbers as large as 2^1023 (64 bit IEEE 754). These things aren't useful unless you're doing something that needs them, in which case they are. I could see the 5 or 6 bit variant of such an iterated scheme potentially being useful as an intermediary representation for certain machine learning applications.