I stumbled on a Twitter account yesterday called Wolfram|Alpha Can’t. It posts bizarre queries that Wolfram Alpha can’t answer. Here’s one that caught my eye.
result of extracting the i’s, j’s, and k’s in order from Finnegans Wake and interpreting as a quaternion product
— Wolfram|Alpha Can’t (@wacnt) May 17, 2017
Suppose you did extract all the i‘s, j‘s, and k‘s from James Joyce’s novel Finnegans Wake. How would you answer the question above?
You could initialize an accumulator to 1 and then march through the list, updating the accumulator by multiplying it by the next element. But is there a more efficient way?
Quaternion multiplication is not commutative, i.e. the order in which you multiply things matters. So it would not be enough to have a count of how many times each letter appears. Is there any sort of useful summary of the data short of carrying out the whole multiplication? In other words, could you scan the list while doing something other than quaternion multiplication, something faster to compute? Something analogous to sufficient statistics.
We’re carrying out multiplications in the group Q of unit quaternions, a group with eight elements: ±1, ±i, ±j, ±k. But the input to the question about Finnegans Wake only involves three of these elements. Could that be exploited for some slight efficiency?
How would you best implement quaternion multiplication? Of course the answer depends on your environment and what you mean by “best.”
Note that we don’t actually need to implement quaternion multiplication in general, though that would be sufficient. All we really need is multiplication in the group Q.
You could implement multiplication by a table lookup. You could use an 8 × 3 table; the left side of our multiplication could be anything in Q, but the right side can only be i, j, or k. You could represent quaternions as a list of four numbers—coefficients of 1, i, j, and k—and write rules for multiplying these. You could also represent quaternions as real 4 × 4 matrices or as complex 2 × 2 matrices.
If you have an interesting solution, please share it in a comment below. It could be interesting by any one of several criteria: fast, short, cryptic, amusing, etc.
Update: See follow up post, Random walk on quaternions
Boring answer, but it seems that it is -j, solved via brute forced R script, a table lookup as you suggested, and the version of Finnegans wake found at “https://ia801302.us.archive.org/17/items/finneganswake00joycuoft/finneganswake00joycuoft_djvu.txt .
R script: https://pastebin.com/UAb5dynj
The result is limited to a sign bit and 1,i,j,k, so encode as a 3-bit number:
000 = 1, 001 = i, 010=j, 011=k, 100=-1, 101=-i, 110=-j, 111=-k
and just do a table lookup, it’ll be in cache anyway.
Well, cheating slightly by using Math::Quaternion to handle the math, and Hamlet[1] instead of the Joyce because Gutenberg doesn’t have the latter.
use v6;
use Math::Quaternion;
my %letter-to-quaternion = (
“i” => Math::Quaternion.new(0, 1, 0, 0),
“j” => Math::Quaternion.new(0, 0, 1, 0),
“k” => Math::Quaternion.new(0, 0, 0, 1)
);
say [*] $*IN.slurp.comb(/”i” | “j” | “k”/).map({ %letter-to-quaternion{$_} });
[1] http://www.gutenberg.org/cache/epub/1524/pg1524.txt
A tempting path is to exploit for efficiency is the fact that for any u,v in
{± i, ±j, ±k}, v!=u that u*v*u = v , so you could *almost* rub of any unit in pairs. The obstruction is that v*1*v = -1 and v*v*v = -v, so the stuff in the middle can’t be ±u or ±1. However if you only cared about the answer up to a sign then you only need to know how many i,j,k’s there are mod 2 to construct the answer.
I also got `-j`. I used a 2×2 complex matrix representation of quaternions:
https://gitlab.com/certik/ijk
Oh no, nerdsniped! I get `-j` with an unholy blend of Perl and Julia:
using Quaternions
i = Quaternion(0,1,0,0)
j = Quaternion(0,0,1,0)
k = Quaternion(0,0,0,1)
s = prod([eval(Symbol(x)) for x in readall(`perl -pe ‘s/[^ijk]//g’ fwake.txt`)])
I like the term “nerdsniped.” :) Hadn’t heard it until someone else said they’d been nerdsniped by one of my blog posts.
For the uninitiated :) https://xkcd.com/356/ and the slightly ironic https://www.explainxkcd.com/wiki/index.php/356:_Nerd_Sniping
nerdsniping seems closely related to Paul Erdos’ concept of a “mathematical disease”
I might be inclined to migrate all i’s to the left, sign-flipping each step (like pushing up your left sleeve), then migrating all k’s to the right (pushing up your right sleeve), leaving all j’s in the middle. The resulting expression is iii…n_left…iiijjj…n_middle…jjjkkk…n_right…kkk. Then compute i^{n_{left}}\ast{j^{n_{middle}}}\ast{k^{n_{right}}}, representing the exponents in base 2 and using efficient table of squares to compute the final answer.
Color me ignorant/boring, but it’s just a single switch statement =)
A string of any number of i, j and k can be reduced to a string of length at most 2 using the following string rewriting system:
iii=kj, iij=ik, iik=ji, iji=j, ijj=kj, ijk=ii, iki=k, ikj=, ikk=kj, jii=ik, jij=i, jik=, jji=kj, jjj=ik, jjk=ji, jki=ii, jkj=k, jkk=ik, kii=ji, kij=ii, kik=i, kji=, kjj=ji, kjk=j, kki=kj, kkj=ik, kkk=ji.
The rules giving ii can also use jj or kk.
I suppose one could compile a finite state machine that runs through the i’s, j’s, and k’s and computes a running product. One could even compute it in parallel thanks to associativity of the quaternion multiplication–useful if you replace Finnegans Wake with a much larger corpora.
Since the product is still associative, it seems stupidly easy to parallelize under MapReduce as well. Thanks, this was amusing!
⍝ 2 lines(for clarity ) of APL
prodM←↑ ‘1¯IJKijk’ ‘¯1ijkIJK’ ‘Ii¯Kj1kJ’ ‘Jjk¯IK1i’ ‘KkJi¯jI1’ ‘iI1kJ¯Kj’ ‘jJK1ik¯I’ ‘kKjI1Ji¯’
prodM{i p←⍺⍺ ⋄ p[⊂(1⌷p)⍳⍺ ⍵]}/’IJK’∩toUpper string
⍝ ¯ i j k are negatives of 1 I J K