Ceil function using limited set of arithmetic operators

Question

Is it possible to calculate a ceiling (e.g ceil(2.12) = 3) with only a few arithmetic operations available: * - + / I.e. without casting and other software tricks, only using division/mul/sub/addition and comparison operators?

Clarifications:

• Complexity is important, but I will be glad to hear any solutions.
• Modulus not available.
• Values are positive.
• Operations are not rounding.
• By software tricks I meant mod, bit level manipulations, etc.

Basically I have a system which allows assigning expressions to variables where expression can contain only the above 4 arithmetic operation, comparisons, and loops. E.g.

var x = if (A * (1.434 + 0.4325)) > 54.4534) then 45.6 else then 43.435

and I would like to do

var x = CEIL(...)

Answer 1

It is possible, but don't expect any amazing performance. The simplest algorithm (th(x)) is:

frac = x;
while(frac<0) frac+=1;
while(frac>=1) frac-=1;

if(frac>0) return x-frac+1;
else return x;

You can do better via binary search (th(log x)):

lower = 0;
upper = 0;
if(x>0){
  upper = 1;
  while (x > upper) upper *= 2;
}else if(x<0){
  lower = -1;
  while (x > lower) lower *= 2;
}

while(upper-lower > 1){
  //mid is guaranteed to be integer, since the upper-lower is a power of two
  mid = (upper+lower)/2; 
  if(x > mid) lower = mid;
  else if(x < mid) upper = mid;
  else return mid;
}

return upper; // lower for floor