Apple’s falling division | Hackaday

[Paul Curtis] over at Segger has an interesting series of blog posts on division calculus. It used to be a hotter topic, but nowadays many computers or computer languages ​​support multiplication and division. But some processors don’t have the instructions, and a library to do so might be less than ideal. Knowing how to roll yourself can allow you to optimize speed or space. The current episode covers using Newton’s algorithm to do division.

Steve Martin had a famous passage about how to be a millionaire and never pay taxes. He started off by saying, “First… get a million dollars. So…” This method is a bit like that since you first have to know how to multiply before knowing how to divide. The basic principle is twofold: Newton’s method allows you to refine an estimate of a reciprocal by successive multiplications, then multiplying a number by a reciprocal is equivalent to dividing. In other words, if we need to divide 34 by 6, you can rewrite 34/6 as 34*1/6 and the answer is the same.

Newton’s approximation for reciprocals lets you guess the answer and then refine it through a series of multiplications. Each multiplication creates better precision. You can use it to make a classic speed/space tradeoff. For example, let’s just say we want to find the inverse of a byte (presumably a fixed-point byte). A 256 element lookup table would provide perfect accuracy and would be very fast. No more math. But what about 32-bit? Now the table is just too big. But you can search, for example, the first 8 bits of the 32-bit number. Or more. Or less. It depends on what is important to you.

So now you have a bad estimate of your reciprocal. Sir Issac can improve it. For a number a, You make your estimate (X) and multiply them together. Subtract that number from 2 and you have a factor to multiply your old estimate by to get a new estimate. Jumping further, it’s clear that if your guess was correct, the multiplication would give you 1, which wouldn’t change the old guess in any way. If the estimate is wrong, you will get a scale factor.

As a formula, it looks like this:

x=x*(2-a*x);

So if you decide that the reciprocal of 22 could be 0.02, the first pass will give you:

0.02*(2-22*0.02) = .0312

.0312*(2-22*.0312) = .0410

.0410*(2-22*.0410) = 0.0450

The correct answer is a repeating decimal 0.0454545 and if you keep going you will get there.

Of course, you then have to multiply one more time to do the division.

We liked that the post has a fixed point implementation and then looks at the resulting assembly code for ARM, RISC-V and dsPIC30. Well worth a read.

We love the math tricks we can use in assembly language. If you work on AVR and floating point, don’t miss this method.

About Roberto Frank

Check Also

OnePlus 10 Pro: long-term review

Over the years, OnePlus has managed to transform itself from an emerging player into a …