Calculating the sum, of the mod Q, position multiplied, sort sequence, of Fibonacci numbers I need to write a program that uses the Fibonacci Sequence to calculate a sum.

The calculation requirement

1: Take the first n Fibonacci numbers (excluding F0)
    S1 = {F1, F2, F3 ..... , Fn}
2: Modulo each Fibonacci number by a positive value Q
    S2 = {A1, A2, A3 ..... , An}  Where Ax = Fx % Q
3: Sort the number in S2 (small to large)
    S3 = {C1, C2, C3 ..... , Cn}
4: Calculated the weighted sum:
    S = 1.C1 + 2.C2 + 3.C3 ......... + n.Cn


I tried to use recursion to find out the Fibonacci number and the professor gave hints to me: "use radix sort to sort the sequence".

I tried it but the result is the program run not fast enough. When the program needs to calculate first 5000000 numbers, it will run a very very long time.

Do there exist any algorithms that can make the program the fastest?

#include &lt;iostream&gt;
#include &lt;algorithm&gt;
using namespace std;


int maxbit(int data[], int n) 
{
    int maxData = data[0];      

    for (int i = 1; i &lt; n; ++i)
    {
        if (maxData &lt; data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData &gt;= p)
    {

        maxData /= 10;
        ++d;
    }
    return d;

}
void radixsort(int data[], int n) 
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; 
    int i, j, k;
    int radix = 1;
    for (i = 1; i &lt;= d; i++) 
    {
        for (j = 0; j &lt; 10; j++)
            count[j] = 0;
        for (j = 0; j &lt; n; j++)
        {
            k = (data[j] / radix) % 10; 
            count[k]++;
        }
        for (j = 1; j &lt; 10; j++)
            count[j] = count[j - 1] + count[j]; 
        for (j = n - 1; j &gt;= 0; j--)
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for (j = 0; j &lt; n; j++) 
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete[]tmp;
    delete[]count;
}

int fib(int n) {

    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return (fib(n - 1) + fib(n - 2));

}

int main() {
    int T,n,Q;
    cin &gt;&gt; T;
    while (T--) {
        cin &gt;&gt; n &gt;&gt; Q;
        int* S1 = new int[n];
        int* A = new int[n];
        for (int i = 0; i &lt; n; i++)
            S1[i] = fib(i+1);
        for (int i = 0; i &lt; n; i++)
            A[i] = S1[i] % Q;

        radixsort(A,n);
        for (int i = 0; i &lt; n; i++)
            A[i] = A[i] * (i + 1);
        int sum = 0;
        for (int i = 0; i &lt; n; i++)
            sum += A[i];

        cout &lt;&lt; sum%Q &lt;&lt; endl;
        delete[] A;
        delete[] S1;
    }
    system("pause");
    return 0;
}
Complexity

The main issue with your application is the calculation of the "Fibonacci" number.

Here you are looping over the range [0,n). Each time you are calling fib() it recalculates the Fib values from scratch.

        for (int i = 0; i &lt; n; i++)
            S1[i] = fib(i+1);


The complexity of fib is O(k^n) (Approx). You put this in a loop so your complexity is O(n^n). Which is fine for small fixed amount of numbers (fib is simple and usually n is small (less than 100)). But when n is unbound like your problem this becomes a problem.

Fib is also relatively simple and can be done in O(n).

        S[0] = 1;
        S[1] = 1;
        for (int i = 2; i &lt; n; i++)
            S1[i] = S[i - 1] + S[i - 2];


That's it. Complexity now O(n).

Range

You don't address the problem with range. Thee Fibonacci sequence generates numbers that exceed 64 bits in less than 100 iterations. You don't address this in your code.

Now if we look at the problem statement we modulus everything by Q. So we only need the part of number below Q and thus overflow does not matter.

Now you are thinking I am saying it is a problem but then I say its not a problem. What gives. The problem is that this is not expressed in the code. Somebody reading the code at a later time is going to say this is wrong because you overflow the integers. What you need to to do is explain what you are doing in the code so that a reader knows that overflow is not an issue.

        S[0] = 1;
        S[1] = 1;
        // Note n can be large.
        // And this will can potentially overflow
        // But this is not an issue in this case because .....
        // Place explanation of why it works.
        for (int i = 2; i &lt; n; i++)
            S1[i] = S[i - 1] + S[i - 2];


Separation of concerns

Your code should be divided into parts that do business logic and those that do resource management. These two parts of the code should be separated otherwise things become very complicated quickly.

In your code you are doing both in the main loop. You are doing the calculations and performing all the memory management in the same place.

Your code has STUFF (the business logic) intertwined with the resource management. This is bad design.

// STUFF

    int *tmp = new int[n];
    int *count = new int[10]; 

    // STUFF

    delete[]tmp;
    delete[]count;

// STUFF


Also this is really a very C way of writting the code. In modern C++ we practically never need to deal with pointers as these are handeled by other higher level constructs for us (usually a container or a smart pointer).

In this case we can replace this memory management with a std::vector and achieve the same result.

// STUFF

    std::vector&lt;int&gt; tmp(n);
    std::vector&lt;int&gt; count(10); 

    // STUFF

// STUFF


Sorting (using radex)

The radix sort is fun. If the number of buckets is the same as the range of your elements then you don't actually need to do any sorting.

In your case the range is [0,Q) if Q is a reasonable number you can create Q different buckets. Then you just count the number of each element (rather than tracking each one). This makes the sort O(n).

 std::vector&lt;int&gt;   count(Q);
 for(int loop = 0;loop &lt; n; ++loop) {
     ++count[calcNextFib(loop) % Q];
 }


Naming

You use some very short names for variables.

    int i, j, k;


This makes reading the code very hard. The current best practice is called self documenting code. This is where you use variables names to explain what you are doing thus making the code self documenting without the need for extra variables.

Also don't declare the variables at the top of the function declare them at the point where they are about to be used. This becomes more important when you start using complex objects that have constructors but is a good habit to get into with all variables.

Code Review

Stop doing this.

using namespace std;


Its a bad habbit that will get you in trouble latter in life. Always use the std:: prefix in your code.

(Why is “using namespace std” considered bad practice?)[https://stackoverflow.com/q/1452721/14065)

Passing C-Arrays is frowned upon.

int maxbit(int data[], int n) 


The more standard way is to use `iterators. Pass the begin and end of a section as the parameters. Remember that iterators behave like pointers so it is still relatively easy to write your code with them.

You don't need to write everything from scratch:

    int maxData = data[0];      

    for (int i = 1; i &lt; n; ++i)
    {
        if (maxData &lt; data[i])
            maxData = data[i];
    }


We have a whole library of algorithms that do this:

    auto maxIter = std::max_element(begin , end);
    int maxData  = *maxIter;


A bit of white space vertically to help logically break up the code would be nice:

int main() {
    int T,n,Q;
    cin &gt;&gt; T;
    while (T--) {
        cin &gt;&gt; n &gt;&gt; Q;
        int* S1 = new int[n];
        int* A = new int[n];
        for (int i = 0; i &lt; n; i++)
            S1[i] = fib(i+1);
        for (int i = 0; i &lt; n; i++)
            A[i] = S1[i] % Q;