Earlier quoted context omitted.
Show me a way to physically compute exp or ln that is less gates than add. More gates means costlier in $, more energy in compute, and for these functions, higher latency. You don’t get to make up free ops, claim there is no cost in reality, and hand wave away reality. There are infinitely many ways to do what the paper did. There’s no gain other than it’s pretty. It loses on every practical front to simply using cur…
The feasibility of memristor analog circuits is evident, and I believe this paper represents a valuable early exploration. We've been constrained by Boolean logic for quite some time now.
All elementary functions from a single binary operator
291–300 of 317 posts
Re: All elementary functions from a single binary operator
#292Earlier quoted context omitted.
And those come from the infinite series needed to compute exp and ln. They’re just as much work either way. The exp and ln way are vastly costlier for every op, including simply adding 1 and 2.
It's not about being costly or not, this is completely irrelevant to the point being made. eml is just some abstract function, that maps ℝ² to ℝ. Same as every other mathematical function it is only really defined by the infinite set of correspondences from one value to some other value. It is NOT exp(x) - ln(y), same as exp is not a series (as you wrongfully stated in another comment). exp can be expressed (and/or d…
Re: All elementary functions from a single binary operator
#293Earlier quoted context omitted.
In my experience this exponential expression blow-up is less the result of the approach of decomposing into a minimum of primitives, but rather a result from repetition in expression trees: If we make the analogy from Bertrand Russel's Principia Mathematica, he derived fully expanded expressions, i.e. trees where the leaves only may refer to the same literals, everyone claimed this madness underscored how formal veri…
Yes, metamath uses a large collection of specialized but reusable building blocks, so it doesn't blow up exponentially. However, if you want to "just do gradient descent" on general trees built from a single universal primitive, you now have to rediscover all those building blocks on the fly. And while the final result may have a compact representation as a DAG by merging common subexpressions, you also need to be ab…
Thats not really necessary, imagine somewhere near the top of the binary tree a leaf ("1" or "x" or ...), with the current brute force method thats a whole binary subtree with parameters going unused.
One could just as well use that whole culled binary subtree as a DAG node.
It does require more complex routing, but selecting input nodes is a sparse task, so those routing parameters can use sparse virtual parameters, say inner products of dense vectors in some vector space, so it doesn't need to take up much memory...
Re: All elementary functions from a single binary operator
#294Earlier quoted context omitted.
Any transcendental function can be produced by arithmetic, since its complete for R. Go ahead and show how to compute exp or ln without an infinite series without circular reasoning. You can’t, since they’re transcendental. There are infinitely many ways to make these binary operators. Picking extremely high compute cost ones really doesn’t make a good basis for computation.
> Any transcendental function can be produced by arithmetic, since its complete for R. Not without some form of limit process or construction. You can approximate e with the basic arithmetic operations but not actually get an exact form in finite steps. And you definitely cannot transverse an infinite binary tree, so the main point of the result in the article is missed by your arguments. Again, you are mixing separa…
A limit process is a definition. Try computing with it. You’ll end up with an infinite sequence, or an approximation.
An iterative process is an infinite series. They’re equivalent.
Newtons method is the same. Completely equivalent to an infinite series as you increase precision.
And both require constants, infinitely precise. So you’re still not doing anything the 1/(x-y) operation cannot do, and to do those series you’ll compute using things amenable to being done via ops easy to do by hand or machine via the 1/(x-y) op.
Re: All elementary functions from a single binary operator
#295Earlier quoted context omitted.
Show me a way to physically compute exp or ln that is less gates than add. More gates means costlier in $, more energy in compute, and for these functions, higher latency. You don’t get to make up free ops, claim there is no cost in reality, and hand wave away reality. There are infinitely many ways to do what the paper did. There’s no gain other than it’s pretty. It loses on every practical front to simply using cur…
> no gain other than it’s pretty Conceptual elegance is worth something, isn't it? I don't mean just aesthetic pleasure, as in recreational mathematics, but there's often (not always) value in being able to succinctly describe a wide range of phenomena with a small number of primitives. It could open up new ways of understanding or working that wasn't possible before. Not saying this specific discovery fits the descr…
Re: All elementary functions from a single binary operator
#296Earlier quoted context omitted.
It's not about being costly or not, this is completely irrelevant to the point being made. eml is just some abstract function, that maps ℝ² to ℝ. Same as every other mathematical function it is only really defined by the infinite set of correspondences from one value to some other value. It is NOT exp(x) - ln(y), same as exp is not a series (as you wrongfully stated in another comment). exp can be expressed (and/or d…
His paper misses infinitely many such functions.
In your original post you were kinda hand-wavy about what we have except for x # y := 1/(x-y), but your examples make it clear you also assume 0 exists. Then it's pretty obvious how to get: identity function, reciprocity, negation, substraction & addition. But I effectively couldn't get anywhere past that. In fact, I got myself convinced that it's provably impossible to define (e.g.) multiplication as a tree of compositions of # and 0.
So here's my interpretation of what you actually meant:
1. I suppose, you assumed we already have ℕ and can sample anything from it. Meaning, you don't need to define 5, you just assume it's there. Well, to level things out, (#, 0, 1) are enough to recover ℤ, so I assume you assumed at least these three. Is that right?
2. Then, I suppose you assumed that since we have addition, multiplication simply follows from here. I mean at this point we clearly have f(x) = 3x, or 4x, or 5x, … so you decided that the multiplication is solved. Because I couldn't find how to express f(x, y) = x⋅y, and as far, as I can tell, it's actually impossible. If I'm wrong, please show me x⋅y defined as a sequence of compositions of (#, 0, 1).
3. This way (assuming №2) we get (ℚ, +, -, ⋅, /). Then, I suppose, you assume we can just define exp(x) as its Taylor series, so we also have all roots, trig functions, etc., and then we obviously have all numbers from ℝ, that are values of such functions acting on ℚ. Exactly as we do in any calculus / real analysis book, with limits and all that jazz.
If that's what you actually meant, I'm afraid you completely missed the point, and 1/(x-y) in fact isn't nearly as good as eml for the purposes of Odrzywołek's paper. Now, I didn't actually verify his results, so I just take them for granted (they are totally believable though, since it's easy to se how), but what he claims is that we can use eml essentially as a gate, like Sheffer stroke in logic, and express "everything else" just as a sequence of such gates and constant 1 (and "everything else" here is what I listed in №3). No words, limits, sets and other familiar mathematical formalism, just one operation and one constant, and "induction" is only used to get all of ℕ, everything else is defined as a finite tree of (eml, 1).
Re: All elementary functions from a single binary operator
#297Built a JS implementation today — monogate https://explorer-taupe-five.vercel.app · npm install monogate The interesting engineering problem was negation. The paper's SI gives one construction; we independently derived a two-regime approach — tower formula for y≤0, shift formula for y>0 — that stays stable to |y|<708 in IEEE 754. We also extended to ℂ. After seeing pveierland's result in this thread (i constructible…
Python package is live: github.com/almaguer1986/monogate/tree/main/python — EMLTree (scalar symbolic regression), EMLNetwork (function approximation from data), fully differentiable via PyTorch autograd.
Two experiments ran:
Experiment 1: EMLTree successfully finds e and 0 by gradient descent. It does NOT rediscover eml(1,1) — it finds different valid constructions. The network finds its own paths.
Experiment 2: We swept a complexity penalty (lambda) trying to force the network toward minimal constructions. Instead of snapping cleanly to eml(1,1), the optimizer got stuck in what we're calling a phantom attractor — eml(eml(0.45, 1), eml(1, 1)) — a non-minimal construction that accidentally evaluates to e and resists the penalty. Forcing true minimality costs 10,518% more MSE.
The phantom attractor is a new phenomenon: locally stable non-minimal EML constructions that gradient descent cannot escape. Whether discrete search can escape them is open.
Exhaustive search tool also found -iπ in 11 nodes, improving our hand-proved 12. monogate.dev/search runs in the browser.
Full results: github.com/almaguer1986/monogate/blob/main/python/RESULTS.md
Re: All elementary functions from a single binary operator
#298This is amazing! I love seeing FRACTRAN-shaped things on the homepage :) This reminds me of how 1-bit stacks are encoded in binary: A stack of zeros and ones can be encoded in a single number by keeping with bit-shifting and incrementing. Pushing a 0 onto the stack is equivalent to doubling the number. Pushing a 1 is equivalent to doubling and adding 1. Popping is equivalent to dividing by 2, where the remainder is t…
Re: All elementary functions from a single binary operator
#299This isn't unique, or even the least compute way to do this. For example, let f(x,y) = 1/(x-y). This too is universal. I think there's a theorem stating for any finite set of binary operators there is a single one replacing it. write x#y for 1/(x-y). x#0 = 1/(x-0) = 1/x, so you get reciprocals. Then (x#y)#0 = 1/((1/(x-y)) - 0) = x-y, so subtraction. it's common problem to show in any (insert various algebraic structu…
The OP only needs 1 number: 1.