Funzione Ceil utilizzando un numero limitato di operatori aritmetici

Question

È possibile calcolare un massimale (ad esempio ceil(2.12) = 3) con solo poche operazioni aritmetiche disponibili: * - + / I.e. senza casting e altri trucchi del software, utilizzando solo gli operatori divisione/mul/sub/addizione e confronto?

Chiarimenti:

• La complessità è importante, ma sarò lieto di sentire alcuna soluzione.
• Modulo non disponibile.
• I valori sono positivi.
• Le operazioni non sono arrotondate.
• Con trucchi software che significava mod, manipolazioni livello di bit, ecc

Fondamentalmente ho un sistema che permette di assegnare le espressioni di variabili in cui espressione può contenere solo il sopra 4 operazione aritmetica, i confronti, e loop. Per esempio.

var x = if (A * (1.434 + 0,4325))> 54,4534) quindi il 45,6 altro allora 43,435

e vorrei fare

var x = CEIL (...)

Answer 1

È possibile, ma non aspettatevi prestazioni sorprendenti. L'algoritmo più semplice (th(x)) è:

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

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

si può fare meglio con ricerca binaria (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