Is there a way to rewrite $L = \left\lceil \frac{\sqrt{v-4 \times N}-1}{4} \right\rceil$ without the ceiling function?

Question

$$L = \left\lceil \frac{\sqrt{v-4 \times N}-1}{4} \right\rceil$$

This is a line in my program but I cannot get ceil() to work in GMP, so I'd like to approach this mathematically and just rewrite it so it doesn't need ceil().

Answer 1

You can use the floor with the difference of the desired quantity and a sufficiently large integer. In particular here we know:

$$ v > \frac{\sqrt{v-4 \times N}-1}{4} $$

Therefore:

$$ L = \left\lceil \frac{\sqrt{v-4 \times N}-1}{4} \right\rceil = v - \left\lfloor v - \frac{\sqrt{v-4 \times N}-1}{4} \right\rfloor $$

'Nuff said? There are other ways to do it, but you have $v$ on hand and this is probably the fewest additional operations (and avoids any case logic). Certainly worth a comment in the code so you don't have a long moment of confusion months down the road...