Live data from Hacker News

All elementary functions from a single binary operator

arxiv.org

21–30 of 317 posts

Re: All elementary functions from a single binary operator

#21
For completeness, there is also Peirce’s arrow aka NOR operation which is functionally complete. Fun applications iirc VMProtect copy protection system has an internal VM based on NOR.

Quick google seach brings up https://github.com/pr701/nor_vm_core, which has a basic idea

Re: All elementary functions from a single binary operator

#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 the number.
I use something not too far off for my daily a programming based on a similar idea:

Rejoice is a concatenative programming language in which data is encoded as multisets that compose by multiplication. Think Fractran, without the rule-searching, or Forth without a stack.

https://wiki.xxiivv.com/site/rejoice

Re: All elementary functions from a single binary operator

#23

> For example, exp(x)=eml(x,1), ln(x)=eml(1,eml(eml(1,x),1)), and likewise for all other operations I read the paper. Is there a table covering all other math operations translated to eml(x,y) form?

last page of the PDF has several tree's that represent a few common math functions.

Re: All elementary functions from a single binary operator

#24
post #11

How would an architecture with a highly-optimized hardware implementation of EML compare with a traditional math coprocessor?

Dreadfully slow for integer math but probably some similar performance to something like a CORDIC for specific operations. If you can build an FPU that does exp() and ln() really fast, it's simple binary tree traversal to find the solution.

You already have an FPU that approximates exp() and ln() really fast, because floatinteger conversions approximate the power 2 functions respectively. Doing it accurately runs face-first into the tablemaker's dilemma, but you could do this with just 2 conversions, 2 FMAs (for power adjustments), and a subtraction per. A lot of cases would be even faster. Whether that's worth it will be situational.

Re: All elementary functions from a single binary operator

#25

> eml(x,y)=exp(x)-ln(y) Exp and ln, isn't the operation its own inverse depending on the parameter? What a neat find.

> isn't the operation its own inverse depending on the parameter?

This is a function from ℝ² to ℝ. It can't be its own inverse; what would that mean?

Re: All elementary functions from a single binary operator

#27

> For example, exp(x)=eml(x,1), ln(x)=eml(1,eml(eml(1,x),1)), and likewise for all other operations I read the paper. Is there a table covering all other math operations translated to eml(x,y) form?

I was curious about that too. Gemini actually gave a decent list. Trig functions come from Euler's identity:

    e^ix = cos x + i sin x
which means:

    e^-ix = cos -x + i sin -x
          = cos x - i sin x
so adding them together:

   e^ix + e^-ix = 2 cos x
   cos x = (e*ix - e^-ix) / 2
So I guess the real part of that.

Multiplication, division, addition and subtraction are all straightforward. So are hyperbolic trig functions. All other trig functions can be derived as per above.

Re: All elementary functions from a single binary operator

#28
post #9
post #5

So, like brainf*ck (the esoteric programming language), but for maths?

But even tighter. With eml and 1 you could encode a funtion in rpn as bits. Although you also need to encode where to put the input. The real question is what emoji to use for eml when written out.

So brainf*ck in binary?

I'm kidding, of course. You can encode anything in bits this way.

Re: All elementary functions from a single binary operator

#29
post #18

How does one actually add with this?

Don't know adding, but multiplication has diagram on the last page of the PDF. xy = eml(eml(1, eml(eml(eml(eml(1, eml(eml(1, eml(1, x)), 1)), eml(1, eml(eml(1, eml(y, 1)), 1))), 1), 1)), 1) From Table 4, I think addition is slightly more complicated?

x+y = ln(exp(x) * exp(y))

exp(a) = eml(a, 1) ln(a)=eml(1,eml(eml(1,a),1))

Plugging those in is an excercise to the reader

Re: All elementary functions from a single binary operator

#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 computational EML tree?

Got a multidimensional and multivariate function to model (with random samples or a full map)? Just do gradient descent and convert it to approximant EML trees.

Perform gradient descent on EML function tree "phi" so that the derivatives in the Schroedinger equation match.

But as I said, still reading, this sounds too good to be true, but I have witnessed such things before :)

Post reply on HN