Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows: $$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$ We only need the products $ac$, $bd$ and $(a+b)(c+d)$. Does there exists a similar trick for quaternion multiplication? A naive multiplication would need $16$. This can probably be reduce to $9$ using the same trick as above (and taking into account that quaternion multiplication is non-commutative). My question is it known that $9$ is the lower bound? If not, does there exist an algorithm, which does quaternion multiplications in less than $9$ real multiplications?
8
-
3$\begingroup$ Duplicate of math.stackexchange.com/questions/1222820/… $\endgroup$– Igor RivinCommented Apr 24, 2015 at 2:24
-
1$\begingroup$ Indeed, word-for-word duplicate. 17762, you ought to have included a link to the other question at each site. But I do note that no answers were given at the other site. $\endgroup$– Gerry MyersonCommented Apr 24, 2015 at 2:32
-
2$\begingroup$ ...though an apparently useful comment was given by a certain Gerry Myerson... $\endgroup$– Noam D. ElkiesCommented Apr 24, 2015 at 3:11
-
1$\begingroup$ theworld.com/~sweetser/quaternions/ps/cornellcstr75-245.pdf claims magic number $8$. $\endgroup$– TurboCommented Apr 24, 2015 at 4:19
-
4$\begingroup$ Also cross-posted to Theoretical Computer Science: cstheory.stackexchange.com/q/31251/8067 $\endgroup$– Zsbán AmbrusCommented Apr 24, 2015 at 5:26
|
Show 3 more comments