Cayley-Dickson construction to multiply complex, quaternion, octonion and so forth

Difference between version 1 and 5 - Previous - Next

[GS] (20190504) The idea behind the Cayley-Dickson construction [https://en.wikipedia.org/wiki/Cayley%E2%80%93Dickson_construction] is that a complex number `a + ib` can be written as a pair of real numbers `(a,b)`.

Multiplication is done like this : 

 (a,b)(c,d) = (ac - db,ad + cb)

And the conjugate of a complex number is defined like this :

 (a,b)* = (a,-b)

Now a quaternion can be considered as a pair of complex numbers where multiplication is :

 (a,b)(c,d) = (ac - db*,a*d + cb)

And the conjugate of a quaternion is defined like this :

 (a,b)* = (a*,-b)

We can continue considering octonion to be a pair of quaternions.

So, Cayley-Dickson construction can be used to multiply complex number, quaternion, octonion, 
sedenion and so forth. Length of lists must be a power of 2.


======
# cayleydickson.tcl
# Author:      Gerard Sookahet
# Date:        04 mai 2019
# Version:     0.1
# Description: Cayley-Dickson construction to multiply complex number quaternion octonion

namespace path ::tcl::mathop

proc Conjugate x {
 set res [lmap i $x {- $i}]
 lreplace $res 0 0 [- [lindex $res 0]]
}

# Vector operation (add or substract)
proc Vec {op a b} {
 if {[llength $a] == 1 && [llength $b] == 1} {
   $op $a $b
 } else {
   lmap i $a j $b {Vec $op $i $j}
 }
}

proc CayleyDickson {x y} {
 set n [llength $x]
 if {$n == 1} {return [* $x $y]}
 set m [/ $n 2]
 set m1 [- $m 1]
 set a [lrange $x 0 $m1]
 set b [lrange $x $m end]
 set c [lrange $y 0 $m1]
 set d [lrange $y $m end]
 return [list {*}[Vec - [CayleyDickson $a $c] [CayleyDickson [Conjugate $d] $b]] \
              {*}[Vec + [CayleyDickson $d $a] [CayleyDickson $b [Conjugate $c]]]]
}

# Tests

# Multiply two real 2 and 3
CayleyDickson 2 3

# Multiply two complex numbers 3 + i2  and 1 + i7  => -11 + i23
CayleyDickson [list 3 2] [list 1 7]

# Multiply two quaternions 0 + i3 + 0 - k and 2 + 0 + j + k => 1 + i7 - j3 + k
CayleyDickson [list 0 3 0 -1] [list 2 0 1 1]
======
[FM] : get a try wiyh [TIP 759]
======
# CayleyDickson 
proc CD {x y} {(
    (n = [llength $x]) == 1 ? [ return [($x * $y)] ]:;
    m = $n/2;
    a = [lrange $x 0 $m-1]; b = [lrange $x $m end];
    c = [lrange $y 0 $m-1]; d = [lrange $y $m end];
    
    [return [list  {*}[Vec [CD $a $c] - [CD [Conjugate $d]        $b      ]] \
                   {*}[Vec [CD $d $a] + [CD       $b        [Conjugate $c]]]]]
)}

proc Vec {a op b} {
    if {[llength $a] == 1 && [llength $b] == 1} {
        switch -- $op \
            "+" ($a+$b)\
            "-" ($a-$b) \
            "*" ($a*$b)\
            "/" ($a/double($b))\
            "%" ($a%double($b))\
            "**" ($a**$b) \
            "," ($a,$b)
    } else {
        lmap i $a j $b {Vec $i $op $j}
    }
}

proc Conjugate {x} {
    lmap i $x {( [incr j] == 1 ? $i : -$i )}
}

CD [list 3 2] [list 1 7]
# -11 23
(bin) 79 % CD [list 0 3 0 -1] [list 2 0 1 1]
# 1 7 -3 1
======
That said, this generality would be a lot more slow than a direct computation with coordinates. <<br>> Comparing with "mult" proc you can find in [Quaternion] gives :
======
timerate {CD [list 0 3 0 -1] [list 2 0 1 1]}
# 69.3958 µs/# 14410 # 14410.1 #/sec 999.994 net-ms
timerate {mult [list 0 3 0 -1] [list 2 0 1 1]}
# 1.480530 µs/# 675433 # 675433 #/sec 999.999 net-ms
======
<<categories>> Mathematics