1. FFT frequency-spectrum coefficients,
the array resulting from time-decimated discrete Fast Fourier Transform D-FFT
computations, is indexed in bit-reversed order: the arithmetic equivalent of replacing
radix 2 by radix 2-1 or 1/2 in the index while keeping the digits as-are
but rescaled, e.g. 011 -> 110.
2. Citified Metric,
proffers semi-efficient linearized packing, sorting, searching, multidimensional
coordinates, by mapping (ordering) points-in-space in neighborhoods-of-neighborhoods
isolated by streets-of-grandeur, accomplished facilely by interleaving coordinate
bits (binary radix): bit-spreading, shifting, prescaling the axes by compensatory
roots-of-2, merging (adding), -equivalent to replacing radix 2 by radix 2² = 4,
likened to squaring but by 2n for higher dimensions-... Binary sorts and
searches can find a significant fraction of nearest neighbors efficiently, like 50%
in gray-scaled 2-space, Less in 3-space....
Gray-scale reordering the linear index to distance-one step through space yields a truer,
serpentine map, metric where the streets are same-grade throughout that is slightly more
efficient having no greater-street crossings while covering the same groupings of
nearest neighborhoods and lots, so reoriented: It is truer, in that small linear
increments are small spatially too. (Implementation can begin at the
integer-fraction radix-point interface.)
Coordinates might be preferentially scaled, -e.g. not precompensated,- so that first-axis
pairs are closest, quads next, then octets....
For better coverage, searching can be multiply-strung (a compound database): on
quadrature-rotated coordinates for 2D, on 3-faced-but-4-diagonal 'octant-rotated' for 3D,
on digital-coordinate-offsets of ...101010 and ...010101 (There is no solution
to get both-001-and-010 offsets, as 011 is like -001) which averages 4+1/16-1 = 1/3 offset,
(or better is ...00110011 and ...11001100 which averages 4-1/16-1 = 1/5 offset, or better-still
...001001 etc. averages 8+1/64-1 = 1/7 offset, but require more strings, etc.) ... as
statistically-overlapped improvement, Coarse, but fast, compact, simple, compared to
distance-computations-for-every-pairing-of-occupied-points-in-space.... And improvements
can be compounded, e.g. in 2D, 4 strings, the original, its diagonal-offset ...00110011
both-x-and-y, the 90°-rotated, and likewise its ...11001100 diagonal-offset....
A trigonally-laid-out metric might fit more tightly, e.g. the secondary axes rotated-30°,
or equivalently the alternate rows offset-interleaved and the whole rescaled,
and the sequence-counting by trinary-gray-scale (tbd).
3. Dragon Curves,
curly scaly space-filling, are accomplishable as arithmetic of radix-reversing and
adding [*] consecutive values (ie. lowpass filter) of an integer index, and proportioning
steering on the carry-bit. Radix 2, ±90°, produces the famous unfolding-paper
Chinese Dragon Curve; Radix 5 works similarly, but is fore-aft symmetric; (Biquinary radix
alternating-2-5 may work); Radix 3 works on 120° turns; (Radix 4 on
90°-turns overlaps a very lot) ... and, Not-truncating below the carry-bit,
produces allusive fractal-like figures, from 'leaves' upto 'seahorses'.
mathematically ideal, combines both bit-interleaving and bit-reversing (as well as
ex-or'ing the coordinates to prefer the diagonal) to accomplish a maximally disperse
order of pixel-photon generation, much as a natural-light display emits photons in
apparently-random disperse order;- and mathematical specifics enable efficient coding
and storage algorithms: Notably, this scheme is infinitely precise video, but for
implementations of camera and display the index can be truncated at some fine detail,
and sub-detail is undistinguished.
5. General Purpose Digital Input/Output Processors,
can utilize bit-re-order for common documentation nomenclature differences, including
indexing signal-bits in alternatively low-to-high or high-to-low naming convention
assignment order; and as well beginning sequences at zero or one: which is bit-shift;-
An IOP program might detect which order is used and quickly adjust.
* [subsequent to bit-scan algorithms for binary dragon-curve routing, Linkabit, ca 1975;
and made available for SAC CPM/P ca 1978]
A premise discovery under the title,
© [1975,1978],1996,2000,2004,2011,2015 GrandAdmiralPetry@Lanthus.net