StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I know of two ways to do this without using division or modulus:</p> <p><em><strong>Method 1: Invariant Multiplication</em></strong>. (<a href="http://www.google.com/url?sa=t&rct=j&q=invarient%20multiplication&source=web&cd=1&ved=0CCsQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.1.2556%26rep%3Drep1%26type%3Dpdf&ei=RjOpTvWmMuXn0QGQyN2oDg&usg=AFQjCNGU0J-Es-VtoO0SylcMLWrs2mHXow&sig2=whOZcSLbz7VD4taq5ORlRg&cad=rja" rel="nofollow">see this paper</a>)</p> <p>The basic idea here is to pre-compute and approximation of the reciprocal of the <code>p</code> which allows you do an integer division using just a couple of integer multiplications. Then you can multiply back and obtain your modulus. This is the easier approach to implement.</p> <p><em><strong>Method 2:</em></strong> (the one that I usually use), <strong><em>is to use floating-point</em></strong>. Convert the numbers to floating-point and multiply by a pre-computed reciprocal of <code>p</code>. Then round and convert back to an integer. This approach is harder to get right, but from my experience it's faster if done properly.</p> <p>Both approaches here involve no divisions aside from a pre-computation of the reciprocal either in integer or floating-point.</p> <p>Whether or not either of these methods will be faster than straight-forward use of <code>%</code>, will depend on how well you can implement them. So I can't guarantee that either one will be faster.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload