Log in

No account? Create an account
February 12th, 2012 - Adventures in Engineering — LiveJournal
The wanderings of a modern ronin.

Ben Cantrick
  Date: 2012-02-12 06:55
  Subject:   A log2(n) integer modulo algorithm for CPUs lacking hardware divide.
  Music:The Klein Four Group - Finite Simple Group (of Order Two)

Code...Collapse )

I created this algorithm as a result of reading a post on Reddit that showed some shockingly poor performance for intrinsic software "%" operator in some C compilers for microcontrollers which don't have hardware divide.

How does the algorithm work? Well, the mathematical definition of modulo is:

y % x = y - (x * int(y/x))

The trick this algorithm employs is to do a kind of weirdo binary search to find (x * int(y/x)), without ever directly computing int(y/x), or using division.

Read more...Collapse )

Is it possible to do this faster? I strongly suspect so. As the Wikipedia link given below notes, it is possible to reduce (y % x) to (y & (x-1)) when x is a power of 2. Seems to me that trick should be exploitable to bring the time to compute modulo down even farther. But in any event, the above unsophisticated and unoptimized algorithm should still be a very large improvement over modulo implemented via a software divide routine... as some people's compilers are probably doing now.

See also:



3 Comments | Post A Comment | | Link

May 2015