0 or 1, that's a bit.

Provide yourself with a sequence of them, you have a set of (unsigned, binary) numbers. 00 01 10 11 are the numbers 0 1 2 3 in binary. You knew that already, too.

But there are amazing ramifications of this simple idea.

Storage

Parallel Communications

The point is, a bit in an address space picks out half the addresses, and establishes a correspondence between halves by swapping that bit's value. If you do that just \(m\) times you can send from anywhere to anywhere or from anywhere to everywhere.

To be extra clear, swapping a bit could be done in different contexts, with interesting ramifications.

• In the context of a single address, keeping all its other bits fixed, swapping a bit picks out a single corresponding address in the other half.
• In the context of all the addresses together, it picks out, for each, one other unique corresponding address which is in the other half from that of the first, and which corresponds to no other in the first half.
• In the context of all the addresses in just one half, it specifies not just 'the other' for every one, but all the \(2^m/2\) bidirectional correspondences between corresponding addresses.
• Finally in the abstract context of just considering the these dimensions or dimensionality in general, swapping one bit also amounts to identifying one dimension that is completely independent of all the others, which is to say that if you choose any dimension (any one of the bits), that amounts to choosing one of many ways of splitting up the address space in half, all being completely orthogonal, independent halves, each of which is itself half black half white; half of it is addressed by a one in that particular bits, and half is addressed by a zero in that bit. Every bit-split half is half one, half zero, for each other bit.

These are just different ways of looking at the same thing. None of these bullet points needed to be said, really, but a concrete minded person like myself might not see these ramifications, or be immediately comfortable with them, in hearing the mere word, "bits".

In particular, to send from everywhere to everywhere, some (any arbitrary) ordering of the available bits is chosen, the instruction is shared at all nodes to communicate in that order each with its specific individual corresponding node, which as we know is directly connected, and which if you want to know its address (which you don't need to know) would be uniquely identified by swapping that bit in the first node's address. Continuing with pairwise communications across the order, which is to say across the \(m\) dimensions, a highlighted message can be shared first between 2 nodes then 4, then 8, ultimately all \(2^m\) nodes. Before the final clock cycle there might be extraneous and pointless correspondent communications between pairs which haven't gotten the message yet, but that doesn't slow down the wildfire of what matters.

On the other hand the others might be building up something that does matter to the final outcomes and communicating their partial results also, so that the model is not one of a message spreading across a network, like a wildfire, but of a joint calculation being shared across a network, a bit more like baking a cake where all the parts go from liquid to bubbling to baked each in their own phases but at the same time -- except that cake batter doesn't communicate. If you like this metaphor you could say that the temperature or the cooked state of each bit of batter is really the size of its partial result, and when the partial result becomes the final result at each location then the cake is baked.

Data Parallelism

Process Parallelism

Thus an even-odd preadjust PDC is equivalent to a left-right postadjust PDC, and as an example the so-called decimation in time FFT and decimation in frequency FFT algorithms are actually the same algorithm in terms of what data values are combined using what calculations with what other particular data values, and so they should be treated as effectively the same although this is not pointed out in Numerical Recipes or elsewhere. If you can wrap your mind around that you will be ahead of the entire field of Computer Science today, outside George's place in Seattle.

Space: GIS, Robotics, SLAM

The Dimensional Shuffle Transform is another ingenious ramification of the idea of the bit sequence. What are the bits in a 3D spatial location, that is, a triple of \(X, Y, Z\) indexes? What if you shuffle those bits, taking the most significant from each first, then the second most significant from each after that, etc. Then you have a single 1D binary number of 3x as many bits as the original indexes, and which contains the same information but which now maintains locality: identifiers which share a prefix are both in some corner, some subset, an octant or sub*octant of the 3D space. Hence spatial search reduces to 1D search, which will multiply the efficiency of all space-related algorithms such as SLAM, robotics, etc.

It means you convert space to text, regions to bit strings, and now instead of stupid near-infinitely tree-climbing space-searching, you can do regular binary search on string-sorted strings, which is log N in the length of the store, and find anything in a blink, no tree-climbing. By tree-climbing I mean, testing on this or that side of a dividing plane, climbing down, climbing up, testing, following the pointer to the place that has the data on that side of the tree, left and right, left and right, no. It's just binary search on the sorted text (bit-strings), and binary search can do 14 levels of subdivision in a single high-speed cache hit with 16k values, so we are SMOKING those other algorithms.

Got it?

Summary

Hah! IF you can understand!

And that's what these pages are for, so you can understand them. The not-so-mathematical intuitive explanations for Mou Math, which doesn't speak for Mou's Math but might help you see why and to orient around so you can get the point and the essence and then understand it and then use it and then conquer the world, and maybe save it, too.

Okay?

Let's go!