14
\$\begingroup\$

Very related, except does some binary stuff, and it allows for more than one dimension per number.

Also related, but restricted to quaternions and also allows more than one dimension per number.

In this challenge, you will be given two numbers with magnitude 1, all positive coefficients and only a single dimension from the Cayley-Dickson algebras (i.e. the direct limit of the Cayley-Dickson construction), and you must return the product of the two numbers. The order of the numbers is important, or otherwise your result may have the wrong sign.

In other words, you receive two numbers both in the form \$e_x\$ where \$x \ge 0\$ and \$x\$ is an integer, and you must output the product.

The Cayley-Dickson algebras are algebras recursively constructed from the real numbers in a particular way. Given an algebra of dimensionality \$2^n\$ (n being a non-negative integer), it constructs an algebra of dimensionality \$2^{n+1}\$ by combining two numbers of the previous dimensionality (e.g. complex numbers (dimension \$2^1 = 2\$) can be represented as the combination of two real numbers (dimension \$2^0 = 1\$), and quaternions (dimension \$2^2 = 4\$) as the combination of two complex numbers (dimension \$2^1 = 2\$).)

$$3+5i=(3,5)$$ $$3+5i+2j+7k=(3+5i,2+7i)=((3,5),(2,7))$$

Note that dimensional components are usually represented as \$e_x\$, \$x\$ being a non-negative integer. $$e_0=1$$ $$e_1=i$$ $$e_2=j$$ $$e_3=k$$ etc.

Firstly, in the Cayley-Dickson construction, the conjugate of a number \$(a,b)^*\$ is \$(a^*,-b)\$, and the conjugate of a real number is just itself. In other words, the conjugate of a number is where every dimension is negated apart from the real dimension.

Multiplication is given by the formula: $$(a,b)\times(c,d)=(ac-d^*b,da+bc^*)$$ Where * represents conjugation as previously defined.

Any reasonable representation of the two numbers are allowed, as long as the representation supports ordering.

Test cases (up to 16 dimensions)

Note that your program must theoretically work for all higher dimensions if your language’s number type supported infinite precision, infinite size integers, and no limits on e.g. recursion. Sedenion multiplication table

Example

Input 1: \$e_2\$

Input 2: \$e_{10}\$

Output: \$-e_8\$

This is , so shortest answer wins!

Improve this question
\$\endgroup\$
2
  • 1
    \$\begingroup\$ @JonathanAllan yes correct. You can also say just a single \$e\$ number. \$\endgroup\$ Commented Apr 3 at 17:30
  • 1
    \$\begingroup\$ @JonathanAllan Remember the cases of \$e_0\$ and \$-e_0\$ \$\endgroup\$ Commented Apr 3 at 17:32

5 Answers 5

Reset to default
8
\$\begingroup\$

Python, 86 73 bytes

(−1 from Arnauld, −12 from Jonathan Allan)

m=lambda i,j:(k:=i^j,0**i or i&~(l:=k|-k)and-m(i&l|k+l,1)[1]or m(j,k)[1])

Attempt This Online!

