GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Adam Horvath's blog

This view

  • Original page
  • New address

GeezerVison is showing blog.teamleadnet.com — Faster division and modulo operation - the power of two

Faster division and modulo operation - the power of two

  • Get link
  • Facebook
  • X
  • Pinterest
  • Email
  • Other Apps
July 05, 2012
The power of two - fast division and modulo operations

There are some - admittedly rare - cases, when the division and modulo operations are responsible for a great percent of the total runtime.

Such case might be when a high performance circular array positioning is calculated and the pointers use the modulo (ptr = curr % ArraySize) operation to calculate the real position in the current array.

The good news is, that if all the variables are known at compile time, the compiler will help to optimise the division/modulo. The bad news is, that with a dynamic sized array, the compiler won't help anything.

Even worse news is that both the DIV and MOD operations are pretty slow on every CPU (or at least  slower than other atomic operations).

Speeding it all up

If the pointer calculation in the previous example is a concern, there is a way to speed it up: use the powers of two! If the divider is a power of two, both the division and modulo operations become extremely simple:

The number X
in decimal: 143
in binary:  1000 1111

The divisor D
in decimal: 4
in binary:  0100

The result (with integers):
X / D = 0010 0011 = 35
X % D = 0000 0011 =  3

However, because D is a power of two, these can be rewritten as:

X / D = X >> 2   = 0010 0011
 (eliminating the last 2 bits; if the divider is 8 then the last 3 bits...)
X % D = X & 0011 = 0000 0011
 (looking at the bits on the right of the divider)

As both the shift (>>) and AND (&) operations are extremely fast, the division/modulo operations  can be tuned if the divider is a power of two and the code is accordingly (the current CPUs will not do this on the fly for you, you have to rewrite the code).

Rewritten division

If the input can be anything, we need to determine whether the divider is a power of two:

if ((divider & (divider - 1)) == 0) { …

If a number is a power of two, it means it has only a single bit set to 1. If we subtract 1 from this number, we have all the positions set to 1 on the right of the original bit:

Number:   1000
Number-1: 0111

If we AND these numbers and the result is zero, it was a power of two!

Be warned, that this operation takes time so do it only once, outside the loop otherwise all performance gain will be lost!

DIV

For dividing, we need to find the number of shifts:

int shift = 0;
int divtmp = divider;
while (divtmp > 1) {
 divtmp = divtmp >> 1;
 shift++;
}

Be warned, that this operation takes time so do it only once, outside the loop otherwise all performance gain will be lost!


If the divider is 8, we will have 3 if the "shift" variable (shifting 1 right is the same as dividing by 2).

From here on, all we need to do is substitute the division with the shifting:

// int x = i / divider;
int x = i >> shift;

MOD

For modulo operation, it's even easier. After deciding whether the number is a power of two, just create a simple AND mask:

int and = (divider) – 1;

Then replace the MOD operation with and AND:

// int x = i % divider;
int x = i & and;

Results

The results are actually quite impressive. I've tested on both an i7 and an Atom processor and the results where the between 10-20x faster than with simple division or modulo (Ref is the empty cycle to give reference for standard speed; Pow2DivMod ran when the divider was power of two and DivMod ran in all other cases).


Performance
  • Get link
  • Facebook
  • X
  • Pinterest
  • Email
  • Other Apps

Comments

  1. UnknownJanuary 15, 2016 at 8:03 AM

    I'd like to know why it has been so difficult to find an algebraic solution to the modular operation. Wouldn't this speed things up?

    ReplyDelete
    Replies
      Reply
Add comment
Load more...

Post a Comment

Popular posts from this blog

How to remove adware (browser hijack or pop-up malware) from Android

June 19, 2015
Image
The browser hijack style malware is getting pretty widespread on Android devices, especially the cheaper ones that can be purchased directly from overseas and come with pre-installed malware. Let’s see how to find the adware app that is causing the issue. The symptom is usually the same: when the web browser is opened it is redirected to an unknown webpage advertising something totally useless. In some cases a virus infected APK Android package gets downloaded in the hope that it will get installed. The app that is causing this issue is waiting in the background for the browser process (either Chrome or Android Browser) to start. When it does it asks it right away to display a webpage. The intent Android natively supports communication between apps, which in itself is very useful, for instance a webpage can be opened from the email client. The code is pretty straightforward too: Uri webpage = Uri.parse(url);     Intent intent = new Intent(Intent.ACTION_VIEW, web...
. . .

Read more »

Quick select algorithm - find the Kth element in a list in linear time

July 23, 2012
Image
Quick select algorithm (Hoare's selection algorithm) – select the Kth element or  the first K element  from a list in linear time Working with large datasets is always painful, especially when it needs to be displayed in a ‘human readable’ format. It is a very frequent task to display only the largest, newest, most expensive etc. items. While sorting the whole dataset definitely gives a correct result, it is much slower than it needs to be – it needs at least O(n*log(n)) time and an it often uses recursion for the sorting, so in practice it can be quite slow. The quick select algorithm can get the top K element from a list of N items in linear time, O(n), with a very reasonable multiplication factor. The quick select does not use recursion so the performance is great for even large datasets. Algorithm The idea of the quick select is quite simple: just like with quicksort, select a random element from the list, and place every item that is smaller to the first half o...
. . .

Read more »

Removing Malware and Bloatware from Lenovo K3 Note (K50-T5)

June 19, 2015
Image
I’ve recently purchased a Lenovo K3 Note from Gearbest and it came with preinstalled malware and bloatware. Here are the things I had to do to bring the phone into a usable state. Root it Lot of the malware was preinstalled system apps which cannot be removed without root mode. I’ve rooted using the CWM (ClockworkMod) method , installing the CWM recovery image then installing SuperSU. The KingRoot method should be easier but didn’t work for me. Remove apps - Bloatware I’ve used Titanium Backup because I wasn’t sure which app would break the phone if removed. I removed the following preinstalled apps (that I remember): BSPTelephonyDevTool 1.0 DU Batter Saver 3.9.9 DU Speed Booster 1.4.0 Mcube Mobile Assistant 3.0.4.0835 Power Manager 1.1.287.150113.c3631eb SYNCit 4.0.54 Theme Center 2.70… UPDATE: needed for ringtone selection User Experience 4.4.1 Remove apps – Malware that was display popup ads The malware that was hijacking my browser was hidden in a modi...
. . .

Read more »

You are visitor 01402605 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.