Click here to Skip to main content
Click here to Skip to main content

Fast floor/ceiling functions

, 24 Dec 2013
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)

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 PinmemberYvesDaoust4-Feb-14 4:13 
QuestionTestbench code please... PinmemberAlbert Holguin26-Dec-13 6:11 
AnswerRe: Testbench code please... [modified] PinmemberYvesDaoust30-Dec-13 0:02 
GeneralRe: Testbench code please... PinmemberAlbert Holguin30-Dec-13 4:10 
QuestionReally Geeky. But loved it! PinmemberMember 1038982125-Dec-13 9:13 
AnswerRe: Really Geeky. But loved it! PinmemberYvesDaoust29-Dec-13 23:36 
QuestionNice! PinmemberVolynsky Alex23-Dec-13 9:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    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 | Mobile
Web04 | 2.8.140721.1 | Last Updated 24 Dec 2013
Article Copyright 2013 by YvesDaoust
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid