Divide by 10 using bit shifts?

by

Editor’s note: this is not actually what compilers do, and gives the wrong answer for large positive integers ending with 9, starting with div10(1073741829) = 107374183 not 107374182. It is exact for smaller inputs, though, which may be sufficient for some uses.

Compilers (including MSVC) do use fixed-point multiplicative inverses for constant divisors, but they use a different magic constant and shift on the high-half result to get an exact result for all possible inputs, matching what the C abstract machine requires. See Granlund & Montgomery’s paper on the algorithm.

See Why does GCC use multiplication by a strange number in implementing integer division? for examples of the actual x86 asm gcc, clang, MSVC, ICC, and other modern compilers make.

This is a fast approximation that’s inexact for large inputs

It’s even faster than the exact division via multiply + right-shift that compilers use.

You can use the high half of a multiply result for divisions by small integral constants. Assume a 32-bit machine (code can be adjusted accordingly):

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

What’s going here is that we’re multiplying by a close approximation of 1/10 * 2^32 and then removing the 2^32. This approach can be adapted to different divisors and different bit widths.

This works great for the ia32 architecture, since its IMUL instruction will put the 64-bit product into edx:eax, and the edx value will be the wanted value. Viz (assuming dividend is passed in eax and quotient returned in eax)

div10 proc 
    mov    edx,1999999Ah    ; load 1/10 * 2^32
    imul   eax              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
    endp

Even on a machine with a slow multiply instruction, this will be faster than a software or even hardware divide.

More Related Contents:

  1. How to perform division in Go
  2. Why is division in Ruby returning an integer instead of decimal value?
  3. A simple algorithm for polygon intersection
  4. Mathematically compute a simple graphics pipeline
  5. How to perform an integer division, and separately get the remainder, in JavaScript?
  6. How do I calculate the normal vector of a line segment? [closed]
  7. Calculating area enclosed by arbitrary polygon on Earth’s surface
  8. Is Big O(logn) log base e?
  9. Overflow and Carry flags on Z80
  10. correcting fisheye distortion programmatically
  11. Implementing Ray Picking
  12. Calculate the center point of multiple latitude/longitude coordinate pairs
  13. Calculating a LookAt matrix
  14. Quadratic Bézier Curve: Calculate Points
  15. How to use 4d rotors
  16. Is finding the equivalence of two functions undecidable?
  17. Why does dividing a float by an integer return 0.0?
  18. Perpendicular on a line from a given point
  19. Why must a nonlinear activation function be used in a backpropagation neural network? [closed]
  20. How to map atan2() to degrees 0-360
  21. Calculate second point knowing the starting point and distance
  22. how map 2d grid points (x,y) onto sphere as 3d points (x,y,z)
  23. “Average” of multiple quaternions?
  24. Why does floating-point arithmetic not give exact results when adding decimal fractions?
  25. 3D coordinates on a sphere to Latitude and Longitude
  26. Calculate rotated rectangle size from known bounding box coordinates
  27. The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?
  28. Line of intersection between two planes
  29. Flipping a quaternion from right to left handed coordinates
  30. OpenGL Math – Projecting Screen space to World space coords

Leave a Comment