Click here to Skip to main content
12,504,984 members (62,847 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

19.2K views
11 bookmarked
Posted

Fast floor/ceiling functions

, 24 Dec 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
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. 

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.

You may also be interested in...

Pro
Pro

Comments and Discussions

 
QuestionA piece of warning Pin
YvesDaoust4-Feb-14 4:13
memberYvesDaoust4-Feb-14 4:13 
QuestionTestbench code please... Pin
Albert Holguin26-Dec-13 6:11
memberAlbert Holguin26-Dec-13 6:11 
AnswerRe: Testbench code please... Pin
YvesDaoust30-Dec-13 0:02
memberYvesDaoust30-Dec-13 0:02 
GeneralRe: Testbench code please... Pin
Albert Holguin30-Dec-13 4:10
memberAlbert Holguin30-Dec-13 4:10 
QuestionReally Geeky. But loved it! Pin
Member 1038982125-Dec-13 9:13
memberMember 1038982125-Dec-13 9:13 
AnswerRe: Really Geeky. But loved it! Pin
YvesDaoust29-Dec-13 23:36
memberYvesDaoust29-Dec-13 23:36 
QuestionNice! Pin
Volynsky Alex23-Dec-13 9:22
memberVolynsky Alex23-Dec-13 9: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.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160919.1 | Last Updated 24 Dec 2013
Article Copyright 2013 by YvesDaoust
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid