Bit-permuting relative arrays
A relative array can be enhanced with the
possibility of ADDRESS BIT PERMUTATION. A Bit-Permuting Relative Array or
Permarray in addition to the parameters of a relative array also contains:
|
enum PT; | // Permutation Type.
// Values of PT can be LH (counting low to high), HL (counting high to low), or R (random).
// R subsumes LH and HL, allowing random ordering, using a permutation array P.
// LH is least-significant-first (equivalent to postadjust LR or preadjust EO)
// HL is most-significant-first (equivalent to postadjust EO or preadjust LR) |
|
int P[]; | // A Permutation, being an absolute array of d elements,
// which contain all the integers 0..d-1 once each, but in
// any permuted order (of which there are d! distinct orderings).
// Then d-1 is an index into P[] while P[d-1] is an actual bit index,
// counting from least to most significant. For example P[d-1]==2 for the most significant
// bit in the 8-element range 0..7 given PT==LH.
|
Now let V be a bit-permuting relative array with \(2^d\) elements, PT==R,
and ordering of address-bit operations according to permutation
P. Let us follow the tail-first convention, namely that, if
P[d-1] = i, then the i'th bit of the addresses in V is the first
bit to use for a division operation \(d_P\), and the last bit to
use for a combine operation \(c_P\).
Note that the concept of least and most significant bits in an
address is lost in permuted relative arrays, that is, when
PT==R. "Least significant" and "most significant" are concepts
dependent on a particular digit-ordering convention.
Writing letters in language, Arabic and Hebrew associate
before-to-after as right-to-left in writing, whereas English
oppositely considers that left "precedes" right. Similarly
digits, whether decimal, binary, or any other base, are
conventionally written in decreasing order of significance in
our accepted number-writing system, but a informationally
equivalent but opposite convention could write digits in
increasing order of significance.
It doesn't matter what order we write them in, it matters
what order we process them in. Further the digits in a
position in a multi-digit number have their own separate
ordering, being the counting order of single digits, which is
separate from the writing or processing order of the digits in the
multi-digit number.
In the case of binary numbers, the counting order of single
digits is always 0<1, while in multi-digit binary we write
most-significant first, least-significant last, but this latter
is also mere convention. Given the possibility of bit
permutation, low-to-high and high-to-low are only two of d!
permutations.
But every bit divides the entire address space into two
equal-sized halves, one with '0' in that bit, and the other with
'1' in that bit. None is more significant than any other, from
this perspective. But if you divide one half in half again,
then the first division by which you extracted a half was more
significant than the second division by which you extracted a
quarter. Processing order can give significance order.
Similarly, intuitions about string-ordering of elements in
arrays are not helpful in the context of randomly ordered bit
permutations of the element addresses within the array.
Instead, it may be more intuitive to think of the elements as
corners of a d-dimensional binary hypercube, and to consider division as
splitting the hypercube along an arbitrary dimension. Similarly
combination can be seen as taking two d-1 dimensional
hypercubes, and joining them corresponding point to
corresponding point across a new dimension the d'th, which could
in principle be considered as a bit in any position within (the
permuted ordering of) the bits of the address.
I find the hypercube idea extremely helpful and intuitive, so I
encourage you to try to get the insight of it.
Permutation concepts:
P[d-1] is the last element of P. P[d-1] = i means the i'th bit
in the address is the bit to be used to divide first, combine
last, or to associate related arrays
for communication at a certain level.
The first division is on the last bit P[d-1], a convention that
requires no change or renumbering of the elements of P. Simply
setting d=d-1 is the main activity in accomplishing a division;
then there could be an extra ignored element in the permutation
array P, namely P[d+1], we need not take notice of
this. Similarly the last combination adds 0's and 1's to the
P[B-1]'th bit, voila.
If dividing on the high (d'th) bit first, P[d-1]=B-1;
if dividing on the low bit first, P[d-1] = 0;
Using a random permutation, the concept of counting order of
addresses goes out the window.
Instead, like the FFT bit-twiddling (which substitutes EO for LR
division), but even more twiddled, a permutation can be any of
B! reorderings of a (\(2^B\)-sized) array's address bit indexes
0..B-1.
Which bit is which?
Considering the binary number 01, the 1'th position has value 0, and the 0'th position has
value 1, because positions count from least to most significant
(which means they count backwards in the high-to-low digit
ordering we learn in 1st grade). Anyway that's intuitive to me.
An Example:
Although the math is elegant, I find myself falling into traps of
unnecessary assumptions, which are made clear when I work a concrete
example. So...
What does random permutation of bits in division look like, more
concretely?
Let's say there are 8 elements in an absolute or relative array, A, at
addresses 0, 1, 2, 3, 4, 5, 6, and 7, which can be written in binary
as addresses 000 001 010 011 100 101 110 111, retaining the high '0'
bits. Among these, 4=100 has its 2'nd bit set to 1. (We count these
from least to most significant -- those being bits 0 and 2
respectively -- in this case.
But moving from absolute and plain relative arrays which count from 0
to L-1, let's switch perspectives by using a address-bit permutation
such as P = [ 1, 0, 2 ], and carry out division.
The initial division of A is with respect to the last element of P
namely 2 which is the most significant bit considered in sequential
ordering of the addresses in A, but it is random that the last element
of P calls out the most significant bit in the counting-order
addresses of A. Hence the first division of A with P=[1,0,2] is:
A = [ 000 001 010 011 100 101 110 111 ] divides into
L = [ 000 001 010 011 ], R = [ 100 101 110 111 ]
See, the addresses having 2'th bit (the leftmost bit according to our
multi-digit number-writing convention) with a '0' there, send their
elements to the left subarray and those with 2'th bit having value '1'
go to the right subarray. Right? Please check to confirm!
The next division uses the next-from-the-end entry in P namely P[1] =
0, hence division is w.r.t. the 0'th (least significant) bit thus:
[ 000 001 010 011 ] and [ 100 101 110 111 ] respectively divide into
[ 000 010 ][ 001 011 ] and [ 100 110 ], [ 101 111 ],
where the left arrays will get the elements whose address within the
array has a '0' in the 0=P[1]'th bit (the rightmost bit), and the
right arrays get the elements with a 1 in the 0=P[1]'th bit.
This continues. To generalize, we can recursively divide arrays into
left right subarrays elements using bit index i = P[++d]. Each
time you get half-sized arrays with the value in the i'th bit being 0
in the left subarray and and 1 in the right subarray.
Make sense?
Finally, to test your understanding, consider this:
If instead we used PT=LH (equivalent to PT=R with P = [ 0, 1, 2 ]) we
could construct the absolute array address, i, of an element in a relative
array V with dividing bit d as \(i = lo \land (1 \ll d) \land (hi \ll (d+1))\), where \(lo\) is the
element's address within V, d the dividing bit, and \(hi\) the ordinal of
sub-array V (one of \(2^{B-d-1}\) same-sized sub-arrays within the
absolute array A). Check my arithmetic! Am I right?
|
