Funkcja sufowa z użyciem ograniczonego zestawu operatorów arytmetycznych

Question

Czy jest możliwe obliczenie pułapu (np. ceil(2.12) = 3) z tylko kilkoma operacjami arytmetycznymi: * - + / I.e. bez castingu i innych sztuczek programistycznych, używając tylko operatorów podziału/mul/sub/dodawania i porównywania?

Wyjaśnienia:

• Złożoność jest ważne, ale będę zadowolony, aby usłyszeć żadnych rozwiązań.
• Moduł niedostępny.
• Wartości są dodatnie.
• Operacje nie zaokrąglają.
• Przez sztuczek oprogramowania Chciałem Mod, manipulacje na poziomie nieco itd

Zasadniczo mam system, który umożliwia przypisanie do zmiennych zwrotów gdzie wyrażenie może zawierać tylko powyższą operację arytmetyczną 4, porównań i pętle. Na przykład.

var x = if (A * (1,434 + 0,4325))> 54,4534), a następnie 45,6 jeszcze wtedy 43,435

i chciałbym zrobić

var x = CEIL (...)

Answer 1

Jest to możliwe, ale nie spodziewaj się niesamowitej wydajności. Najprostszy algorytm (th(x)) wynosi:

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

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

można zrobić lepiej poprzez poszukiwanie binarnym (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