Radix-Grafted Arithmetic

several applications

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....

citified metric: serpentine, jazz 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). dragon curves: binary, quinary

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'.

4. Fully interleaved video-scanning,

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,

Grand-Admiral Petry
'Majestic Service in a Solar System'
Nuclear Emergency Management

© [1975,1978],1996,2000,2004,2011,2015 GrandAdmiralPetry@Lanthus.net