How to use modulo when denominator is out of unsigned long long int bounds?

Question

Given 1 ≤ N ≤ 10¹⁸ and 1 ≤ K ≤ 10¹⁸, how do I do the operation N % K²? The K² (Denominator) goes out of bounds for unsigned long long int when K is near the value 10¹⁸, so I cannot store the value K2.

[How to ask a good question](https://stackoverflow.com/help/how-to-ask) & [Minimal, Reproducible Example](https://stackoverflow.com/help/minimal-reproducible-example) — Trenton McKinney, Aug 07 '19 at 16:56

score 0 · Answer 1 · answered Aug 07 '19 at 16:47

0

You don't really need a bigint library because

if K > 10⁹ then K² > 10¹⁸ > N, hence N % K² = N. No need to calculate K²
if K ⩽ 10⁹ then you can calculate N % (K*K) using the normal uint64_t without overflow

FWIW there's also a 128-bit type in most modern compilers in 64-bit mode. GCC, Clang and ICC call it __int128

See Is there a 128 bit integer in gcc?

answered Aug 07 '19 at 16:47

phuclv

37,963
15
156
475

Well you have to take the exact limit (as in my answer), otherwise you won't get the correct answer in some cases (for ex. if N is 5 × 10^18 and K is 2 × 10^9). – Phil1970 Aug 07 '19 at 17:02
@Phil1970 the condition is that N ⩽ 10¹⁸ so what you said never happens – phuclv Aug 08 '19 at 01:34

score 0 · Accepted Answer · edited Dec 03 '19 at 03:08

Well if K² is bigger than N then N % K² is equal to N.

Example:

253 % 17² = 253 % 289 = 253

Assuming 64-bit unsigned long long, the maximum value that can be squared without overflow is 2³² - 1 which is equal to 0xFFFFFFFF (or 4'294'967'295).

Thus you can simply have the following code:

unsigned long long compute(unsigned long long n, unsigned long long k)
{
    if (k > 0xFFFFFFFF)
    {
        // k² is bigger than n (require more than 64 bits), so the modulo is n
        return n;
    }

     return n % (k * k);
}

How to use modulo when denominator is out of unsigned long long int bounds?

2 Answers2