C: Exponentiation over 256bit integers

Question

I am dealing with an algorithm that operates on unsigned 256-bit integers, and I need to write a function that computes the value of the given formula

uint256 compute(uint16 x) {
    return floor(exp2(x / 256)) - 1;
}

We can see that the equation preserves the variable bounds (compute(0) == 0, compute(65535) == 1<<255). The division should be treated as division of rational numbers, not integers.

The presented syntax is pseudo-C, but I'm looking for a general algorithmic aproach that could be used in other languages.

Thank you very much for your help and time.

Answer 1

You can precompute and tabulate all 256-bit values of the function for x in [65280, 65535] (i.e. 255 x 256 + i); you will lookup the table by the 8 least significant bits of the argument. That will take 8KB of storage.

For lower values of the argument, shift the tabulated value right by 255 - (x >> 8).

If you want sheer speed and can afford 64KB of storage, you can precompute the shifts 0 to 7, and perform larger shifts by copying with the right byte offset.

Alternatively, you can consider the CORDIC method for exponentials, but I don't think it will be faster or require less storage.