Click here to Skip to main content
15,122,149 members
Articles / General Programming / Algorithms
Tip/Trick
Posted 23 Dec 2013

Tagged as

Stats

41.1K views
11 bookmarked

Fast floor/ceiling functions

Rate me:
Please Sign up or sign in to vote.
4.64/5 (7 votes)
24 Dec 2013CPOL2 min read
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:  

C++
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.  

C++
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: 

C++
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):  

C++
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. 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

YvesDaoust
CEO VISION fOr VISION
Belgium 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.

Comments and Discussions

 
QuestionA piece of warning Pin
YvesDaoust4-Feb-14 5:13
MemberYvesDaoust4-Feb-14 5:13 
BugRe: A piece of warning Pin
MrKii20-Mar-18 2:29
MemberMrKii20-Mar-18 2:29 
QuestionTestbench code please... Pin
Albert Holguin26-Dec-13 7:11
professionalAlbert Holguin26-Dec-13 7:11 
AnswerRe: Testbench code please... Pin
YvesDaoust30-Dec-13 1:02
MemberYvesDaoust30-Dec-13 1:02 
GeneralRe: Testbench code please... Pin
Albert Holguin30-Dec-13 5:10
professionalAlbert Holguin30-Dec-13 5:10 
QuestionReally Geeky. But loved it! Pin
Kirk 1038982125-Dec-13 10:13
MemberKirk 1038982125-Dec-13 10:13 
AnswerRe: Really Geeky. But loved it! Pin
YvesDaoust30-Dec-13 0:36
MemberYvesDaoust30-Dec-13 0:36 
QuestionNice! Pin
Volynsky Alex23-Dec-13 10:22
professionalVolynsky Alex23-Dec-13 10:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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