Bitwise-operators?

[karttu]

Bitwise-operators XOR, OR, AND would very useful for the myriad of crazy binary sequences in OEIS, including also some operations in the polynomial ring GF(2)[X], see e.g. https://oeis.org/A048720 see also https://en.wikipedia.org/wiki/CLMUL_instruction_set ) (Or if we were minimalist purists, then just NAND would suffice, hah!?) Of course, the set of built-in primitives greatly affects to which particular directions or subsets of sequences Lodaminer will home to.

[ckrause]

This certainly makes sense. The set of operations does not need to be minimal or puristic. At the same time, we should restrict it to a meaningful set of common operations. Which ones would you propose exactly? Would they be undefined for negative integers?

[karttu]

XOR, OR, AND are used in the most CPU-architectures, so they should suffice for LODA as well. As what comes to the negative arguments, the common strategy is to interpret integer-arguments in 2's complement. Do I guess right that LODA tries to implement arbitrarily large integers (bignums?) so that wouldn't then work? I don't know whether there's any correct way to extend bitwise operators to the negative realm. See https://oeis.org/A163617 for some guidance, perhaps. (Sorry, writing this in haste, my train comes soon...)

[ckrause]

We currently use 64-bit signed integers but conceptually we want to support arbitrarily large integers. For that reason, I would leave the binary operations undefined (NUM_INF) for negative values.

TODOs for the implementation:

• [ ] Extend the Operation::Type enum: https://github.com/ckrause/loda/blob/master/src/include/program.hpp#L56-L77
• [ ] Extend the Operation::Types array: https://github.com/ckrause/loda/blob/master/src/program.cpp#L5 and header
• [ ] Provide operation metadata in https://github.com/ckrause/loda/blob/master/src/program.cpp#L11
• [ ] Implement the operations in semantics.hpp and semantics.cpp
• [ ] Add operations to switch in interpreter: https://github.com/ckrause/loda/blob/master/src/interpreter.cpp#L52
• [ ] Add CSV for semantics tests: https://github.com/ckrause/loda/tree/master/tests/semantics
• [ ] Add documentation to table in README.md

Optional:

• [ ] Check if the optimizer can be extended, e.g. and $x,$x is a no-op

[ckrause]

I'm having second thoughts about this. The original goal was to provide number-theoretic primitives that do not rely on a particular format (encoding) of numbers.

[karttu]

Second thoughts about bitwise-operators or about something else? (Negative values?) In the 64-bit (or any fixed-length) implementation, I would let AND, OR, XOR work as they natively do (which by A.D. 2021 is the same 2's complement interpretation of negative integers in all CPU-architectures, as far as I know). In bignum-implementation, where I guess the sign-bit is always separately stored in the data-structure (or so I guess, please correct me anybody if you know!), we could do anything we want with that bit, even if it is not "naturally" part of operations like AND, OR, NOT. For example, if there were instruction MULZ2X, i.e., carryless multiplication in base-2 (See https://oeis.org/A048720 and https://en.wikipedia.org/wiki/CLMUL_instruction_set ), then it could be programmed to act with signed arguments just the same way as the ordinary MUL-instruction: negative times positive is negative, and negative times negative is positive. (It would be interesting to know how CLMUL in Intel-architecture works in that respect). However, it should be checked how these kinds of solutions would mathematically agree with some other assumptions, when thinking about the way A048720 is computed with XOR's and SHIFT's.

[ckrause]

I guess my main concern is that binary operators are very machine-oriented operations for "real" assembler. LODA is targeting number-theoretical problems, where the number encoding and binary operations should play only a marginal role. The other point for me is: if we include base-2 operations, you could argue in the same way for base-3, base-4, ..., base-10, base-16 etc. There are plenty of such sequences in OEIS, but I've seen LODA being able to generate programs for many of them. For example A053735: Sum of digits of (n written in base 3): https://github.com/ckrause/loda/blob/master/programs/oeis/053/A053735.asm

[karttu]

But please note that base-2 is very important, not only for all the one-dimensional cellular automata (mostly known from S. Wolfram's work) as they are essentially various combinations of these operators, see e.g., https://oeis.org/A269160 and https://oeis.org/A269174 and https://oeis.org/A001317 for example), but also in more traditional number theory: both Mersenne primes (A000668) and Fermat primes (A019434) are primes with a "funny binary pattern". Note that base-3 is also important, but not even half as important as base-2!

[neoneye]

In https://oeis.org/A047999 there is a great example of how to eliminating the binomial mod 2. The formula is (n-k) & k. I'm in the process of making a A047999 program for LODA.

def binomial_mod2(n, k)
    # https://oeis.org/A047999
    v = (n-k) & k
    if v == 0
        return 1
    else
        return 0
    end
end

Same as binomial(n, k) % 2 which may waste cpu cycles.

[ckrause]

@karttu @neoneye : I'm fine with adding and, or, xor. Shall I go ahead with this?

[neoneye]

Today I have implemented A269160, A269174, A001317 without using and, or, xor. It wasn't easy, but not impossible. I think bitwise operations will be handy.

[karttu]

@neoneye Can you show them (the code)? I assume it is neither easy for the miner to come up with that kind of code? In any case, I'm for the bitwise-operators.

[ckrause]

@karttu This was the commit: https://github.com/ckrause/loda/pull/109/files ; The miner also recently generated a few new programs based on these ones. They will be included in the next commit.

[ckrause]

If this is still needed, please open a new issue in https://github.com/loda-lang/loda-lang