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

Question

是否可以仅使用少量可用的算术运算来计算上限(例如 ceil(2.12) = 3):* - +/IE。没有强制转换和其他软件技巧，仅使用除法/乘法/减法/加法和比较运算符？

说明:

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

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

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

我想做

var 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