Alternative quaternion multiplication method

627 Views Asked by At

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.

2

There are 2 best solutions below

1
On BEST ANSWER

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.

0
On

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.