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

All elementary functions from a single binary operator

arxiv.org

Post reply on HN
Print view View original

181–190 of 317 posts

Re: All elementary functions from a single binary operator

#181

Post by tgtweak »

tgtweak wrote: post #175

This could have some interesting hardware implications as well - it suggests that a large dedicated silicon instruction set could accelerate any mathematical algorithm provided it can be mapped to this primitive. It also suggests a compiler/translation layer should be possible as well as some novel visualization methods for functions and methods.

This paper seems to suggest that a chip with 10 pipeline stages of EML units could evaluate any elementary function (table 4) in a single pass.

I'm curious how this would compare to the dedicated sse or xmx instructions currently inside most processor's instruction sets.

Lastly, you could also create 5-depth or 6-depth EML tree in hardware (fpga most likely) and use it in lieu of the rust implementation to discover weight-optimal eml formulas for input functions much quicker, those could then feed into a "compiler" that would allow it to run on a similar-scale interpreter on the same silicon.

In simple terms: you can imagine an EML co-processor sitting alongside a CPUs standard math coprocessor(s): XMX, SSE, AMX would do the multiplication/tile math they're optimized for, and would then call the EML coprocessor to do exp,sin,log calls which are processed by reconfiguring the EML trees internally to process those at single-cycle speed instead of relaying them back to the main CPU to do that math in generalized instructions - likely something that takes many cycles to achieve.

Re: All elementary functions from a single binary operator

#183

Post by danbruc »

ikrima wrote: post #46
DoctorOetker wrote: post #30

EDIT: please change the article link to the most recent version (as of now still v2), it is currently pointing to the v1 version which misses the figures. I'm still reading this, but if this checks out, this is one of the most significant discoveries in years. Why use splines or polynomials or haphazardly chosen basis functions if you can just fit (gradient descent) your data or wave functions to the proper computati…

From my experience of working in this problem domain for the last year, I'd say it is pretty powerful but the "too good to be true part" comes from that EML buys elegance through exponential expression blow-up. Multiplication alone requires depth-8 trees with 41+ leaves i.e. minimal operator vocabulary trades off against expression length. There's likely an information-theoretic sweet spot between these extremes. It'…

Where do you see exponential blow-up? If you replace every function in an expression tree with a tree of eml functions, that is a size increase by a constant factor. And the factor does not seem unreasonable but in the range 10 to 100.

Re: All elementary functions from a single binary operator

#184

Post by tgtweak »

benleejamin wrote: post #178
tgtweak wrote: post #175

This could have some interesting hardware implications as well - it suggests that a large dedicated silicon instruction set could accelerate any mathematical algorithm provided it can be mapped to this primitive. It also suggests a compiler/translation layer should be possible as well as some novel visualization methods for functions and methods.

I'm not too familiar with the hardware world, but does EML look like the kind of computation that's hardware-friendly? Would love for someone with more expertise to chime in here.

Yes actually, it is very regular which usually lends itself to silicon implementations - the paper event talks about this briefly.

I think the bigger question is whether it will be more energy-optimal or silicon density-optimal than math libraries that are currently baked into these processors (FPUs).

There are also some edge cases "exp(exp(x))" and infinities that seem to result in something akin to "division by zero" where you need more than standard floating-point representations to compute - but these edge cases seem like compiler workarounds vs silicon issues.

Re: All elementary functions from a single binary operator

#185

Post by entaloneralie »

SeanSullivan86 wrote: post #176
entaloneralie wrote: post #22

This 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…

Wouldn't you also need to keep track of the stack's size, to know if there are leading zeros?

For trailing zeros yeah, or if you care for stack overflow/underflow. Here's a few primitives if you wanna try it out:

https://paste.sr.ht/~rabbits/cd2369cc7c72bfad0fcd83e27682095...

Re: All elementary functions from a single binary operator

#186

Post by tgtweak »

tgtweak wrote: post #181
tgtweak wrote: post #175

This could have some interesting hardware implications as well - it suggests that a large dedicated silicon instruction set could accelerate any mathematical algorithm provided it can be mapped to this primitive. It also suggests a compiler/translation layer should be possible as well as some novel visualization methods for functions and methods.

This paper seems to suggest that a chip with 10 pipeline stages of EML units could evaluate any elementary function (table 4) in a single pass. I'm curious how this would compare to the dedicated sse or xmx instructions currently inside most processor's instruction sets. Lastly, you could also create 5-depth or 6-depth EML tree in hardware (fpga most likely) and use it in lieu of the rust implementation to discover w…

You could also make an analog EML circuit in theory, using electrical primitives that have been around since the 60s. You could build a simple EML evaluator on a breadboard. Things like trig functions would be hard to reproduce, but you could technically evaluate output in electrical realtime (the time it takes the electrical signal to travel though these 8-10 analog amplifier stages).

