7

Given two quaternions, $a+bi+cj+dk$ and $e+fi+gj+hk$, their product (w.r.t. their given order) would normally be given by $Q_1+Q_2i+Q_3j+Q_4k=(ae-bf-cg-dh)+(af+be+ch-dg)i+(ag-bh+ce+df)j+(ah+bg-cf+de)k$. This takes a total of $16$ real multiplications and $12$ real additions to accomplish.

I'm looking to reduce the number of multiplications. Here's what I have so far.

$P_1=(c+d)(g+h)$, $P_2=(a+b)(e+f)$, $P_3=(c+d)(e+f)$, $P_4=(a+b)(g+h)$, $Q_1=(ae+dg)+(ch-bf)-P_1$, $Q_2=P_2+(ch-bf)-(ae+dg)$, $Q_3=P_3+(ag-de)-(bh+cf)$, $Q_4=P_4-(ag-de)-(bh+cf)$.

As far as I can tell, this requires 12 real multiplications and 16 real additions, assuming certain quantities are reused.

Are there any well-known methods for doing this using less real multiplications, or any obvious simplifications that I could make to my formulas?

EDIT: You can calculate $(R_1,R_2)=(ae+dg,ag-de)$ and $(R_3,R_4)=(cf+bh,ch-bf)$ by this method: $S_1=(a+d)(e+g)$, $S_2=(c+b)(f+h)$, $(R_1,R_2)=(S_1-ag-de,ag-de)$, $(R_3,R_4)=(S_2-ch-bf, ch-bf)$. This brings the total number of real multiplications down to 10, and the real additions up to 22.

Benjamin Roycraft
  • 464
  • 2
    Identifying quaternions as a two-by-two matrices with complex entries, via $$a+bi+cj+dk\mapsto\left(\begin{array}{cc}a+bI&c+dI\-c+dI&a-bI\end{array}\right),$$ where $I=\sqrt{-1}$, makes life easier at the multiplication time. – janmarqz Jan 14 '15 at 00:16
  • 4
    It's convenient notationally, but does it offer any insight towards an efficient algorithm? – Benjamin Roycraft Jan 14 '15 at 00:24
  • 1
    Multiplying matrices is pretty agile. Instead of three imaginary units only you need one. – janmarqz Jan 14 '15 at 00:37
  • 2
    The least amount of real mults that I know of to do a complex multiplication is 3. A matrix multiplication of this kind, without any simplification, would then require 24 real mults. – Benjamin Roycraft Jan 14 '15 at 00:42

2 Answers2

8

There's an algorithm here that uses eight multiplications, as long as you don't count multiplications by $2$ and by $-1$. This paper also mentions a proof that it can't be done with less than seven. Here is a review of an article which shows it can't be done with less than ten multiplications if you count multiplying by fixed constants, and gives such an algorithm, but I can't see the paper (due to paywalls I don't know if either of these links will work.)

The algorithm in the first paper is as follows: $(a_0+a_1i+a_2j+a_3k)(b_0+b_1i+b_2j+b_3k)=c_0+c_1 i+c_2j+c_3k$, where $$\begin{pmatrix} -c_0&c_1&c_2&c_3\end{pmatrix}=1/4\begin{pmatrix} n_0p_0&n_1p_1&n_2p_2&n_3p_3\end{pmatrix} A-2\begin{pmatrix} a_0b_0&a_3b_2&a_2b_1&a_1b_3\end{pmatrix} $$ $$A=\begin{pmatrix} 1&1&1&1\\ 1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{pmatrix}$$ $$\begin{pmatrix} n_0&n_1&n_2&n_3\end{pmatrix}=\begin{pmatrix} a_0&a_1&a_2&a_3\end{pmatrix} A$$$$\begin{pmatrix} p_0&p_1&p_2&p_3\end{pmatrix}=\begin{pmatrix} b_0&b_1&b_2&b_3\end{pmatrix}A$$ So the only "real" multiplications being down are between $n$s and $p$s and between $a$s and $b$s in the final formula.

Community
  • 1
Kevin Carlson
  • 52,457
  • 4
  • 59
  • 113
  • 4
    Well, the multiplication by 2 and division by 4 can be accomplished via bitshift, so those wouldn't count as true mults. This has an awful lot of additions to get the mults down, though. – Benjamin Roycraft Jan 14 '15 at 00:38
1

One method from the internetz

$$ \begin{align} A_1 & = (d + b) * (f + g) \\ A_3 &= (a - c) * (e + h) \\ A_4 &= (a + c) * (e - h) \\ A_2 &= A_1 + A_3 + A_4 \\ A_5 &= 0.5 * (A_2 + (d - b) * (f - g)) \\ \\ Q_1 &= A_5 - A_1 + (d - c) * (g - h)\\ Q_2 &= A_5 - A_2 + (b + a) * (f + e)\\ Q_3 &= A_5 - A_3 + (a - b) * (g + h)\\ Q_4 &= A_5 - A_4 + (d + c) * (e - f)\\ \end{align} $$

9 multiplications highlighted with "*" (including one divide-by-2)

checked, seems to work OK.

Joffan
  • 39,627