Intro
Second write-up here; this is something I just happened upon today while (super) bored at work. I’m not a math/algorithm nerd by any means, but I did find this pretty fascinating. This will walk you through what I found and how I moved forward with it.
If anyone knows of an official name for this algorithm, I’d be interested in knowing what it is. I highly doubt I discovered anything new or mind-blowing, but it was a personal discovery I felt was worth sharing.
Let’s begin!
Boredom [part 0]
I remember reading a Quora post (if I find it again, I’ll add it as a link) where a person asked “what does the graph of XOR look like?” and only got one reply, which shot the question down as being misinterpretive of what XOR does as a function. That answer bothered me, so today I decided to explore it on my own.
Boredom [part 1]:
The beginning
To start from the very beginning, for any newcomers unaware of how logical XOR works, here is the truth table for the function:
P | Q | P^Q
--+---+----
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
To put it in words, given two propositional variables, P and Q, the expression P XOR Q is true for either P OR Q but not P AND Q.
That’s all well and good, but what if we replace variables in the propositional expression with natural numbers? Just convert the number to binary, and run the function:
2 ^ 3 = ?
2 = 0b10
3 = 0b11
--------
^ = 0b01
2 ^ 3 = 1
The table
So that’s it; XORing two natural numbers will output a natural number. I wanted more, though. I thought back to my days of elementary school and how we were taught multiplication using times tables. Let’s make an “XORs table” with natural numbers (I stop at 15 to keep this down to using 4 bits):
| 0 1 2 3 4 5 6 7 8 9 A B C D E F
---+------------------------------------------------
0 | 0 1 2 3 4 5 6 7 8 9 A B C D E F
1 | 1 0 3 2 5 4 7 6 9 8 B A D C F E
2 | 2 3 0 1 6 7 4 5 A B 8 9 E F C D
3 | 3 2 1 0 7 6 5 4 B A 9 8 F E D C
4 | 4 5 6 7 0 1 2 3 C D E F 8 9 A B
5 | 5 4 7 6 1 0 3 2 D C F E 9 8 B A
6 | 6 7 4 5 2 3 0 1 E F C D A B 8 9
7 | 7 6 5 4 3 2 1 0 F E D C B A 9 8
8 | 8 9 A B C D E F 0 1 2 3 4 5 6 7
9 | 9 8 B A D C F E 1 0 3 2 5 4 7 6
A | A B 8 9 E F C D 2 3 0 1 6 7 4 5
B | B A 9 8 F E D C 3 2 1 0 7 6 5 4
C | C D E F 8 9 A B 4 5 6 7 0 1 2 3
D | D C F E 9 8 B A 5 4 7 6 1 0 3 2
E | E F C D A B 8 9 6 7 4 5 2 3 0 1
F | F E D C B A 9 8 7 6 5 4 3 2 1 0
When I first looked at this, I was once again bored. I kept staring at it though and realized it was symmetric. Not only that, but this table is symmetric over the line f(x) = x.
Boredom [part 2]:
Patterns and permutations and bears, oh my!
In case staring at a 16x16 table of characters doesn’t make the symmetry immediately obvious, let’s take another look:
| 0 1 2 3 4 5 6 7 8 9 A B C D E F
---+------+------+------------+------------------------
0 | 0 1 | 2 3 | 4 5 6 7 | 8 9 A B C D E F
1 | 1 0 | 3 2 | 5 4 7 6 | 9 8 B A D C F E
+------+ | |
2 | 2 3 0 1 | 6 7 4 5 | A B 8 9 E F C D
3 | 3 2 1 0 | 7 6 5 4 | B A 9 8 F E D C
+-------------+ |
4 | 4 5 6 7 0 1 2 3 | C D E F 8 9 A B
5 | 5 4 7 6 1 0 3 2 | D C F E 9 8 B A
6 | 6 7 4 5 2 3 0 1 | E F C D A B 8 9
7 | 7 6 5 4 3 2 1 0 | F E D C B A 9 8
+--------------------------+------------------------
8 | 8 9 A B C D E F 0 1 2 3 4 5 6 7
9 | 9 8 B A D C F E 1 0 3 2 5 4 7 6
A | A B 8 9 E F C D 2 3 0 1 6 7 4 5
B | B A 9 8 F E D C 3 2 1 0 7 6 5 4
C | C D E F 8 9 A B 4 5 6 7 0 1 2 3
D | D C F E 9 8 B A 5 4 7 6 1 0 3 2
E | E F C D A B 8 9 6 7 4 5 2 3 0 1
F | F E D C B A 9 8 7 6 5 4 3 2 1 0
Awesome! The numbers did … something! What does this mean? We start by looking at the 2x2 box in the top left corner. Think of that box as taking the two numbers on top as input, and producing the two numbers on bottom as output. In this case, you give it [0,1] and it outputs [1,0].
This is where things start to get interesting. Let’s make our scope bigger and jump out to a 4x4 box. Now the top of the box takes in two 2x2 boxes as its input, and then swaps the entire box. We can keep growing our scope and the block-swapping will perform the same operation, albeit on a larger input, every time. If you notice, the output of the final block-swap is an exact reverseal of the first input string.
Boredom [part 3]:
Application for string literals
“Gee, @fi6uh, this is hella boring,” you might say. No! This is where the lightbulb went off over my head. When given a string (adhering to some constraints we’ll get to in a minute), you can reverse it in a fixed number of steps.
The catch
Since XOR is a bitwise operator, its properties permeate through the this algorithm. One caveat to this algorithm is that the string must be of length 2^n (^ here is “raised to”, not XOR). This is easy enough to get around though, just pad the rest of the string up to the next power of 2. Let’s do an example; my username is only 5 characters, so I will pad it with 3 _'s in order to make it a power of 2:
input: fi6uh___
1st permutation: ifu6_h__
2nd permutation: u6if___h
3rd permutation: ___hu6if
The math
So the trick here is that for any string (padded to the next power of 2 if necessary) of length n, where n is 2 raised to some p in the natural numbers, it can be reversed in p permutations. Let’s demonstrate this with a longer string, of 16 characters. log2(16) = 4, so I should be able to reverse this string in 4 steps:
input: abcdefghijklmnop
1st permutation: badcfehgjilknmpo
2nd permutation: dcbahgfelkjiponm
3rd permutation: hgfedcbaponmlkji
4th permutation: ponmlkjihgfedcba
And we did it! Pretty cool. But can this be applied to a different structure? Definitely!
Boredom [part 4]:
The matrix
Ok so we’ve seen how this algorithm can reverse a string linearly, but it can be applied to a two dimensional “string” (er, matrix) as well. When applying this to a string, you can think of “pushing” the operations down. When we add a second dimension into the mix, you do the same thing, but “push” the operations right as well. Let’s demonstrate with an easy one:
a b
input: c d
b a
1st permutation (down): d c
d c
2nd permutation (right): b a
To explain this a bit more, when we push the operation down, we select an element and its neighbor to the right, in this case a and b, and swap them horizontally. Then, when we push the operation right, we select an element and its neighbor immediately below it, in this case b and d, and swap them vertically. With a 2x2 matrix, that’s all it takes!
A larger matrix
There’s a trick to this applying this algorithm in two directions, however. You have to keep track of how many permutations you have done for each direction before you can grow your scope. Notice for a 2x2, we did 2 permutations and selected 2 elements in the same scope for both permutations. This may be a little more obvious with a larger matrix, so let’s bump it up a notch:
a b c d
e f g h
i j k l
input: m n o p
b a d c
f e h g
j i l k
1st permutation (down): n m p o
f e h g
b a d c
n m p o
2nd permutation (right): j i l k
h g f e
d c b a
p o n m
3rd permutation (down): l k j i
p o n m
l k j i
h g f e
4th permutation (right): d c b a
You can see more clearly here that with 2 dimensions, you do 2 permutations for each direction before growing your scope. After following the algorithm, the matrix will be reflected over the bottom right corner (the “origin”, for the sake of this writing). For a string, which only reads left to right, you only need to do 1 permutation to grow your scope.
Conclusion:
LOL you thought you were done, but in the wise words of Leo:
Boredom [part n]:
The multiverse
The title for this topic uses the word “scalable” for a reason! We’ve seen a 1 dimensional permutation (string), we’ve seen a 2 dimensional permutation (matrix), what about 3 dimensions? Great question! The answer is: apply the 1 dimensional algorithm for every added dimension, then grow your scope and repeat. This means it should work for n-dimensional structures, but I don’t know how to draw permutations of things in those realms. That said, I also don’t know how to easily display permutations of a cube in ASCII, so instead I will draw a picture. Note: not an artist.
Here goes:
As you can see, simply following the algorithm for every direction results in a cube whose verteces have been reflected over the vertex 6 (in this case).
Conclusion:
Hopefully this journey through permutations, time, and space has been entertaining and not boring. I found that this personal discovery got me through lunch and made the rest of my work day exciting. If any of you are more familiar with these topics (or have a name for what I just described), please comment and share with the group.
As always, if you notice any errors please let me know so I can address them.
/end math
Addendum:
A detail was brought to my attention that I felt should be addressed:
If defining “fixed” as a constant for every input, this statement is incorrect. This algorithm has a logarithmic time complexity rather than a constant one.
It was also noted that this algorithm is similar in function to both the XOR swap algorithm and the Feistel cipher (though the name of the algorithm demonstrated here is still unknown to me). Both of which have been implemented numerous times, though I’m not sure if they “move” into higher dimensions.