0

Is there any general (not ISA specific) way, how to get a reciprocal value of any positive number in assembly, not using div function?

I am using reciprocal values for division of an unknown number x by a constant y. Say, I want to divide 256 by a constant 3 (which is same as multiply 256 by 1/3)

  1. Calculate 1/3 by hand
  2. Convert 0.3333... from floating point to Q32 fixed point (32 fraction bits unsigned) 1/3 * 2^32 = 0x55555555 by hand
  3. Save 0x0x55555555 constant to a register in assembly as an immediate value
  4. Multiply 0x100 * 0x55555555 = 0x5555555500 in assembly
  5. Convert back from Q64 fixed point to 32bit integer 0x5555555500 >> 32 = 0x55 = 85 in assembly

This is working fine, but now, I want to divide 2 unknown number by each other. In order to do this, using the algorithm above, first I must calculate a reciprocal value of the y in assembly, not by hand.

Or is there another general method, which I can use for division? I don't want to use subtraction in a cycle to calculate the division because of speed performance of my code.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
peter_esp
  • 31
  • 2
  • 1
    You mean like [Why does GCC use multiplication by a strange number in implementing integer division?](https://stackoverflow.com/q/41183935)? If you want to do that for a runtime variable, see libdivide [Repeated integer division by a runtime constant value](https://stackoverflow.com/q/45353629) for an example of that, or use one of the algorithms yourself to find that fixed-point reciprocal. Or do you really just want a fixed-point reciprocal directly, for use with fixed-point math, not for exact integer division? If so, please add the [fixed-point] tag, and maybe remove [integer-division] – Peter Cordes Nov 25 '22 at 11:22
  • 1
    Note that `1 / 3 * 2^32` = `2^32 / 3`. You also use the usual "convert to binary" algorithm but for the decimal part (multiply by 2, take the integer part, repeat with the fractional part). For a number in the form `a / b` you just double the numerator and if `2a >= b` you have a 1 and repeat with `2a - b / b`. if `2a < b` you have a 0 and repeat with `2a / b`. You keep looping util your number is 0 or you reached full precision. The bits goes in the Q32 number from the MSb. – Margaret Bloom Nov 25 '22 at 11:43
  • You can implement the binary version of long division. – Simon Goater Nov 25 '22 at 11:52
  • If the goal is 1/x, some divisors require an extra bit. For example, for a 32 by 32 bit divide, 1/7 requires 33 bits, for the multiply and shift method, which also has to be modified. Link to a [prior answer](https://stackoverflow.com/questions/41183935/41224096#41224096) that explains this. – rcgldr Nov 27 '22 at 03:28

1 Answers1

1

Newton Raphson algorithm is one way to implement this. Using a table for initial estimate based on the upper non-zero bits of the divisor can speed up the process. A second table can be used for the inverses of small numbers, like from 2 to 255.

https://en.wikipedia.org/wiki/Division_algorithm#Newton%E2%80%93Raphson_division

rcgldr
  • 27,407
  • 3
  • 36
  • 61