Re: All elementary functions from a single binary operator

#187

Post by wasabi991011 »

danbruc wrote: post #183
ikrima wrote: post #46

Earlier quoted context omitted.

From my experience of working in this problem domain for the last year, I'd say it is pretty powerful but the "too good to be true part" comes from that EML buys elegance through exponential expression blow-up. Multiplication alone requires depth-8 trees with 41+ leaves i.e. minimal operator vocabulary trades off against expression length. There's likely an information-theoretic sweet spot between these extremes. It'…

Where do you see exponential blow-up? If you replace every function in an expression tree with a tree of eml functions, that is a size increase by a constant factor. And the factor does not seem unreasonable but in the range 10 to 100.

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.

Re: All elementary functions from a single binary operator

#188

Post by xpe »

noobermin wrote: post #163
xpe wrote: post #41

Earlier quoted context omitted.

> but there's a reason that all approximations are done using series of polynomials (taylor expansion). "All" is a tall claim. Have a look at https://perso.ens-lyon.fr/jean-michel.muller/FP5.pdf for example. Jump to slide 18: > Forget about Taylor series > Taylor series are local best approximations: they cannot compete on a whole interval. There is no need to worry about "sh-tt-ng" on their result when there is so m…

Sorry, re-reading this, I should have said "most". As the other reply mentions, Pade approx. are also well liked for numerical methods. I personally mostly do my everyday work using taylor expansion (mostly explicit numerical methods in comp. EM because they're cheaper these days and it's simpler to write down) so it's what first comes to mind.

A quick meta-take here: it is hard to assess the level of expertise here on HN. Some might be just tangentially interested, other might have degrees in the specific topic. Others might maintain a scientific computing library. Domains vary too: embedded systems, robotics, spacecraft navigation, materials modeling, or physics simulation. Until/unless people step up and fill the gaps somehow, we have little notion of identity nor credentialing, for better and for worse.*

So it really helps when people explain (1) their context** and (2) their reasoning. Communicating well is harder than people think. Many comments are read by hundreds or more (thousands?) of people, most of whom probably have no idea who we are, what we know, or what we do with our brains on a regular basis. It is generous and considerate to other people to slow down and really explain where we're coming from.

So, when I read "most people use Taylor approximations"...

1. my first question is "on what basis can someone say this?"

2. for what domains might this somewhat true? False?

3. but the bigger problem is that claims like the above don't teach. i.e. When do Taylor series methods fall short? Why? When are the other approaches more useful?

Here's my quick take... Taylor expansions tends to work well when you are close to the expansion point and the function is analytic. Taylor expansions work less well when these assumptions don't hold. More broadly they don't tend to give uniform accuracy across a range. So Taylor approximations are usually only local. Other methods (Padé, minimax, etc) are worth reaching for when other constraints matter.

* I think this is a huge area we're going to need to work on in the age where anyone can sound like an expert.

** In the case above, does "comp. EM" mean "computational electromagnetics" or something else? The paper talks about "EML" so it makes me wonder if "EM" is a typo. All of these ambiguities add up and make it hard for people to understand each other.

Re: All elementary functions from a single binary operator

#189

Post by Sharlin »

mah4k4l wrote: post #153
Sharlin wrote: post #150

Earlier quoted context omitted.

Congrats, you made a hallucination machine successfully hallucinate?

I understand enough for it's arguments' symmetry to have an impact. Used Deep Research, it had the paper from the link as input plus some previous discussions about Tensor Logic and the new hardcoded neuroweb - like processors. Didn't make those up either.

I hope you get help. Mental health issues are not fun.

Re: All elementary functions from a single binary operator

#190

Post by jmyeet »

DoctorOetker wrote: post #30

EDIT: please change the article link to the most recent version (as of now still v2), it is currently pointing to the v1 version which misses the figures. I'm still reading this, but if this checks out, this is one of the most significant discoveries in years. Why use splines or polynomials or haphazardly chosen basis functions if you can just fit (gradient descent) your data or wave functions to the proper computati…

This isn't all that significant to anyone who has done Calculus 2 and knows about Taylor's Series.

All this really says is that the Taylor's expansions of e^x and ln x are sufficient to express to express trig functions, which is trivially true from Euler's formula as long as you're in the complex domain.

Arithmetic operations follow from the fact that e^x and ln x are inverses, in particular that e^ln(x) = x.

Taylor's series seem a bit like magic when you first see them but then you get to Real Analysis and find out there are whole classes of functions that they can't express.

This paper is interesting but it's not revolutionary.

Post reply on HN