Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Iterated Log Coding

adamscherlis.github.io

Post reply on HN
Print view View original

31–40 of 40 posts

Re: Iterated Log Coding

#31

Post by jillesvangurp »

Retr0id wrote: post #6

How feasible is it to do arithmetic directly in this representation?

For low bit representations, you could just pre-calculate all the possible answers and cache those. A simple algorithm would be to decode numbers, do the arithmetic, and re-encode the answer. With the seven bit example used in the article, there are only 2^7 = 128 unique numbers. So you'd need 16KB of memory to store all possible multiplications. With 16 bit numbers that grows to 4GB. Beyond that, it probably gets too expensive rapidly. You might get some optimizations out of the symmetry for positive and negative.

Re: Iterated Log Coding

#32

Post by yorwba »

karparov wrote: post #30
yorwba wrote: post #28

Earlier quoted context omitted.

It is not. (There are no square roots, for instance.)

It very much is. sqrt(x) is just x^(1/2) which is x^(2^-1). Dirac's solution is using iterated square root of 2, effectively generating a sequence similar to what's used in this post.

Okay, but iterating square roots like √√2 = (2^(2^-1))^(2^-1) recurses into the base, whereas the equivalent iterated log is 2^(2^-1 × 2^-1) = 2^(2^-2) = +2^(+2^(-2^(+2^0))) with the bit representation [1 1 0 0 1 0 0 ...], i.e. it recurses into the exponent.

Re: Iterated Log Coding

#33

Post by vednig »

holy Father! this is amazing, the things a human mind can do, ask an LLM for that and it'll give you 10 more complicated and unmaintainable ways to do it.

Re: Iterated Log Coding

#34

Post by lblume »

dullcrisp wrote: post #19
lblume wrote: post #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.

Who said anything about practical purposes?

I usually like my float representations to have some use. But sure, this does seem like a very interesting idea.

Re: Iterated Log Coding

#35

Post by dullcrisp »

lblume wrote: post #34
dullcrisp wrote: post #19

Earlier quoted context omitted.

Who said anything about practical purposes?

I usually like my float representations to have some use. But sure, this does seem like a very interesting idea.

> I usually like my float representations to have some use.

If this does have some use, I don’t think representing real-world numbers is one of them, for the reasons you intuited.

Re: Iterated Log Coding

#36

Post by snarkconjecture »

DannyBee wrote: post #23

Isn't this just a variant of Dirac's solution for representing any number using sqrt, log, and the number 2?

Not really. Dirac's trick works entirely at a depth of two logs, using sqrt like unary to increment the number. It requires O(n) symbols to represent the number n, i.e. O(2^n) symbols to represent n bits of precision. This thing has arbitrary nesting depth of logs (or exps), and can represent a number to n bits of precision in O(n) symbols.

Re: Iterated Log Coding

#37

Post by DannyBee »

snarkconjecture wrote: post #36
DannyBee wrote: post #23

Isn't this just a variant of Dirac's solution for representing any number using sqrt, log, and the number 2?

Not really. Dirac's trick works entirely at a depth of two logs, using sqrt like unary to increment the number. It requires O(n) symbols to represent the number n, i.e. O(2^n) symbols to represent n bits of precision. This thing has arbitrary nesting depth of logs (or exps), and can represent a number to n bits of precision in O(n) symbols.

Sure, but that was because that was an arbitrary restriction on the problem dirac solved.

Still seems a fairly simple variation once you remove the arbitrary restriction. To the point: I don't believe for a second that anyone familiar with his solution, asked to make it more bit efficient, would not have come up with this. Nor do I believe they would call it anything other than a variation.

That doesn't make it less cool but I don't think it's like amazingly novel.

Re: Iterated Log Coding

#38

Post by DannyBee »

yorwba wrote: post #32
karparov wrote: post #30

Earlier quoted context omitted.

It very much is. sqrt(x) is just x^(1/2) which is x^(2^-1). Dirac's solution is using iterated square root of 2, effectively generating a sequence similar to what's used in this post.

Okay, but iterating square roots like √√2 = (2^(2^-1))^(2^-1) recurses into the base, whereas the equivalent iterated log is 2^(2^-1 × 2^-1) = 2^(2^-2) = +2^(+2^(-2^(+2^0))) with the bit representation [1 1 0 0 1 0 0 ...], i.e. it recurses into the exponent.

So uh, how is that not a variation, exactly?

Dirac's solution was also arbitrarily restricted by the problem definition.

Do you believe that if you asked someone familiar with the solution to come up with a bit efficient variant they would not have trivially come up with the encoding in this post and called it a variation?

I don't, for a second, believe that.

Re: Iterated Log Coding

#39

Post by fc417fc802 »

BreakMaker9000 wrote: post #27
fc417fc802 wrote: post #12

It'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…

Agree, I had to ask ChatGPT to explain this to me with an example number and then I was able to understand the approach.

It was successfully able to run through the math? I'm surprised. That's quite impressive.
Post reply on HN