Products > Programming

Neat algorithms

(1/43) > >>

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

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: ---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);
 }

--- End code ---

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


--- Code: ---#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
};

--- End code ---

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


--- Code: ---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
 };

--- End code ---

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

Navigation

[0] Message Index

[#] Next page