How to use Modulo efficiently?

Question

Im doing a (for myself) very complex task, where i have to calculate the largest possible number of sequences when given a number n of segments.

I found out that the Catalan Number represents this sequences, and i got it to work for n<=32. The results i get should be calculated mod 1.000.000.007. The problem i have is that "q" and "p" get to big for a long long int and i can't just mod 1.000.000.007 before dividing "q" and "p" because i would get a different result.

My question is, is there a really efficient way to solve my problem, or do i have to think about storing the values differently? My limitations are the following: - stdio.h/iostream only - only Integers - n<=20.000.000 - n>=2

#include <stdio.h>

long long cat(long long  l, long long  m, long long  n);

int main(){
    long long  n = 0;
    long long  val;
    scanf("%lld", &n);

    val = cat(1, 1, n / 2);

    printf("%lld", (val));

    return 0;
}

long long  cat(long long  q, long long  p, long long  n){
    if (n == 0) {
        return (q / p) % 1000000007;
    }
    else {
        q *= 4 * n - 2;
    }

    p *= (n + 1);

    return cat(q, p, n - 1);
}

Answer 1

To solve this efficiently, you'll want to use modular arithmetic, with modular inverses substituting for division.

It's simple to prove that, in the absence of overflow, (a * b) % c == ((a % c) * b) % c. If we were just multiplying, we could take results mod 1000000007 at every step and always stay within the bounds of a 64-bit integer. The problem is division. (a / b) % c does not necessarily equal ((a % c) / b) % c.

To solve the problem with division, we use modular inverses. For integers a and c with c prime and a % c != 0, we can always find an integer b such that a * b % c == 1. This means we can use multiplication as division. For any integer d divisible by a, (d * b) % c == (d / a) % c. This means that ((d % c) * b) % c == (d / a) % c, so we can reduce intermediate results mod c without screwing up our ability to divide.

The number we want to calculate is of the form (x1 * x2 * x3 * ...) / (y1 * y2 * y3 * ...) % 1000000007. We can instead compute x = x1 % 1000000007 * x2 % 1000000007 * x3 % 1000000007 ... and y = y1 % 1000000007 * y2 % 1000000007 * y3 % 1000000007 ..., then compute the modular inverse z of y using the extended Euclidean algorithm and return (x * z) % 1000000007.

Answer 2

If you're using gcc or clang and a 64-bit target, there exists a __int128 type. This gives you extra bits to work with, but obviously only to a point.

Most likely the easiest way to deal with this kind of issue is to use a "bignum" library, i.e. a library that deals with representing and doing arithmetic on arbitrarily large numbers. The arguably most popular open source example is libgmp - you should be able to get your algorithm going quite easily with that. It's also tuned to high performance standards.

Obviously you can reimplement this yourself, by representing your numbers as e.g. arrays of integers of a certain size. You'll have to implement algorithms for doing basic arithmetic such as +, -, *, /, % yourself. If you want to do this as a learning experience that's fine, but there's no shame in using libgmp if you just want to focus on the algorithm you're trying to implement.