9
\$\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 yesterday
  • 1
    \$\begingroup\$ @JonathanAllan Remember the cases of \$e_0\$ and \$-e_0\$ \$\endgroup\$ Commented yesterday

3 Answers 3

Reset to default
5
\$\begingroup\$

Python, 86 bytes

m=lambda i,j:(k:=i^j,0**i or i&~(l:=k|-k)and-(-1)**int(f"{i&l|k^-l:b}",3)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
  • \$\begingroup\$ I believe k^-l is k+l in this context. \$\endgroup\$ Commented 10 hours ago
  • \$\begingroup\$ @Arnauld isn't k^-1 ~k regardless of context? \$\endgroup\$ Commented 8 hours ago
  • \$\begingroup\$ @Albert.Lang it says -l, not -1. \$\endgroup\$ Commented 8 hours ago
  • \$\begingroup\$ @TheEmptyStringPhotographer Oops, silly me. \$\endgroup\$ Commented 7 hours ago
2
\$\begingroup\$

JavaScript (ES6), 75 bytes

Port of Anders Kaseorg's excellent answer.

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

f=(i,j)=>[x=i^j,i?i&j&~(k=-x|x)?-(h=n=>!n||-h(n&n-1))(i&k|x+k):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):
      -(h = n =>      //     h is a helper recursive function counting the number
        !n ||         //     of bits set in n and returning 1 if it's even or -1
        -h(n & n - 1) //     if it's odd
      )(              //     apply h to:
        i & k |       //       the common bits between i and k
        x + k         //       merged with x without its LSB
      )               //     (and invert the sign once more)
    :                 //   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\$
0
\$\begingroup\$

Charcoal, 94 bytes

ＮθＮη≔⁰ζ≔⁰δ≔⁰ε≔¹φＷ‹⁺δε⁺θη«≧⁺＆θφδ≧⁺＆ηφε≔∧δ∧ε∨⁼δε∨⁼⁺φδε∨∧＆θφ⁼εφ∧⁻εφ∧∧＆ηφ⁻δφ⁼¬＆｜θηφζζ≦⊗φ»ζＩ⁻｜θη＆θη

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

ＮθＮη

Input the two coefficients.

≔⁰ζ≔⁰δ≔⁰ε≔¹φ

Start with no bits of the coefficients yet, a positive sign, using false (0) for positive and true (1) for negative, and work from the least significant bit to the most significant.

Ｗ‹⁺δε⁺θη«

Repeat until all of the bits of the coefficients have been processed.

≧⁺＆θφδ≧⁺＆ηφε

Get the next bits of each coefficient.

≔∧δ∧ε∨⁼δε∨⁼⁺φδε∨∧＆θφ⁼εφ∧⁻εφ∧∧＆ηφ⁻δφ⁼¬＆｜θηφζζ

Update the resulting sign.

≦⊗φ

Prepare to get the next bit on the next pass though the loop.

»ζ

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

Ｉ⁻｜θη＆θη

Output the result's coefficient.

The logic to update the sign is as follows:

  • If either coefficient has no set bits so far, set the sign to false (positive).
  • Otherwise, if the bits so far are equal in both coefficients, set the sign to true (negative).
  • Otherwise, if the bits only differ in the latest bit being set only in the second coefficient, set the sign to true (negative).
  • Otherwise, if the first coefficient's latest bit is set and the second coefficient just got its first set bit, set the sign to true (negative).
  • Otherwise, if the second coefficient just got its first set bit, set the sign to false (positive).
  • Otherwise, if the second coefficient's latest bit is set and the first coefficient just got its first set bit, set the sign to false (positive).
  • Otherwise, if either coefficient's latest bit is set, toggle the sign.
Improve this answer
\$\endgroup\$
1
  • \$\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 2 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.