13,142,182 members (55,468 online)
Tip/Trick
alternative version

#### Stats

23.1K views
11 bookmarked
Posted 23 Dec 2013

# Fast floor/ceiling functions

, 24 Dec 2013
 Rate this:
Yet another home-made implementation of the floor function

## Introduction

Those of you who are after sheer running speed already know how slow the standard floor/ceiling functions can be. Here are handy alternatives.

## Background

The standard floor/ceiling functions have two drawbacks:

1. they are shockingly slow, and
2. they return a floating-point value;

when what you want is an integer, this costs you an extra conversion to int, which seems extraneous.

You will find alternatives on the Web, most being built on a cast to int. Unfortunately, this cast rounds towards zero, which gives wrong results for negative values. Some try to fix this by subtracting 1 for negative arguments. This solution is still not compliant with the function definition, as it does not work for negative integer values.

Closer scrutiny shows that the -1 adjustment is required for all negative numbers with a nonzero fractional value. This occurs exactly when the result of the cast is larger than the initial value. This gives:

i= int(fp); if (i > fp) i--;

It involves a single comparisons and an implicit type conversion (required by the comparison).

Similarly, the ceiling function needs to be adjusted for positive fractional values.

## i= int(fp); if (i < fp) i++;Using the code

A faster and correct solution is obtained by shifting the values before casting, to make them positive. For instance, assuming all your values fit in the range of a short, you will use:

i= (int)(fp + 32768.) - 32768;

That costs a floating-point add, a typecast and an integer add. No branch.

The ceiling function is derived by using the property floor(-fp) = -ceiling(fp):

## i= 32768 - (int)(32768. - fp);Points of Interest

I benchmarked the (int)floor/ceil functions, the comparison-based and the shifting-based expressions by running them 1000 times on an array of 1000 values in range -50..50. Here are the times in nanoseconds per call.

Floor:

• Standard function: 24 ns
• Comparison based:   14 ns
• Shifting based:   2.6 ns

Ceiling:

• Standard function: 24 ns
• Comparison based:   14 ns
• Shifting based:   2.8 ns

This clearly shows that it is worth to use the shifting alternatives.

## History

• Second version, simpler comparison-based version and ceiling handled.

## About the Author

 CEO VISION fOr VISION Belgium
I fell into applied algorithmics at the age of 16 or so. This eventually brought me to develop machine vision software as a professional. This is Dreamland for algorithm lovers.

 Pro

## Comments and Discussions

 First Prev Next
 Message Closed 24-Jul-17 20:57 histogenetics 24-Jul-17 20:57
 A piece of warning YvesDaoust4-Feb-14 4:13 YvesDaoust 4-Feb-14 4:13
 Testbench code please... Albert Holguin26-Dec-13 6:11 Albert Holguin 26-Dec-13 6:11
 Re: Testbench code please... YvesDaoust30-Dec-13 0:02 YvesDaoust 30-Dec-13 0:02
 Re: Testbench code please... Albert Holguin30-Dec-13 4:10 Albert Holguin 30-Dec-13 4:10
 Really Geeky. But loved it! Member 1038982125-Dec-13 9:13 Member 10389821 25-Dec-13 9:13
 Re: Really Geeky. But loved it! YvesDaoust29-Dec-13 23:36 YvesDaoust 29-Dec-13 23:36
 Nice! Volynsky Alex23-Dec-13 9:22 Volynsky Alex 23-Dec-13 9:22
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Sep-17 21:42 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.