Neat algorithms

[hamster_nz]

I want to learn some new binary or computational algorithms. The hard thing is that unless you know the names you don't know what to look for.

Things like 8b/10b coding, CORDIC, LFSRs, FFT, forward error correction codes, that sort of thing.

So far I think 8b/10b is my favorite for 'wow' factor, and CORDIC sine/cosine for usefulness, and CORDIC rectangular to polar conversion for how it seems to turn the magical into mundane.

Am thinking of looking at turbo codes - are they nice to study?

[westfw]

There are a lot of collections of this sort of thing.
For example, there is "HAKMEM": ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-239.pdfIt's from 1972, and most of the actual code is PDP10 assembly language (in which you might consider a 36x36bit multiply as faster than than the obvious loop to reverse the bit in a 7 or 8bit byte), but it has some stuff nevertheless.

[westfw]

Bit twiddling hacks: https://graphics.stanford.edu/~seander/bithacks.html

[westfw]

Mark Owen fit an entire floating point library into 1k bytes of ARM CM0 code:  https://www.quinapalus.com/qfplib.html
I don't know if there are any "interesting" algorithms in there, or whether it's just a really impressive implementation...

[hamster_nz]

So I've started to look at BKM - https://en.wikipedia.org/wiki/BKM_algorithm - mainly because the Wikipedia page is so small that it must be interesting  .

