Divide by 240

!Readme.md

Fast Division

We want to calculate x/240, and to do that, we calculate (x*34953)>>23. This only works for sufficiently small values of x.

The value of 34953 looks like some kind of magic constant. It is really just ceil((1 << 23)/240)—the value 1/240, scaled up by 2^23. As you use larger scaling factors (above 1<<23), the value becomes more accurate, but you need more bits.

GCC can do this optimization for you under certain circumstances. GCC will convert x * 34953 to the same sequence of shifts and adds, if you are targeting an old processor like a 68000.

divide_240.c

// Return x/240, for 0 <= x <= 61439.
int divide_240(int x) {
	// Same as (x * 34953) >> 23.
	int y = x + (x << 4);
	y += y << 8;
	return ((y << 3) + x) >> 23;
}

// Test that the divide_240 function is correct.
#include <stdio.h>
int main(int argc, char **argv) {
	(void)argc;
	(void)argv;
	for (int x = 0; x <= 61439; x++) {
		int expect = x / 240;
		int result = divide_240(x);
		if (expect != result) {
			fprintf(stderr, "Error: divide_240(%d) = %d, should be %d",
				x, result, expect);
			return 1;
		}
	}
	return 0;
}