what is precalculation and how does it work?

general
1

I see lot of people mention precalculation but I have no idea how it works. I know they calculate some values and then they just use them but… that means the timer is started when they finish reading the input, how does that does not affect the resulting time of their answers? May someone explain me? Thanks in advance

1 Like
2

Hello @cybuster

You have misunderstood what pre-calculation means. I shall try to explain with an example.

Question

Write a program to print the nth prime number for a given n.

Input

First line of input contains a number t. Then t lines follow, each one containing an n.

Output

For each of the test cases, output the nth prime number.

Constraints

1 <= t <= 5000

1 <= n <= 1000

Sample Input

6

3

5

1

3

2

4

Sample Output

5

11

2

5

3

7

Suppose you are writing a function int nthPrime(int n) that returns the nth prime. That function will look something like this:

int nthPrime(int n)
{
    int count = 0;
    for (i = 2; ; ++i)
    {
        if (isPrime(i) == true)
        {
            ++count;
        }
        if (count == n)
        {
            return i;
        }
    }
}

Now, from the constraints, it is obvious that a particular value of n can repeat (n can take only 1000 values, but there can be 5000 test cases, so some of the numbers must repeat). Imagine this worst case scenario input:

5000

1000

1000

.

. // 1000 is repeated 5000 times

.

1000

The answer for this test case will be

7919

7919

.

. // 7919 is repeated 5000 times

.

7919

Now, consider our function. For each test case, when we are passing the value of n (which is 1000), it finds the 1000th prime number (which is 7919). So, the for loop will run 7918 times (loop starts at 2). Ignoring the time required for the isPrime function used, we can conclude that the time takes is directly proportional to 7918. Let us call it 7918 units (whatever this unit be). Now, this is repeated 5000 times. So, total time taken will be around 5000 * 7918 (= 39590000) units.

Here, we are calculating the required values each and every time we need it.

Now consider another method of solving this problem – using pre-calculation.

We will have a function init, that will calculate all 1000 primes and store it in an array. Then, the function nthPrime simply returns the number from the corresponding index in that array.

It looks something like this:

int primes[1000];

void init()
{
    int count = 0;
    for (i = 2; ; ++i)
    {
        if (isPrime(i) == true)
        {
            primes[count] = i;
            ++count;
        }
    }
}

int nthPrime(int n)
{
    return primes[n - 1];
}

Here, we call the init function even before we start taking inputs. So, the init function takes about 7918 units of time. Now, our nthPrime function will take only 1 unit of time. So, total time taken for 5000 test cases will be around 7918 + 5000 (= 12918) units. This one is about 39590000 / 12918 (~ 3000) times faster than the previous solution. In fact, considering the complexity of the isPrime function as well, the total speed up obtained using precalculated values is very much than computing values as and when required.

Now, the timer starts not just before starting to take input. Timer starts at the very beginning of the execution of your program. So everything you are doing in your program will add to the execution time of your program. Precalculation is usually used when you will be needing to calculate some fairly easily calculable values a lot of times.

2 Likes