For inputs 2, 10 representing \$e_2, e_{10}\$, returns (8, -1) representing \$-e_{8}\$.

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I believe k^-l is k+l in this context. \$\endgroup\$ Commented Apr 4 at 8:05
  • \$\begingroup\$ @Albert.Lang it says -l, not -1. \$\endgroup\$ Commented Apr 4 at 10:21
  • 2
    \$\begingroup\$ -(-1)**int(f"{i&l|k^-l:b}",3) -> -m(i&l|k+l,1)[1] saves 13 (including one byte save from Arnauld's k+l) - ATO \$\endgroup\$ Commented Apr 5 at 22:19
  • \$\begingroup\$ 0**i or can be i<1or, I think. \$\endgroup\$ Commented Apr 6 at 18:23
4
\$\begingroup\$

JavaScript (ES6), 61 bytes

Port of Anders Kaseorg's excellent answer, with -14 bytes from a simplification suggested by Jonathan Allan on said answer.

Expects (i, j) and returns [k, ±1].

f=(i,j)=>[x=i^j,i?i&j&~(k=-x|x)?-f(i&k|x+k,1)[1]:f(j,x)[1]:1]

Try it online!

Commented

f = (i, j) =>       // f is a recursive function taking (i, j)
[                   //
  x = i ^ j,        // x = i XOR j -> this is the absolute value of the result
  i ?               // if i is not 0:
    i & j &         //   if there's at least one common bit between i, j and ~k
    ~(k = -x | x) ? //   where k = -LSB(x) (so ~k is LSB(x)-1, which gives a
                    //   mask of lower bits below the LSB of x):
      -f(           //     do a recursive call with:
        i & k |     //       - i set to the common bits between i and k
        x + k,      //         merged with x without its LSB
        1           //       - j set to 1
      )[1]          //     take the sign and invert it
    :               //   else:
      f(j, x)[1]    //     do a recursive call with (j, x) and take the sign
  :                 // else:
    1               //   stop and return 1
]                   //
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 94 58 bytes

ＮθＮηＩ⁻｜θη＆θη≔⁰ζＷ��«≔¹εＷ‹εη≦⊗εＦΣ⍘÷θε²≦¬ζ≔⊘﹪⊗θεε≔ηθ≔εη¿η≦¬ζ»ζ

Try it online! Link is to verbose version of code. Outputs the coefficient of the result, followed by a - if the result should be negative. Explanation: I don't claim to understand @AndersKaesorg's bit twiddling, so this implements my own formula.

ＮθＮη

Input the two coefficients.

Ｉ⁻｜θη＆θη

Output the result's coefficient.

≔⁰ζ

Start with a positive sign, using false (0) for positive and true (1) for negative.

Ｗη«

Repeat until the second coefficient is zero.

≔¹εＷ‹εη≦⊗ε

Find the smallest power of two not less than the second coefficient. (The interesting bit is actually the previous bit, but this is easier to calculate with.)

ＦΣ⍘÷θε²≦¬ζ

Masking out the interesting and lower bits of the first coefficient, toggle the sign if there are an odd number of 1 bits remaining.

≔⊘﹪⊗θεε

Mask out the interesting and higher bits of the first coefficient. Note that we never used the interesting bit; that's what's so interesting about it!

≔ηθ≔εη

Swap the coefficients.

¿η≦¬ζ

If we haven't finished, toggle the sign again.

»ζ

Output the final sign. Conveniently Charcoal's default boolean output format is - for true and nothing for false.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ So it basically turns out that the imaginary unit can be determined by a bitwise xor of the two input values, and it’s the sign that takes more code. \$\endgroup\$ Commented Apr 4 at 15:55
  • \$\begingroup\$ I've since come up with a new formula that takes less more code than before - it's actually now golfier than porting @JonathanAllan's answer (unless you use my experimental Zip branch of Charcoal, which cuts the byte count down from 60 to 56). \$\endgroup\$ Commented Apr 5 at 6:08
2
\$\begingroup\$

R, 122 bytes

f=\(i,j,`~`=bitwAnd,`?`=bitwOr,N=bitwNot)c(k<-bitwXor(i,j),`if`(!i,1,`if`(i~N(l<-(k?N(k-1))),-f(i~l?k+l,1)[2],f(j,k)[2])))

Attempt This Online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly,  33  31 bytes

N,ZN1¦€€;"/;@;"Z$
’^/‘WWÇṀ}¡œị@

A monadic Link that accepts a pair of imaginary units as their positive, 1-indexed dimension, and yields the resulting imaginary unit, in the same notation but signed.

i.e.:

  • inputs: \$e_0 = 1, e_1 = 2, \cdots\$
  • outputs: inputs and \$-e_0 = -1, -e_1 = -2, \cdots\$.

Try it online! Or see the test-suite.
For a larger table, see this faster version that avoids building an unnecessarily huge table.

How?

Build a signed value table by repeatedly doubling its size, starting with [[D]], where D is the unsigned result (a simple XOR after dealing with 1-indexing), then index into the result.

N,ZN1¦€€;"/;@;"Z$ - Helper Link (double table size): table of +/-D, T
N                 - negate {T}
  Z               - transpose {T}
 ,                - pair those -> [-T, T']
   N1¦€€          - negate first element of each of each
        ;"/       - place the altered T' to the right of the altered -T
                     -> bottom half of new table
             ;"Z$ - place T' to the right of T
                     -> top half of new table
           ;@     - concatenate these -> new table

’^/‘WWÇṀ}¡œị@ - Main Link: pair of positive integers, [i, j]
’^/‘          - ((i - 1) XOR (j - 1)) + 1
                 -> D = the dimension
    WW        - wrap {D} twice -> Table = [[D]]
         ¡    - repeat...
       Ṁ}     - ...times?: maximum of i and j
      Ç       - ...action: call the helper link (double the size of Table)
          œị@ - {[i,j]} 1-index into {Table}
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.