algorithm - 使用有限算术运算符集的 Ceil 函数

Question

ceil(2.12) = 3是否可以仅使用几个可用的算术运算来计算上限（例如）：* - + / 即没有强制转换和其他软件技巧，只使用除法/mul/sub/addition 和比较运算符？

说明：

• 复杂性很重要，但我很高兴听到任何解决方案。
• 模数不可用。
• 价值观是积极的。
• 运算不是四舍五入的。
• 我所说的软件技巧是指 mod、位级操作等。

基本上我有一个系统，它允许将表达式分配给变量，其中表达式只能包含上述 4 个算术运算、比较和循环。例如

var x = if (A * (1.434 + 0.4325)) > 54.4534) 则为 45.6 否则为 43.435

我想做

变量 x = CEIL(...)

Answer 1

这是可能的，但不要指望任何惊人的表现。最简单的算法 ( th(x)) 是：

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

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

您可以通过二分搜索 ( ) 做得更好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