multiplicative inverse with lookup table

user_4928920 0
Viewed 193

I have an formula that I use multiple times in my subroutine, but my processor does not have division instruction(M0), so this is handled by the software library. To speed up this operation, I am considering using a lookup table to store the result of the inverse. However that would still take up 2kb in space (2 bytes per value). How can I optimize it further?

Formula is as follows, k is a constant known at compile time k = [10, 100]. x = [0, 1023]

(1000 * k) * ((1023/x) - 1)

EDITE: Clarification about precision. Since I have the "1000", I am considering using the result of the multiplication by 1000 to increase precision.

arm math c
4 Answers

Assuming / is integer division

You don't need to store 1024 values, because many values of x result in the same value of 1023/x.

Specifically:

x:      [   1,    2,    3,    4,    5,    6,    7,    8,    9,   10,   11,   12,   13,   14,   15,   16,   17,   18,   19,   20,   21,   22,   23,   24,   25,   26,   27,   28,   29,   30,   31,   33,   34,   35,   36,   37,   39,   40,   42,   44,   46,   48,   51,   53,   56,   60,   63,   68,   73,   78,   85,   93,  102,  113,  127,  146,  170,  204,  255,  341,  511, 1023]
1023/x: [1023,  511,  341,  255,  204,  170,  146,  127,  113,  102,   93,   85,   78,   73,   68,   63,   60,   56,   53,   51,   48,   46,   44,   42,   40,   39,   37,   36,   35,   34,   33,   31,   30,   29,   28,   27,   26,   25,   24,   23,   22,   21,   20,   19,   18,   17,   16,   15,   14,   13,   12,   11,   10,    9,    8,    7,    6,    5,    4,    3,    2,    1]

You need only to store these 62 values of x and the 62 results of 1023/x.

As a bonus: if you look carefully, you'll notice those values are symmetric. The values for x are the exact mirror of the values for 1023/x. So you only need to store one of these two arrays.

user_30807230

You can easily shrink the lookup table to 256*2 bytes

static inline uint16_t get1023divxminus1(uint16_t x)
{
    static const uint16_t table[256] = {0, 1022, 510, ....., 3};
    if (x >= 512) return 0;
    if (x >= 342) return 1;
    if (x >= 256) return 2;
    return table[x];
}

You could shrink the table even further, but I think it isn't worth the additional ifs.

user_10215040

You could compress the data in the table.

For example by storing full 2-byte values for every N-th value of x and store difference values for xs in between. The difference should fit in 1 byte in many cases.

If N would be 4, you'd store full values for x: 0, 4, 8, ... and difference values for x: 1, 2, 3, 5, 6, 7, 9, ...

To get the result for say x == 3, start with 2-byte value of 0 and add the 1-byte difference values of 1 and 2.

There will for sure be other 'tricks' to play if you'd have a close look at the data and think in the direction of data compression.

user_19710130

Accessing RAM is probably going to be slower than calculating long division, as long as your values fit within a register. In principle, calculating long division should be linear in the number of bits. Implement both and profile, but I am highly convinced that long division will be faster:

The algorithms is: left shift the divisor until the MSD of the divisor equals the MSD of the dividend.

If the divisor is smaller than the dividend, write one, else write 0. Right shift the divisor by one. Repeat until the LSD of the divisor is also the LSD of the dividend.

Here is an explicit implementation: https://codegolf.stackexchangechaschastitytity.com/questions/24541/divide-two-numbers-using-long-division

user_62023270
Related