How does this $\lfloor{\frac{qm[i] + \lfloor\frac{t+1}{2}\rfloor}{t}\rfloor}$ round up in case of a tie?

92 Views Asked by At

There is a code that is supposed to multiply a vector by $\lfloor q/t\rfloor$. It says this:

        // Coefficients of plain m multiplied by coeff_modulus q, divided by plain_modulus t,
        // and rounded to the nearest integer (rounded up in case of a tie). Equivalent to
        // floor((q * m + floor((t+1) / 2)) / t).

Or, if $m$ is a vector, we have this:

$$\lfloor{\frac{qm[i] + \lfloor\frac{t+1}{2}\rfloor}{t}\rfloor}$$

on each component.

What is the $\lfloor\frac{t+1}{2}\rfloor$ about? I suspect it's for round up in case of a tie, but I don't see why.

$$\lfloor{\frac{qm[i] + \lfloor\frac{t+1}{2}\rfloor}{t}\rfloor} = \lfloor{\frac{qm[i] }{t} + \frac{\lfloor\frac{t+1}{2}\rfloor}{t}\rfloor} = \lfloor{\frac{qm[i] }{t} + \frac{\lfloor\frac{t+1}{2}\rfloor}{t}\rfloor}$$

Well, $\lfloor\frac{t+1}{2}\rfloor$ means that $t+1 = 2q_1 + r$ for $r<2$, where $\lfloor\frac{t+1}{2}\rfloor=q_1$. If we want to know the result of $q_1/t$ we can divide everything by $t$:

$$\frac{t+1}{t} = 2\frac{q_1}{t} + \frac{r}{t}\implies 2\frac{q_1}{t} = \frac{t+1}{t}-\frac{r}{t} = \frac{t+1-r}{t}\implies \frac{q_1}{t} = \frac{t+1-r}{2t}$$

but I don't see what happens next.