1
\$\begingroup\$

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 <iostream>
#include <algorithm>
using namespace std;


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

    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= 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 <= d; i++) 
    {
        for (j = 0; j < 10; j++)
            count[j] = 0;
        for (j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; 
            count[k]++;
        }
        for (j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; 
        for (j = n - 1; j >= 0; j--)
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for (j = 0; j < 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 >> T;
    while (T--) {
        cin >> n >> Q;
        int* S1 = new int[n];
        int* A = new int[n];
        for (int i = 0; i < n; i++)
            S1[i] = fib(i+1);
        for (int i = 0; i < n; i++)
            A[i] = S1[i] % Q;

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

        cout << sum%Q << endl;
        delete[] A;
        delete[] S1;
    }
    system("pause");
    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Apart from being too slow, your approach is generally broken because integer overflow can occur at many places. For n>47 or so, the numbers are already wrong before they are reduced modulo Q. \$\endgroup\$ – Martin R Dec 15 '17 at 15:25
  • \$\begingroup\$ the fib sequence exceeds 64 bits at around 100 iterations. Getting to 5 Million iterations is going to be a huge number. But you only need to keep the part of the fib that is under Q (as the rest will not affect the result). \$\endgroup\$ – Martin York Dec 15 '17 at 18:36
  • 1
    \$\begingroup\$ If you have Q buckets. Then your radix sort becomes very simple. You just count the number of elements in each bucket (no actual sort needed). \$\endgroup\$ – Martin York Dec 15 '17 at 18:40
  • 1
    \$\begingroup\$ Your program is inefficient because of the way you calculate fib() When you calculate the fib(n) you recalculate it from scratch. But since you start at 1 and go up. You have already calculate fib(n-1) and the fib(n-2) so rather than re-calculating you can re-use these values. \$\endgroup\$ – Martin York Dec 15 '17 at 18:43
2
\$\begingroup\$

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 < 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 < 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 < 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<int> tmp(n);
    std::vector<int> 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<int>   count(Q);
 for(int loop = 0;loop < 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 < n; ++i)
    {
        if (maxData < 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 >> T;
    while (T--) {
        cin >> n >> Q;
        int* S1 = new int[n];
        int* A = new int[n];
        for (int i = 0; i < n; i++)
            S1[i] = fib(i+1);
        for (int i = 0; i < n; i++)
            A[i] = S1[i] % Q;
\$\endgroup\$
  • \$\begingroup\$ Your argumentation about "overflow does not matter" is unclear to me. First (according to stackoverflow.com/q/16188263/1187415) signed integer overflow is undefined behavior. Second, even if we assume unsigned integers, it does make a difference if you reduce mod 2^32 (or 2^64) before computing the remainder modulo Q. For example, F(50) % 1000 = 25, but F(50) % (2^32) % 1000 = 433. \$\endgroup\$ – Martin R Dec 15 '17 at 20:30
  • \$\begingroup\$ @MartinR Sure. My point is that it needs to be documented so people understand that what is happening is correct for this algorithm. \$\endgroup\$ – Martin York Dec 15 '17 at 21:14
  • \$\begingroup\$ But it does matter. Separating the calculation of the Fibonacci numbers from the % Q reduction gives wrong results. It is wrong in OP's code and in your suggestion. "documenting/explaining that is does not matter" won't help. \$\endgroup\$ – Martin R Dec 15 '17 at 21:18
  • \$\begingroup\$ @MartinR I never described an algorithm of how to do (quite deliberately). My point is simply that it can be done (you don't need to store the whole of each fib point if in the end you are going to modulo it) BUT more importantly it needs to be documented. \$\endgroup\$ – Martin York Dec 15 '17 at 23:21
0
\$\begingroup\$

Slow Running Time

The recursive function calculating Fibonacci:

int fib(int n) {

    if (n == 0)
        return 0;      
    if (n == 1)
        return 1;

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

}

Is "tree recursive" and therefore does a lot of extra work. Tree Recursion is described in The Structure and Interpretation of Computer Programs. Section 1.2.2 has a very helpful illustration that shows how tree recursive algorithms wind up performing substantially more work than is necessary.

Remarks

People often describe Structure and Interpretation of Computer Programs (often called "SICP") as a book about the language Scheme. It isn't. It is a book about computer programming and probably worth reading for many programmers. It just uses Scheme because Scheme is both powerful and easy to use. For example, SICP does not dive into Scheme's Macro system.

It is also worth looking at section 1.2.1 on Linear Recursion and Iteration. SICP is a reasonable introduction to the way good recursive algorithms can be written.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.