使用有限的一组算术运算符的Ceil函数

Question

是否有可能仅用几个算术运算就可以计算出一个上限（例如ceil(2.12) = 3）：* - + / 即，没有投射和其他软件技巧，只使用分区/多分区/子/添加和比较运算符？

澄清：

• 复杂性是很重要的，但我会很高兴听到任何解决方案。
• 模量不可用。
• 数值是正数。
• 操作不是四舍五入。
• 通过软件招数我的意思是模，位级操作等

基本上我有一个系统，它允许到变量，其中表达式可以包含仅由上述4算术运算，比较，和循环分配表达式。例如。

变种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