0

As the title suggests, I want to know how to perform the division operation and modular operation without any overflow.

Currently, I'm calculate it by dividing 2^63 by an random integer N, then doubling the value, and adding 1 to the value if (2^63 % N)<<1 is larger than the N.

int64 div, mod, N;
...
div = ((1<<63) / N) << 1;
mod = ((1<<63) % N) << 1;

if (mod >= N){
    div++;
    mod -= N;
}

As you can see, this process is very complicated, and it doesn't seem to be the optimal way.

Is there some more effective way to calculate it?

(I am a student living in Korea, so I am asking questions with the help of a translator. Please understand even if my English is not good enough.)

KMS studio
  • 1
  • 1
    Are you having performance issues with this code? – klutt Sep 05 '22 at 16:22
  • 3
    `1<<63` is undefined behaviour (unless your `int` is larger than 64 bits). You need `1ull<<63`. – ikegami Sep 05 '22 at 16:24
  • What values can `N` have? I know it's random, but what is the min and max value? – klutt Sep 05 '22 at 16:26
  • On x86-64 systems, the modulus and the division are computed using only 1 instruction (known to be slow though). The thing is the division is probably the bottleneck and not avoidable in the general case. What are typical values for N? Is N random distribution uniform? – Jérôme Richard Sep 05 '22 at 16:30
  • The marked duplicate is for an unsigned type. So, to use its solution for a signed type, cast to `uint64_t`: `- (uint64_t) n / (uint64_t) n + 1`. If negative numbers need to be supported and simply negating before and after is insufficient, it might be worth reopening this. – Eric Postpischil Sep 05 '22 at 16:54

0 Answers0