I wonder how this combines with Richardson's Theorem.
All elementary functions from a single binary operator
211–220 of 317 posts
Re: All elementary functions from a single binary operator
#212I like this guy. https://th.if.uj.edu.pl/~odrzywolek/homepage/index.html
Re: All elementary functions from a single binary operator
#213Earlier quoted context omitted.
The exponential blowup is in the symbolic regression section, where to search among depth K trees requires 2^K parameters. As an example, searching for sqrt(x) would require a tree of depth ~40 which is in the trillion-parameter regime.
But that is not an increase in the expression size, that is the effort for searching for an expression tree that fits some target function. And that is no different from searching an expression based on common functions, that is of course also exponential in the expression tree height. The difference is that a eml-based tree will have a larger height - by some constant factor - than a tree based on common functions.…
Ah I see I misunderstood your point, thanks for clarifying.
I think you are right, each node in some other expression tree formed of primitives in some set Prim would be increased by at most max(nodes(expr)) for expr in Prim.
That's essentially what the EML compiler is doing from what I understand.
Re: All elementary functions from a single binary operator
#214Earlier quoted context omitted.
It would almost always be much, much worse. Practical numerical libraries (whether implemented in hardware or software) contain lots of redundancy, because their goal is to give you an optimized primitive as close as possible to the operation you actually want. For example, the library provides an optimized tan(x) to save you from calling sin(x)/cos(x), because one nasty function evaluation (as a power series, lookup…
I actually don't think this is true - Traditional processors, even highly dedicated ones like TMUs in gpus, still require being preconfigured substantially in order to switch between sin/cos/exp2/log2 function calls, whereas a silicon implementation of an 8-layer EML machine could do that by passing a single config byte along with the inputs. If you had a 512-wide pipeline of EML logic blocks in modern silicon (say 5…
So to clarify, you think that replacing every multiplication with 24 transcendental function evaluations (12 eml(x, y), each of which evaluates exp(x) and ln(y) plus the subtraction; see the paper's Fig 2) is somehow a win?
The fact that addition, subtraction, and multiplication run quickly on typical processors isn't arbitrary--those operations map well onto hardware, for roughly the same reasons that elementary school students can easily hand-calculate them. General transcendental functions are fundamentally more expensive in time, die area, and/or power, for the same reasons that elementary school students can't easily hand-calculate them. A primitive where all arithmetic (including addition, subtraction, or negation) involves multiple transcendental function evaluations is not computationally faster, lower-power, lower-area, or otherwise better in any other practical way.
The comments here are filled with people who seem to be unaware of this, and it's pretty weird. Do CS programs not teach computer arithmetic anymore?
Re: All elementary functions from a single binary operator
#215I like this guy. https://th.if.uj.edu.pl/~odrzywolek/homepage/index.html
Oh my god the PC history is hilarious
https://th.if.uj.edu.pl/~odrzywolek/homepage/personal/pc/pc_...
Re: All elementary functions from a single binary operator
#216That's quite interesting.
Few ideas that come to my mind when reading this:
1. One should also add absolute value (as sqrt(x*x)?) as a desired function and from that min, max, signum in the available functions. Since the domain is complex some of them will be a bit weird, I am not sure.
2. I think, for any bijective function f(x) which, together with its inverse, is expressible using eml(), we can obtain another universal basis eml(f(x),f(y)) with the added constant f^-1(1). Interesting special case is when f=exp or f=ln. (This might also explain the EDL variant.)
3. The eml basis uses natural logarithm and exponent. It would be interesting to see if we could have a basis with function 2^x - log_2(y) and constants 1 and e (to create standard mathematical functions like exp,ln,sin...). This could be computationally more feasible to implement. As a number representation, it kinda reminds me of https://en.wikipedia.org/wiki/Elias_omega_coding.
4. I would like to see an algorithm how to find derivatives of the eml() trees. This could yield a rather clear proof why some functions do not have indefinite integrals in a symbolic form.
5. For some reason, extending the domain to complex numbers made me think about fuzzy logics with complex truth values. What would be the logarithm and exponential there? It could unify the Lukasiewicz and product logics.
Re: All elementary functions from a single binary operator
#217I like this guy. https://th.if.uj.edu.pl/~odrzywolek/homepage/index.html
Definitely prefer his old-school page to the vibe-coded-design page,
Re: All elementary functions from a single binary operator
#218Earlier quoted context omitted.
They are done with transistors though. Transistors form an efficient, single element, universal digital basis. And are a much less arbitrary choice than NAND, vs. NOR, XOR, etc. Using transistors as conceptual digital logic primitives, where power dissipation isn't a thing, Pass Logic is "The Way".
> Transistors form an efficient, single element, universal digital basis But transistors can be N or P-channel, so it’s not a single logical primitive, like e.g. NAND-gates.
True.
NAND also use both N and P-channel transistors, and have to use at least the same number, but frequently many more transistors for anything non-trivial.
But as you point out, as a computational basis, pass transistors have two variants.
Re: All elementary functions from a single binary operator
#219Earlier quoted context omitted.
I actually don't think this is true - Traditional processors, even highly dedicated ones like TMUs in gpus, still require being preconfigured substantially in order to switch between sin/cos/exp2/log2 function calls, whereas a silicon implementation of an 8-layer EML machine could do that by passing a single config byte along with the inputs. If you had a 512-wide pipeline of EML logic blocks in modern silicon (say 5…
So to clarify, you think that replacing every multiplication with 24 transcendental function evaluations (12 eml(x, y), each of which evaluates exp(x) and ln(y) plus the subtraction; see the paper's Fig 2) is somehow a win? The fact that addition, subtraction, and multiplication run quickly on typical processors isn't arbitrary--those operations map well onto hardware, for roughly the same reasons that elementary sch…
For basic arithmetic, this is not required nor would it be faster, as it is not likely advantageous for bulk static transcendal functions. Where this becomes interesting is when combining them OR when chaining them where today they must come back out to the main process for reconfiguration and then re-issued.
Practical terms: Jacobian (heavily used in weather and combustion simulation): The transcendental calls, mostly exp(-E_a/RT), are the actual clock-cycle bottleneck. The GPU's SFU computes one exp2 at a time per SM. The ALU then has to convert it (exp(x) = exp2(x × log2(e))), multiply by the pre-exponential factor, and accumulate partial derivatives. It's a long serial chain for each reaction rate.
The core of this is the Arrhenius rate, (A × T^n × exp(-E_a/(R×T))), which involves an exponentiation, a division, a multiplication, and an exponential. On a GPU, that's multiple SFU calls chained with ALU ops. In an EML tree, the whole expression compiles to a single tree that flows through the pipeline in one pass.
GPU (PreJacGPU) is currently the state of the art for speed on these simulations - a moderate width 8-depth EML machine could process a very complex Jacobian as fast as the gpu can evaluate one exp(). Even on a sub-optimal 250mhz FPGA, an entire 50x50 Jacobian would be about 3.5 microseconds vs 50 microseconds PER Jacobian on an A100.
If you put that same logic path into an ASIC, you'd be about 20x the fPGA's speed - in the nanoseconds per round. And this is not like you're building one function into an ASIC it's general purpose. You just feed it a compiled tree configuration and run your data through it.
For anything like linear algebra math, which is also used here, you'd delegate that to the dedicated math functions on the processor - it wouldn't make sense to do those in this.
Re: All elementary functions from a single binary operator
#220Earlier quoted context omitted.
On page 11, the paper explicitly states: > EML-compiled formulas work flawlessly in symbolic Mathematica and IEEE754 floating-point… This is because some formulas internally might rely on the following properties of extended reals: ln 0 = −∞, e^(−∞) = 0. And then follows with: > But EML expressions in general do not work ‘out of the box’ in pure Python/Julia or numerical Mathematica. Thus, the paper’s completeness cl…
I would not call a "non-standard arithmetic convention" that ln(0) = -∞. This is the standard convention when doing operations in the extended real number line, i.e. in the set of the real numbers completed with positive and negative infinities. When the overflow exception is disabled, any modern CPU implements the operations with floating-point numbers as operations in the extended real number line. So in computing…
Apparently Python throws an exception. This surprised me, I expected it to only throw for integers. Throwing for floats is weird and unsafe.
>>> import math
>>> math.log(0.0)
Traceback (most recent call last):
File "", line 1, in
math.log(0.0)
~~~~~~~~^^^^^
ValueError: expected a positive input, got 0.0
>>> import numpy as np
>>> np.log(np.float64(0))
:1: RuntimeWarning: divide by zero encountered in log
np.float64(-inf)
> Math.log(0.0)
-Infinity
> Math.log(-0.0)
-Infinity
> Math.log(-0.1)
NaN