6

ceil(2.12) = 3いくつかの算術演算のみを使用して上限 (例: ) を計算することは可能* - + / ですか?つまり、キャストやその他のソフトウェアのトリックを使用せずに、除算/mul/sub/addition および比較演算子のみを使用しますか?

説明:

  • 複雑さは重要ですが、解決策があれば喜んでお聞きします。
  • モジュラスは利用できません。
  • 値は正です。
  • 操作は丸められません。
  • ソフトウェアのトリックとは、mod、ビットレベルの操作などを意味していました。

基本的に、式に上記の4つの算術演算、比較、およびループのみを含めることができる変数に式を割り当てることができるシステムがあります。例えば

var x = (A * (1.434 + 0.4325)) > 54.4534) の場合 45.6 それ以外の場合 43.435

そして私はやりたい

var x = CEIL(...)

4

1 に答える 1

7

可能ですが、驚くべきパフォーマンスは期待しないでください。最も単純なアルゴリズム ( 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
于 2013-03-04T12:48:21.760 に答える