It is a "shift and add" algorithm that allows you to calculate things like log(x) and log2(x), such that it could be implemented in digital logic or microcontrollers without floating point. (but it only converges over a limited (but still enough to be useful) range of inputs.

I've converted it to fixed point, and it works like magic:

Code: [Select]

static double log_base_e ( double Argument) /* 1.0 <= Argument <= 4.0 */
 {
    assert(Argument >= 1.0 && Argument <= 4.01);
    uint32_t a = Argument * 512*1024*1024;
    uint32_t x =            512*1024*1024;
    uint32_t y = 0;

    for ( int k = 0; k < N_CONSTANTS; k++ ) {
      uint32_t z = x + (x>>k);
      if ( z <= a) {
          x  = z;
          y += A_e_i[k];
      }
    }
    return y/(1024.0*1024.0*1024.0*2.0);
 }

If anybody else is interested in experimenting, the constants are appropriately scaled versions of A_e[k] = ln (1 + 0.5^i)

Code: [Select]

#define N_CONSTANTS (31)

unsigned int A_e_i[N_CONSTANTS] =
{
        1488522235, 870729689, 479197127,
        252937143,  130190384, 66081633,
        33294987,   16712019,  8372266,
        4190213,    2096128,   1048320,
        524224,     262128,    131068,
        65535,      32767,     16383,
        8191,       4095,      2047,
        1023,       511,       255,
        127,        63,        31,
        15,         7,         3,
        1
};

I've also got log2() version that also works - same algorithm, just different constants:

Code: [Select]

static const unsigned int A_2_i [N_CONSTANTS] =
 {
         2147483648, 1256197404, 691335319,
         364911161,  187825021,  95335645,
         48034512 ,  24110347,   12078627,
         6045199,    3024074,    1512406,
         756295,     378170,     189091,
         94547,      47273,      23637,
         11818,      5909,       2954,
         1477,       738,        369,
         184,        92,         46,
         23,         11,         5,
         2
 };

I'm instantly confused as to how it works, so I think there is plenty of pondering for me to do!

[BravoV]

Subbed ... 

[Berni]

There is also quite a bit to be seen in some of the more advanced fast sorting algorithms.

Another field filled with tricks is computer graphics. The amounts of data that have to be moved is very large so things tend to be optimized to be as efficient as possible. This goes into how to quickly draw smooth lines, fill in polygon areas, do image manipulation such as resampling, stretching, rotations etc.. Then goes into how 3D rendering is done in fast ways, coming from oldschool and now obsolete ray casting to more current polygon based 3D to raytracing to real time ray tracing. For example whole bunch of fancy algorithms are involved in the game like Doom 3D to make it fast enough to run smoothly on the slow computers of the time.

[Nominal Animal]

This might come in handy someday:

I found these when I needed a mapping between in-order and heap/storage-order perfect binary search trees (but I wasn't the first; they're OEIS A131987 and A101279).

    k(i,N) = (b(i + 2^N - 1))/2

    i(k,N) = (k - 2^{⌊log₂ k⌋}) 2^{N - ⌊log₂ k⌋} + 2^{N - ⌊log₂ k⌋ - 1}

where i and k = 1 .. 2^N-1, b(y) is a function that divides y by its largest power of two factor (i.e. removes low zero bits), and ⌊ ⌋ denotes the floor operation.  Note that ⌊log₂ k⌋ evaluates to the position of the highest bit set in k (with 0 used for the least significant bit), and 2^{⌊log₂ k⌋} evaluates to the highest bit set in k.

The two expressions might look odd, but they're surprisingly simple and fast when written in C (using e.g. GCC builtins like __builtin_clz() and __builtin_ctz() and bit shifts); just remember to account for zero-based indexing in C.

[Dubbie]

<snip>coming from oldschool and now obsolete ray casting</snip>

Oi whats this about raycasting being obsolete?

Thats all I do all day every day

[BillyD]

Even though I've never had to use it in my career, I always thought that the Bresenham circle algorithm was very clever.
Up to that I would use floating point trigonometric functions to achieve the same result, at probably thousands of times more processing overhead.

[Nominal Animal]

That reminds me: basic vector algebra. Dot product, cross product, projection, transformation matrices (and their properties), and rotations via unit quaternions aka versors.

If you ever wondered how hard or easy it is to raycast stick-and-balls atomic models, or capped cylinders or capsules, lookee here.  These assume the eye (ray source) is at origin.  (The answer is, very easy with vector algebra, and if you know vector algebra, turning them into raycasting code is easy as well.)

If you've ever done trilateration or multilateration, and you used any trigonometric functions, you did it wrong.  (The formulae are quite easy if you use vector algebra to get to a simple coordinate system where you only need addition, subtraction, multiplication and division, and a single square root to get the result; and vector algebra again, to transform that result to your original coordinate system.)

[T3sl4co1l]

Linear algebra, and complex numbers (arguably a special case of R^2 or R^2x2, depending on which format you opt for, and how you define operations), is a bit of work to learn, but intuitively powerful.

Simple case I've played with, the intersections of lines to give a pseudo-3D perspective view.  The operations are very familiar from complex arithmetic: dot and cross products are complex multiplication and division.



Repeat for all lines in the current sector, and recurse over connected sectors, and you have a rudimentary graphics engine.  This is roughly how Ken Silverman's Build engine is written.  Similar arithmetic applies to Wolfenstein 3D, with simplifications for the grid-based geometry.  (This is not, in fact, how Doom is written -- the geometry is of course just as indispensable, but sorting is done by BSP tree.)

Speaking of raycasters (Wolf3D and such), I implemented one of those on an AVR.  Tons of CPU power for this -- the actual rendering is done in a few milliseconds, the rest is spent drawing pixels to the stupid serial LCD.

It could be textured, if there were enough free RAM/ROM to hold textures in; drawing would be a little slower, really just because more pixels would have to be written (the flat shading allows an optimal display routine, writing exactly the pixels that change from frame to frame; this is why the fill rate varies between scenes).

Also for that display, I wrote this compressor, which was a nice exercise: https://www.seventransistorlabs.com/compr.html

Tim

[scatha]

If you haven't already, before starting on turbo codes have a look at block and convolutional codes more generally. Block codes are a really cool example of applied linear algebra and some of the decoding techniques used in convolutional codes (particularly the Viterbi algorithm) are neat. The Viterbi algorithm is pretty simple, easy to visualize, and pops up in other places where a maximum likelihood path through a hidden Markov model is needed.

[coppice]

If you haven't already, before starting on turbo codes have a look at block and convolutional codes more generally. Block codes are a really cool example of applied linear algebra and some of the decoding techniques used in convolutional codes (particularly the Viterbi algorithm) are neat. The Viterbi algorithm is pretty simple, easy to visualize, and pops up in other places where a maximum likelihood path through a hidden Markov model is needed.

I'd add that if you are interested in turbo codes, also look at LDPC and polar codes. I find LDPC particularly interesting because it was published in the 1960s but sunk without trace, because the industry wasn't ready for it. Then it was rediscovered decades later, and is now widely used.

[hamster_nz]

I'd add that if you are interested in turbo codes, also look at LDPC and polar codes. I find LDPC particularly interesting because it was published in the 1960s but sunk without trace, because the industry wasn't ready for it. Then it was rediscovered decades later, and is now widely used.

I've never heard of Polar Codes before. Thanks!

(starts looking at http://pfister.ee.duke.edu/courses/ecen655/polar.pdf - A Brief Introduction to Polar Codes)

[Berni]

Oh and since nobody trolled with this one, here is the algorithm that's actually called NEAT:
https://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies

[brucehoult]

8b/10b is nice. It's pretty old, developed by IBM in 1983.

One wonders if they were influenced by Woz's "5 plus 3" and slightly later "6 plus 2" encodings, which served the same purpose on Apple ][ floppy disks. 8b/10b of course "wastes" only 20% of the bits vs 25% for "6 plus 2". I also don't think Woz paid a lot of attention to DC balance, but only to the maximum number of bit times without a transition.

[mrflibble]

I've never heard of Polar Codes before. Thanks!

Same here!

(starts looking at http://pfister.ee.duke.edu/courses/ecen655/polar.pdf - A Brief Introduction to Polar Codes)

Just in case you didn't already notice, there's more interesting stuff to be found on the ECEN 655 course page. For example the one on partition functions of non-fucked-up factor graphs. Or whatever's your mathematical poison really. 

[NorthGuy]

I have a book "Numerical recipes in c", which is a collection of various algorithms.

[RoGeorge]

The hard thing is that unless you know the names you don't know what to look for.

Did you parsed the classics?
If not, try the programming bible, the Knuth's books:  https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

[mrflibble]

This might come in handy someday:

I found these when I needed a mapping between in-order and heap/storage-order perfect binary search trees (but I wasn't the first; they're OEIS A131987 and A101279).

    k(i,N) = (b(i + 2^N - 1))/2

    i(k,N) = (k - 2^{⌊log₂ k⌋}) 2^{N - ⌊log₂ k⌋} + 2^{N - ⌊log₂ k⌋ - 1}

Neat! While scribbling those down and looking at the resulting graphs & indices I noticed that it contained cyclic subgroups. Taking the above graphs as example, and start at number k=3, so an entry in the "Storage" graph. That maps to i=6 in the "In-order" graph. Then jump to k=6 in the other graph again, and repeat mapping.

k=3
i(3,N) = 6
i(6,N) = 5
i(5,N) = 3

Now we're back at 3 again, so we have a cycle of 3 elements {3,6,5}.
Similarly we have a cycle of 2 elements {1,4}. Which leaves {2} and {7}.

So I wondered how the number and size of these cyclic subgroups would progress for larger N. In binary notation those cycles also exhibit some interesting patterns. Just the first few entries, N=1..9. Note how mirror and rotation symmetries affect the number of entries in a subgroup. As an extreme example for N=9, the single element group {170} (010101010 binary).

Code: [Select]

  1 : 1

--------------------------------------------------------------------------------

  1 : 01, 10
  3 : 11

--------------------------------------------------------------------------------

  1 : 001, 100
  2 : 010
  3 : 011, 110, 101
  7 : 111

--------------------------------------------------------------------------------

  1 : 0001, 1000
  2 : 0010, 0100
  3 : 0011, 1100, 1001
  5 : 0101, 0110, 1010
  7 : 0111, 1110, 1101, 1011
 15 : 1111

--------------------------------------------------------------------------------

  1 : 00001, 10000
  2 : 00010, 01000
  3 : 00011, 11000, 10001
  4 : 00100
  5 : 00101, 01100, 10010
  6 : 00110, 10100, 01001
  7 : 00111, 11100, 11001, 10011
 10 : 01010
 11 : 01011, 01110, 11010, 10101
 13 : 01101, 10110
 15 : 01111, 11110, 11101, 11011, 10111
 31 : 11111

--------------------------------------------------------------------------------

  1 : 000001, 100000
  2 : 000010, 010000
  3 : 000011, 110000, 100001
  4 : 000100, 001000
  5 : 000101, 011000, 100010
  6 : 000110, 101000, 010001
  7 : 000111, 111000, 110001, 100011
  9 : 001001, 001100, 100100
 10 : 001010, 010100, 010010
 11 : 001011, 011100, 110010, 100101
 13 : 001101, 101100, 011001, 100110
 14 : 001110, 110100, 101001, 010011
 15 : 001111, 111100, 111001, 110011, 100111
 21 : 010101, 010110, 011010, 101010
 23 : 010111, 011110, 111010, 110101, 101011
 27 : 011011, 101110, 011101, 110110, 101101
 31 : 011111, 111110, 111101, 111011, 110111, 101111
 63 : 111111

--------------------------------------------------------------------------------

  1 : 0000001, 1000000
  2 : 0000010, 0100000
  3 : 0000011, 1100000, 1000001
  4 : 0000100, 0010000
  5 : 0000101, 0110000, 1000010
  6 : 0000110, 1010000, 0100001
  7 : 0000111, 1110000, 1100001, 1000011
  8 : 0001000
  9 : 0001001, 0011000, 1000100
 10 : 0001010, 0101000, 0100010
 11 : 0001011, 0111000, 1100010, 1000101
 12 : 0001100, 1001000, 0010001
 13 : 0001101, 1011000, 0110001, 1000110
 14 : 0001110, 1101000, 1010001, 0100011
 15 : 0001111, 1111000, 1110001, 1100011, 1000111
 18 : 0010010, 0010100, 0100100
 19 : 0010011, 0011100, 1100100, 1001001
 21 : 0010101, 0101100, 0110010, 1001010
 22 : 0010110, 0110100, 1010010, 0100101
 23 : 0010111, 0111100, 1110010, 1100101, 1001011
 25 : 0011001, 1001100
 26 : 0011010, 1010100, 0101001, 0100110
 27 : 0011011, 1011100, 0111001, 1100110, 1001101
 29 : 0011101, 1101100, 1011001, 0110011, 1001110
 30 : 0011110, 1110100, 1101001, 1010011, 0100111
 31 : 0011111, 1111100, 1111001, 1110011, 1100111, 1001111
 42 : 0101010
 43 : 0101011, 0101110, 0111010, 1101010, 1010101
 45 : 0101101, 0110110, 1011010, 0110101, 1010110
 47 : 0101111, 0111110, 1111010, 1110101, 1101011, 1010111
 55 : 0110111, 1011110, 0111101, 1110110, 1101101, 1011011
 59 : 0111011, 1101110, 1011101
 63 : 0111111, 1111110, 1111101, 1111011, 1110111, 1101111, 1011111
127 : 1111111

--------------------------------------------------------------------------------

  1 : 00000001, 10000000
  2 : 00000010, 01000000
  3 : 00000011, 11000000, 10000001
  4 : 00000100, 00100000
  5 : 00000101, 01100000, 10000010
  6 : 00000110, 10100000, 01000001
  7 : 00000111, 11100000, 11000001, 10000011
  8 : 00001000, 00010000
  9 : 00001001, 00110000, 10000100
 10 : 00001010, 01010000, 01000010
 11 : 00001011, 01110000, 11000010, 10000101
 12 : 00001100, 10010000, 00100001
 13 : 00001101, 10110000, 01100001, 10000110
 14 : 00001110, 11010000, 10100001, 01000011
 15 : 00001111, 11110000, 11100001, 11000011, 10000111
 17 : 00010001, 00011000, 10001000
 18 : 00010010, 00101000, 01000100
 19 : 00010011, 00111000, 11000100, 10001001
 20 : 00010100, 01001000, 00100010
 21 : 00010101, 01011000, 01100010, 10001010
 22 : 00010110, 01101000, 10100010, 01000101
 23 : 00010111, 01111000, 11100010, 11000101, 10001011
 25 : 00011001, 10011000, 00110001, 10001100
 26 : 00011010, 10101000, 01010001, 01000110
 27 : 00011011, 10111000, 01110001, 11000110, 10001101
 28 : 00011100, 11001000, 10010001, 00100011
 29 : 00011101, 11011000, 10110001, 01100011, 10001110
 30 : 00011110, 11101000, 11010001, 10100011, 01000111
 31 : 00011111, 11111000, 11110001, 11100011, 11000111, 10001111
 36 : 00100100
 37 : 00100101, 00101100, 01100100, 10010010
 38 : 00100110, 00110100, 10100100, 01001001
 39 : 00100111, 00111100, 11100100, 11001001, 10010011
 41 : 00101001, 01001100, 00110010, 10010100
 42 : 00101010, 01010100, 01010010, 01001010
 43 : 00101011, 01011100, 01110010, 11001010, 10010101
 45 : 00101101, 01101100, 10110010, 01100101, 10010110
 46 : 00101110, 01110100, 11010010, 10100101, 01001011
 47 : 00101111, 01111100, 11110010, 11100101, 11001011, 10010111
 51 : 00110011, 10011100, 00111001, 11001100, 10011001
 53 : 00110101, 10101100, 01011001, 01100110, 10011010
 54 : 00110110, 10110100, 01101001, 10100110, 01001101
 55 : 00110111, 10111100, 01111001, 11100110, 11001101, 10011011
 58 : 00111010, 11010100, 10101001, 01010011, 01001110
 59 : 00111011, 11011100, 10111001, 01110011, 11001110, 10011101
 61 : 00111101, 11101100, 11011001, 10110011, 01100111, 10011110
 62 : 00111110, 11110100, 11101001, 11010011, 10100111, 01001111
 63 : 00111111, 11111100, 11111001, 11110011, 11100111, 11001111, 10011111
 85 : 01010101, 01010110, 01011010, 01101010, 10101010
 87 : 01010111, 01011110, 01111010, 11101010, 11010101, 10101011
 91 : 01011011, 01101110, 10111010, 01110101, 11010110, 10101101
 93 : 01011101, 01110110, 11011010, 10110101, 01101011, 10101110
 95 : 01011111, 01111110, 11111010, 11110101, 11101011, 11010111, 10101111
109 : 01101101, 10110110
111 : 01101111, 10111110, 01111101, 11110110, 11101101, 11011011, 10110111
119 : 01110111, 11011110, 10111101, 01111011, 11101110, 11011101, 10111011
127 : 01111111, 11111110, 11111101, 11111011, 11110111, 11101111, 11011111, 10111111
255 : 11111111

--------------------------------------------------------------------------------

  1 : 000000001, 100000000
  2 : 000000010, 010000000
  3 : 000000011, 110000000, 100000001
  4 : 000000100, 001000000
  5 : 000000101, 011000000, 100000010
  6 : 000000110, 101000000, 010000001
  7 : 000000111, 111000000, 110000001, 100000011
  8 : 000001000, 000100000
  9 : 000001001, 001100000, 100000100
 10 : 000001010, 010100000, 010000010
 11 : 000001011, 011100000, 110000010, 100000101
 12 : 000001100, 100100000, 001000001
 13 : 000001101, 101100000, 011000001, 100000110
 14 : 000001110, 110100000, 101000001, 010000011
 15 : 000001111, 111100000, 111000001, 110000011, 100000111
 16 : 000010000
 17 : 000010001, 000110000, 100001000
 18 : 000010010, 001010000, 010000100
 19 : 000010011, 001110000, 110000100, 100001001
 20 : 000010100, 010010000, 001000010
 21 : 000010101, 010110000, 011000010, 100001010
 22 : 000010110, 011010000, 101000010, 010000101
 23 : 000010111, 011110000, 111000010, 110000101, 100001011
 24 : 000011000, 100010000, 000100001
 25 : 000011001, 100110000, 001100001, 100001100
 26 : 000011010, 101010000, 010100001, 010000110
 27 : 000011011, 101110000, 011100001, 110000110, 100001101
 28 : 000011100, 110010000, 100100001, 001000011
 29 : 000011101, 110110000, 101100001, 011000011, 100001110
 30 : 000011110, 111010000, 110100001, 101000011, 010000111
 31 : 000011111, 111110000, 111100001, 111000011, 110000111, 100001111
 34 : 000100010, 000101000, 010001000
 35 : 000100011, 000111000, 110001000, 100010001
 36 : 000100100, 001001000, 001000100
 37 : 000100101, 001011000, 011000100, 100010010
 38 : 000100110, 001101000, 101000100, 010001001
 39 : 000100111, 001111000, 111000100, 110001001, 100010011
 41 : 000101001, 010011000, 001100010, 100010100
 42 : 000101010, 010101000, 010100010, 010001010
 43 : 000101011, 010111000, 011100010, 110001010, 100010101
 44 : 000101100, 011001000, 100100010, 001000101
 45 : 000101101, 011011000, 101100010, 011000101, 100010110
 46 : 000101110, 011101000, 110100010, 101000101, 010001011
 47 : 000101111, 011111000, 111100010, 111000101, 110001011, 100010111
 49 : 000110001, 100011000
 50 : 000110010, 100101000, 001010001, 010001100
 51 : 000110011, 100111000, 001110001, 110001100, 100011001
 52 : 000110100, 101001000, 010010001, 001000110
 53 : 000110101, 101011000, 010110001, 011000110, 100011010
 54 : 000110110, 101101000, 011010001, 101000110, 010001101
 55 : 000110111, 101111000, 011110001, 111000110, 110001101, 100011011
 57 : 000111001, 110011000, 100110001, 001100011, 100011100
 58 : 000111010, 110101000, 101010001, 010100011, 010001110
 59 : 000111011, 110111000, 101110001, 011100011, 110001110, 100011101
 60 : 000111100, 111001000, 110010001, 100100011, 001000111
 61 : 000111101, 111011000, 110110001, 101100011, 011000111, 100011110
 62 : 000111110, 111101000, 111010001, 110100011, 101000111, 010001111
 63 : 000111111, 111111000, 111110001, 111100011, 111000111, 110001111, 100011111
 73 : 001001001, 001001100, 001100100, 100100100
 74 : 001001010, 001010100, 010100100, 010010010
 75 : 001001011, 001011100, 011100100, 110010010, 100100101
 77 : 001001101, 001101100, 101100100, 011001001, 100100110
 78 : 001001110, 001110100, 110100100, 101001001, 010010011
 79 : 001001111, 001111100, 111100100, 111001001, 110010011, 100100111
 82 : 001010010, 010010100
 83 : 001010011, 010011100, 001110010, 110010100, 100101001
 85 : 001010101, 010101100, 010110010, 011001010, 100101010
 86 : 001010110, 010110100, 011010010, 101001010, 010010101
 87 : 001010111, 010111100, 011110010, 111001010, 110010101, 100101011
 89 : 001011001, 011001100, 100110010, 001100101, 100101100
 90 : 001011010, 011010100, 101010010, 010100101, 010010110
 91 : 001011011, 011011100, 101110010, 011100101, 110010110, 100101101
 93 : 001011101, 011101100, 110110010, 101100101, 011001011, 100101110
 94 : 001011110, 011110100, 111010010, 110100101, 101001011, 010010111
 95 : 001011111, 011111100, 111110010, 111100101, 111001011, 110010111, 100101111
102 : 001100110, 100110100, 001101001, 101001100, 010011001
103 : 001100111, 100111100, 001111001, 111001100, 110011001, 100110011
106 : 001101010, 101010100, 010101001, 010100110, 010011010
107 : 001101011, 101011100, 010111001, 011100110, 110011010, 100110101
109 : 001101101, 101101100, 011011001, 101100110, 011001101, 100110110
110 : 001101110, 101110100, 011101001, 110100110, 101001101, 010011011
111 : 001101111, 101111100, 011111001, 111100110, 111001101, 110011011, 100110111
115 : 001110011, 110011100, 100111001
117 : 001110101, 110101100, 101011001, 010110011, 011001110, 100111010
118 : 001110110, 110110100, 101101001, 011010011, 101001110, 010011101
119 : 001110111, 110111100, 101111001, 011110011, 111001110, 110011101, 100111011
122 : 001111010, 111010100, 110101001, 101010011, 010100111, 010011110
123 : 001111011, 111011100, 110111001, 101110011, 011100111, 110011110, 100111101
125 : 001111101, 111101100, 111011001, 110110011, 101100111, 011001111, 100111110
126 : 001111110, 111110100, 111101001, 111010011, 110100111, 101001111, 010011111
127 : 001111111, 111111100, 111111001, 111110011, 111100111, 111001111, 110011111, 100111111
170 : 010101010
171 : 010101011, 010101110, 010111010, 011101010, 110101010, 101010101
173 : 010101101, 010110110, 011011010, 101101010, 011010101, 101010110
175 : 010101111, 010111110, 011111010, 111101010, 111010101, 110101011, 101010111
181 : 010110101, 011010110, 101011010
183 : 010110111, 011011110, 101111010, 011110101, 111010110, 110101101, 101011011
187 : 010111011, 011101110, 110111010, 101110101, 011101011, 110101110, 101011101
189 : 010111101, 011110110, 111011010, 110110101, 101101011, 011010111, 101011110
191 : 010111111, 011111110, 111111010, 111110101, 111101011, 111010111, 110101111, 101011111
219 : 011011011, 101101110, 011011101, 101110110, 011101101, 110110110, 101101101
223 : 011011111, 101111110, 011111101, 111110110, 111101101, 111011011, 110110111, 101101111
239 : 011101111, 110111110, 101111101, 011111011, 111101110, 111011101, 110111011, 101110111
247 : 011110111, 111011110, 110111101, 101111011
255 : 011111111, 111111110, 111111101, 111111011, 111110111, 111101111, 111011111, 110111111, 101111111
511 : 111111111


The number of subgroups for N=1..20:
1,2,4,6,12,18,34,58,106,186,350,630,1180,2190,4114,7710,14600,27594,52486,99878

That looked so deliciously progressive that I would have been a little sad if there wasn't an OEIS entry. The main surprise was going to be, what kind of entry is it going to be.

So ... plug it into OEIS and hope to find something interesting. Turns out it is A052823, "A simple grammar: cycles of pairs of sequences". Sounds about right.
And it has all the right features that can result in a rainy day down the rabbit hole. Or maybe two rainy days, because both the number of n-bead necklaces and the Zeta function reference look vewy vewy rabbit holey. For a previous project, while mucking about with partitioning of bit sequences I kept tripping over beads and necklaces, so I wonder what that reference is going to turn up. I am so hoping that it has partitions all over the place, but that surprise will just have to wait for some rain...

[Nominal Animal]

Absolutely; digit reversal is one of those things that surprised the heck out of me when I first encountered it.  I thought it only appeared in games and tricks, not in real-world tasks, and not in stuff related to graphs!
My intuition says the cyclic subgraphs are related to digit reversal, but my math-fu isn't good enough to be sure.

[mrflibble]

Those cyclic subgroups are indeed caused in part by the reversal of part of the bit sequence. But you don't really need any math-fu to see how it works. Just take a good look at those k(i,N) & i(k,N) functions. Pick the one you find easiest to read, and check what happens when this function is applied. Each step splits the binary representation in 2 chunks, does something reversey to 1 chunk while keeping the other as is, and then swaps the 2 resulting chunks. And you can even see what kind of operation that is when you keep track of what those operations "mean" in the graph.

The way those cycles looked I thought I could probably generate them with a bunch of polynomials over a Galois field + some modular arithmetic (similar to how a LFSR works since I used GF(2)). Well, aaaaalmost, but not quite.  Darnit. I was hoping to generate those cycles using polynomials with a degree comparable to the tree depth, but that was a no-go. Works for the first few orders but after that it's a nogo. Of course you could make it work by using polynomials of higher degree, but that would be cheating.

As for rabbit holes, yup, several freaking big ones. Complete with prime number distributions, because Zeta. Haven't even scratched the surface there, because those or not just rabbit holes, but bloody recursive rabbit holes.

[Nominal Animal]

I know what you mean by rabbit holes (planetary warrens, more like).  I did start looking at whether there are efficient swapping sequences to convert one into another (that's closely related to loops in the graphs), but managed to catch myself in time.

I once explored the Fibonacci sequence, up to examining the ways of calculating a specific F_n efficiently.  Well, that ended up with me reading some papers on how to do multiplication of very large numbers via summing the Fourier-transforms of their digits.  Yeah.  It Gets Deep.

[notadave]

If you like 8b10b you might like my version of 4b6b, I am sure it is a brain twister.
Of these two functions, one counts up, the other down.
Encode.c takes a normal binary number and returns a balanced number. Decode.c converts the other way.
Due to the implementation with zeros in the unused places, it is a fixed number of ones and zeros counter but I meant it to be the same number of ones and zeros. That is why I call it balanced.
What uses you may have for it I can not know, but I use it for channel coding (mostly 4b6b but also 6b8b), without the use of tables or other encoded knowledge. Maybe this type of counting could one day be used by computers that save power by maintaining what ever state property they use to represent bits. The code words are well suited for OOK modulation.
These functions are small as machine code and sufficiently fast for encoding 4b6b and 6b8b at 10kBaud with 8MIps. They only require simple 8bit instructions that are always (PIC, ATtiny, Z80) available, the encoder does not even add. Their run time goes up exponentially with the bits, so even though the algorithm scales  to any number it is impractical.
This implementation is done in 'C', it does not need much memory but done in ASM or HDL the implementation would be different, operating on the bits themselves.
These functions do not provide any error handling, they are part of a chain/stack that ensures data flow, framing, error handling, synchronization, ... none of which is included here. Right in front of the encoding counter you will need a function that skips unwanted combinations. These are to me: 000111=0d and their inverse=19d. Other words might be used as special side channel info or for synchronization. That is how I find/mark the start of a frame.