Close

Multiplication/Division and Floating-point-removal

A project log for limited-code hacks/ideas

When you're running out of code-space... sometimes yah's gots to hack. Here are some ideas.

eric-hertzEric Hertz 11/27/2016 at 14:010 Comments

There may be a lot of cases where floating-point "just makes sense" in the intuitive-sense...

But Floating-Point math takes a *lot* of code-space on systems which don't have an FPU.

I'm not going to go into too much detail, here... but consider the following

float slope = 4.0/3.0;

int pixelY = slope * pixelX + B;
This can be *dramatically* simplified in both execution-time and code-size by using:
int slope_numerator = 4;
int slope_denominator = 3;

int pixelY = slope_numerator * pixelX / slopeDenominator + B;

Note that the order matters!

Do the multiplication *first*, and only do the division at the *very end*.

(Otherwise, you'll lose precision!)

Note, also, that doing said-multiplication *first* might require you to bump up your integer-sizes...

You may know that pixelX and pixelY will fit in uint8_t's, but pixelX*slope_numerator may not.

So, I can never remember the integer-promotion rules, so I usually just cast as best I can recall:

uint8_t B = 0;
uint8_t pixelX = 191;
uint8_t pixelY = (uint16_t)slope_numerator * (uint16_t)pixelX
                 / slopeDenominator + B;

Don't forget all the caveats, here... You're doing 16-bit math, probably throughout the entire operation, but the result is being written into an 8-bit variable... The case above results in pixelY = 254, but what if B was 2?

------

Regardless of the casting, and the additional variable, this is almost guaranteed to be *much* faster and *much* smaller than using floating-point.

----------

@Radomir Dopieralski strikes again!

I was planning on writing up about iterative-computations, next... but it's apparently already got a name and a decent write-up, so check out: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

(whew, so much energy saved by linking!)

THE JIST: The above examples (y=mx+b) should probably *NOT* be used for line-drawing!

They're just easy/recognizable math-examples for this writeup to show where floating-point can be removed.

On a system where you *have* to iterate through, anyhow (e.g. when drawing every pixel on a line, you have to iterate through every pixel on the line), then you can turn the complicated math (e.g. y=mx+b) containing multiplications/divisions into math which *only* contains addition/subtraction.

(Think of it this way, how do you calculate 50/5 way back in the day...? "How many times does 5 go into 50?" One way is to subtract 5 from 50, then 5 from 45, then 5 from 40, and so-on, and count the number of times until you reach 0. Whelp, computers are great at that sorta thing, and even better at it when you have to do looping for other things as well.

Discussions