Hacker News Reader

Comment by lugao | Hacker News Reader

I think the point here is to explore the reduction of these functions to finite binary trees using a single binary operator and a single stopping constant. The operator used could be arbitrarily complex; the objective is to prove that other expressions in a certain family — in this case, the elementary functions — can be expanded as a finite (often incomplete) binary tree of that same operation.

In other words, this result does not aim to improve computability or bound the complexity of calculating the numerical value. Rather, it aims to exhibit this uniform, finite tree structure for the entire family of elementary expressions.

View on HN

I think there is still an implicit restriction on the complexity of the operator for this to be interesting. Otherwise you could design an operator which accepts a pair x,y and performs one of 2^k elementary binary operations by reading off the first k bits of x and applying the specified operation on the remainder of x and y. (This is kind of like how real-valued computational models become too powerful for complexity theory to work if you allow bitwise operations.)

Exactly! If you didn't strictly limit the operator's complexity, you could just smuggle a Turing machine in via bitwise logic and turn the whole thing into a parlor trick. The beauty here is that eml(x,y) is a pure, continuous analytical function with no hidden branching whatsoever.

To clarify my earlier point: the author isn't trying to build a practical calculator or generate human-readable algebra. Using exp and ln isn't a cheat code because the goal is purely topological. The paper just proves that this massive, diverse family of continuous math can be mapped perfectly onto a uniform binary tree, without secretly burying a state machine inside the operator.

> The beauty here is that eml(x,y) is a pure, continuous analytical function with no hidden branching whatsoever.

They use the complex version of logarithm, that has a lot of branching problems.

Different sense of “branching”

Yep.

Well, the paper explicitly takes the principal branch to solve this.

So it isn't exploiting the branching for computation.

I agree, as the sibling comment there are two different things that are named "branches". Anyway, to get the principal branch in the microprocessor it's necessary to implement "atan2" that has a lot of special cases.

For example, IIRC ln( -inf.0 + y * i ) = ´+inf.0 + pi * sign(y)

Reply on news.ycombinator.com