Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!dogie.macc.wisc.edu!uwvax!astroatc!mcdaniel
From: mcdaniel@astroatc.UUCP (Tim McDaniel)
Newsgroups: comp.lang.c
Subject: ceil(x/y), portably
Message-ID: <2796@astroatc.UUCP>
Date: 8 Sep 89 00:23:14 GMT
Reply-To: mcdaniel@astroatc.UUCP (Tim McDaniel)
Organization: Astronautics, Advanced Tech. Center, Madison, WI
Lines: 63

Recently I thought about how to compute
        ceil(x/y)
portably, where y != 0 and x and y are integers.  "ceil(x/y)" means
"the least integer >= x/y", where "/" means real (not integer)
division here.

I was lead to this topic by seeing (essentially)
        int howmany(int x, int y) { return (x+y-1)/y; }
        int roundup(int x, int y) { return (x+y-1)/y*y; }
howmany(x,y) is supposed to compute ceil(x/y), but it can overflow for
large x or y, even if x or y were unsigned.  Furthermore, it doesn't
work all the time.  If x=5 and y=-4,
        ceil(5/-4) is ceil(-1.25) is supposed to be -1
but     (5+(-4)-1)/-4 == 0/-4 == 0

I then considered
        int howmany(int x, int y) { return (x-1)/y+1;   }
but it can underflow, and still doesn't work for x=5 and y=-4.

A further complication is that pANS C does not define integer division
precisely.  All that is required is that
        (a/b)*b + a%b == a
and     absolute value(a%b) < b.
For instance, either of two cases can arise, as long as the machine is
consistent:
        5/-4 == -1 and 5%-4 == 1        (more common)
or      5/-4 == -2 and 5%-4 == -3       (less common)

I went back to a version of the original definition for positive x, y:
        ceil(x/y) is x div y         if x mod y == 0
                  is x div y + 1     otherwise
I considered x=5 or -5, and y=4 or -4, and derived the function
        int howmany(int x, int y)
                {
                if (y >= 0)
                        return x/y + (x%y > 0);
                else
                        return x/y + (x%y < 0);
                }
        int roundup(int x, int y) { return howmany(x,y)*y; }

If y is an integral power of 2, all the "/"s and "%"s can be replaced
throughout by appropriate shifts and masks, even if x can be negative.

There can still be overflow.  For instance, on a 2's complement
machine, INT_MIN < -INT_MAX, so if x=INT_MIN, y=-1, the new "howmany"
overflows.  However, it's impossible to represent "ceil(x/y)" in that
case (unles "long" or "long long" helps), so "howmany" can hardly get
the correct result.

Some might complain that the new "howmany" is much slower than the
old.  However, on a heavily pipelined machine like the Astronautics
ZS-1 (plug plug), the "/" and the "%" almost completely overlap,
taking about as much time as the "/" in the original "howmany".
Furthermore, the original didn't always work.  If you remove the
requirement that it work, I'll use
        int howmany(int x, int y) { exit(0); }
which causes great program execution time.
-- 

\    Tim McDaniel       "Tim, the Bizarre and Oddly-Dressed Enchanter"
 \   Internet: mcdaniel%astroatc.uucp@cs.wisc.edu
/ \  USENET:   ...!ucbvax!uwvax!astroatc!mcdaniel