New answers tagged

2

Since $0 \leq k_i < n$, as long as $i$ is not too large, we will have $0 \leq k_i + 2i+1 < 2n$. Therefore you can compute the modulo by checking whether $k_i+2i+1 \geq n$, and if so, subtracting $n$. This works as long as $(n-1) + (2i+1) < 2n$, that is, as long as $i < n/2$. Usually $n$ is very large, and so we are never going to perform $n/2$ ...


1

(Can't leave a comment, unfortunately.) I'm having the same issue. Here's the diagram (sorry, it's messy): I've also found this on the web: The algorithm to subtract two binary numbers using 2’s complement is explained as following below − Take 2’s complement of the subtrahend Add with minuend If the result of above addition has carry bit 1, then it is ...


Top 50 recent answers are included