Caculating 1/d if you have multiply

[rcgldr]

This will be done in assembly code, using an integer multiply, 32 bit by 32 bit producing 64 bit result. Unsigned algorithm is good enough.


Generic algorithm to find 1 / D, eq is initial estimated quotient, from table, say with 8 bits of precision.

$$q_0\ =\ eq$$

$$q_{n+1}\ =\ q_n\ (2\ -\ q_n\ X)$$

For integer math, pre and post shifting of values will be done. Generally only 4 or 5 interations are required to get 32 bits of precision.

Are there better algorithms?

 

[Aaron Barnard]

Yes, there are better algorithms available for computing the inverse of a number. Newton-Raphson iteration is one of the most popular methods used. This method involves repeatedly calculating the derivative of the function and using it to refine the estimate for the inverse. Other methods such as the binary search algorithm can also be used to calculate the inverse.

 

[ravenprp]

There may be more efficient algorithms for calculating 1/D in assembly code, but the generic algorithm provided is a good starting point. It uses a technique called Newton's method, which is commonly used for finding the root of a function. In this case, the function is 1/D and the root is the quotient.

Some possible improvements to this algorithm could include using a lookup table for the initial estimated quotient, which could save some computation time. Additionally, instead of using a fixed number of iterations, the algorithm could be modified to stop when a certain level of precision is achieved. This would also save some computation time.

Overall, the most efficient algorithm will depend on the specific hardware and programming language being used. It may be worth experimenting with different variations of the algorithm to see which one performs the best in a particular situation.