Vectors

Pages: 12
seatea (37)
Hi!

Imagine having a function like the following:

1
2
3
4
5
6
7
8
9
10
11
 
typedef unsigned long long long_type;

long_type fibonacciIteration(size_t nthNumber) {
    size_t x = 0, y = 1, z = 0;
    for (size_t i = 0; i < nthNumber; i++) {
        z = x + y;
        x = y;
        y = z;
    }
    return x;
}


How do you get the results of this function in to a vector? Imagine having a struct like this:

1
2
3
4
 
struct Stats {
    std::string type;
    std::vector<long_type> values;
};


I'm trying to use push_back(); but I can only get one result out, and I want to print every fifth calculation by the fibonacci function. My code so far looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
#include <iostream>
#include <string>
using namespace std;
#include <iostream>
#include <chrono>
#include <limits>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>

typedef unsigned long long long_type;

struct Stats {
    std::string type;
    std::vector<long_type> values;
    long_type nanosec=0, microsec=0, millisec=0;
    double sec=0;
};

//------------------------------------------------------------------------------
// Function prototypes
//------------------------------------------------------------------------------
long_type fibonacciIteration(size_t nthNumber);
std::vector<Stats> fibonacciTimer(size_t nthNumber);

size_t subMenu();
void showMenu();

//------------------------------------------------------------------------------
// int main
//------------------------------------------------------------------------------
int main()
{
    bool AGAIN = true;
    size_t nthNumber;
    do
    {
        showMenu();
        char choice;
        cout << endl << "Make your choice: ";
        cin >> choice;

        switch (choice)
        {
            case '1' :  nthNumber = subMenu();
                        fibonacciTimer(nthNumber);
                        break;

            case '2' :
            case 'q' :
            case 'Q' :  AGAIN = false;
                        break;

            default : break;
        }

    } while (AGAIN);
    return 0;
}

//------------------------------------------------------------------------------
// Name: subMenu
//------------------------------------------------------------------------------
void showMenu()
{
    cout << endl;
    cout << "=====================" << endl;
    cout << "===== MAIN MENU =====" << endl;
    cout << "1. Measure" << endl;
    cout << "2. Timer - Test only" << endl;
    cout << "2. Print - Test only" << endl;
    cout << "4. Exit" << endl;
    cout << "=====================" << endl;
    cout << "=====================" << endl;
}


//------------------------------------------------------------------------------
// Name: subMenu
//------------------------------------------------------------------------------
size_t subMenu()
{
    size_t nthNumber;
    cout << "Choose your number: ";
    cin >> nthNumber;
    return nthNumber;
}

//------------------------------------------------------------------------------
// Name: fibonacciIteration
//------------------------------------------------------------------------------
long_type fibonacciIteration(size_t nthNumber) {
    size_t x = 0, y = 1, z = 0;
    for (size_t i = 0; i < nthNumber; i++) {
        z = x + y;
        x = y;
        y = z;
    }
    return x;
}

//------------------------------------------------------------------------------
// Name: fibonacciTimer
//------------------------------------------------------------------------------
std::vector<Stats> fibonacciTimer(size_t nthNumber)
{
    std::vector<Stats> tempVector;
    bool AGAIN = true;

    do
    {
        Stats Iteration;
        Iteration.type = "Iteration";
        auto timeStart = std::chrono::high_resolution_clock::now();

        do
        {
            Iteration.values.push_back(fibonacciIteration(nthNumber));

            for (size_t i = 0; i < Iteration.values.size(); i++)
            {
                cout << Iteration.type << " ";

                cout << " " << nthNumber << "'th value is: ";

                if (i % 5 == 0)
                {
                    cout << Iteration.values[i] << endl;
                }
            }

        } while (fibonacciIteration(nthNumber) <= 0);

        auto timeStop = std::chrono::high_resolution_clock::now();
        long_type duration = std::chrono::duration_cast<std::chrono::microseconds>(timeStop - timeStart ).count();
        tempVector.push_back(Iteration);
        cout << "The duration of this task took: " << duration << " microseconds." << endl;
        AGAIN = false;

    } while (AGAIN);


    return tempVector;
}


Output right now is:


=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
2. Print - Test only
4. Exit
=====================
=====================

Make your choice:1
Choose your number:9
Iteration  9'th value is: 34
The duration of this task took: 1577 microseconds.


What I want is something more like:


Iteration 30’th value: 832040
Iteration 25’th value: 75025
Iteration 20’th value: 6765
Iteration 15’th value: 610
Iteration 10’th value: 55
Iteration 5’th value: 5
Iteration 0’th value: 0
Last edited on
JLBorges (13770)
> How do you get the results of this function in to a vector?

Something along these lines, perhaps: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include <iostream>
#include <vector>
#include <limits>
#include <iomanip>

using ullong = unsigned long long ;
constexpr ullong max_val = std::numeric_limits<ullong>::max() ;

void push_next_fib( std::vector<ullong>& fibs )
{
    const auto sz = fibs.size() ;
    if( sz == 0U ) fibs.push_back(0) ; // first fibonacci number
    else if( sz == 1U ) fibs.push_back(1) ; // second fibonacci number

    else // compute and push_back the next fibonacci number
    {
        const auto last = fibs.back() ; // last number so far
        const auto prev = fibs[sz-2] ; // the one previous to that
        
        // sanity check
        if( (max_val-last) >= prev ) fibs.push_back(last+prev) ;
        else throw "next fib number is too big for unsigned long long" ;
    }
}

// may throw if n is too large 
std::vector<ullong> first_n_fibs( std::size_t n )
{
    std::vector<ullong> fibs ;
    while( fibs.size() < n ) push_next_fib(fibs) ;
    return fibs ;
}

int main()
{
    // compute and print the first 80 fibonacci numbers

    const auto fibs = first_n_fibs(80) ; 

    for( std::size_t i = 0 ; i < fibs.size() ; ++i )
    {
        std::cout << std::setw(20) << fibs[i] ;
        if( i%5 == 4 ) std::cout << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/f1542f23030c4647
seatea (37)
That is pretty much what I want, I think, but I'm just starting out in C++, so that code is way too advanced for me!

I was picturing something like this in my head:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
std::vector<Stats> fibonacciTimer(size_t nthNumber)
{
    std::vector<Stats> tempVector;
    bool AGAIN = true;

    do
    {
        Stats Iteration;
        Iteration.type = "Iteration";
        auto timeStart = std::chrono::high_resolution_clock::now();
        Iteration.values.push_back(fibonacciIteration(nthNumber));

        do
        {
            for (size_t e : Iteration.values)
            {
                cout << Iteration.type;
                cout << " " << nthNumber << "'th value: ";
                cout << e << " " << endl;
                
                Iteration.values.push_back(fibonacciIteration(nthNumber - 1 until nthNumber == 0));
                cout << USER INPUT (nthNumber) VALUE AND THEN EVERY FIFTH SEQUENCE FROM THERE UNTIL 0 << endl;

            }

        } while (fibonacciIteration(nthNumber) == 0);

        auto timeStop = std::chrono::high_resolution_clock::now();
        long_type duration = std::chrono::duration_cast<std::chrono::microseconds>(timeStop - timeStart ).count();
        tempVector.push_back(Iteration);
        cout << "The duration of this task took: " << duration << " microseconds." << endl;
        AGAIN = false;

    } while (AGAIN);


    return tempVector;
}


With the bold being my pseudo code for what I'm trying to get!

I find it really tricky.
JLBorges (13770)
Does this look easier?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <iostream>
#include <vector>
#include <iomanip>

using ullong = unsigned long long ;

// invariant: the nth fibonacci number is within the range of ullong
std::vector<ullong> first_n_fibs( std::size_t n )
{
    std::vector<ullong> fibs ;

    ullong x = 0 ;
    ullong y = 1 ;
    ullong z = 0 ;

    while( fibs.size() < n )
    {
        fibs.push_back(z) ;

        z = x+y ;
        x = y ;
        y = z ;
    }

    return fibs ;
}

int main()
{
    const auto fibs = first_n_fibs(80) ;

    for( std::size_t i = 0 ; i < fibs.size() ; ++i )
    {
        std::cout << std::setw(20) << fibs[i] ;
        if( i%5 == 4 ) std::cout << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/bbbf5d42dc2d2018
seatea (37)
For me, no, sorry!

I'm following a pseudo code that looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
REPEAT {
DETERMINE type of approach
SET Stats.type
MARK start time
REPEAT {
CALL appropriate Fibonacci function
ADD Fibonacci value to Stats container
FOR EACH 5th sequence OUTPUT information on screen**
} IF iteration IS NOT 0*
MARK end time
CALCULATE duration of all needed formats
SET duration for relevant Stats members
} FOR each Fibonacci approach
RETURN container filled with two Stats objects


And I don't really understand how to implement your code to make it work with that. But it's probably doable if you know what you are doing, haha.

I think I've done the first 7 lines correctly, but it's the output of the fibonacci sequences that confuses me.

The output in the end should look like this, if user input is 30:


Iteration 30’th value:  832040
Iteration 25’th value:   75025
Iteration 20’th value:    6765
Iteration 15’th value:     610
Iteration 10’th value:      55
Iteration 5’th value:        5
Iteration 0’th value:        0
Last edited on
JLBorges (13770)
> I'm following a pseudo code that looks like this:
> ...
> REPEAT {
> CALL appropriate Fibonacci function
> ...
> }

Note that this would be somewhat inefficient with your current fibonacciIteration function;
for each call it would need to start from zero all over again.

May be, that is intended; and something like this is what is expected: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
#include <iostream>
#include <string>
#include <vector>

typedef unsigned long long long_type;

struct Stats {

    std::string type;
    std::vector<long_type> values;
    // time etc. ...
};

long_type fibonacciIteration( std::size_t nthNumber ) {

    long_type x = 0, y = 1, z = 0;

    for (size_t i = 0; i < nthNumber; i++) {

        z = x + y;
        x = y;
        y = z;
    }

    return x;
}

Stats fibonacciTimer( std::string fib_type, std::size_t nthNumber ) {

    // SET Stats.type
    Stats st { fib_type, {} } ;

    // TO DO: MARK start time

    // REPEAT {
    for( std::size_t i = 1 ; i <= nthNumber ; ++i ) {

        // CALL appropriate Fibonacci function
        // ADD Fibonacci value to Stats container
        st.values.push_back( fibonacciIteration(i) ) ;

        // FOR EACH 5th sequence OUTPUT information on screen**
        if( i%5 == 0 ) std::cout << i << ". " << st.values.back() << '\n' ;
    }

    // TO DO: MARK end time, update time in Stats

    return st ;
}

// TO DO: Write a function to implement the second approach

// TO DO: Write a function to do the following
// REPEAT {

    // DETERMINE type of approach
    // call appropriate Fibonacci function: fibonacciTimer or a function with a different approach
    // add the returned Stats object to a vector
// } FOR each Fibonacci approach

// RETURN container (vector) filled with Stats objects
// call this function from main

int main() {

    fibonacciTimer( "fib type", 60 ) ;

}

http://coliru.stacked-crooked.com/a/4d3c00bc8bc2ee47
againtry (2313)
How do you get the results of this function in to a vector?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <vector>

int main()
{
    std::vector< long long> series;
    
    long long f0{0}, f1{1};
    
    series.push_back(f0);
    series.push_back(f1);
    
    size_t last{0};
    
    for(int i = 0; i < 90; i++)
    {
        last = series.size() - 1;
        series.push_back( series.at(last) + series.at(last-1));
    }
    
    for(auto i:series)
    {
        std::cout << i << '\n';
    }
    return 0;
}


0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
Program ended with exit code: 0
againtry (2313)
And:

1
2
3
4
5
6
7
8
 
int counter = 0;
    for(auto i:series)
    {
        if(counter % 5 == 0)
            std::cout << i << '\n';
        
        counter++;
    }


0
5
55
610
6765
75025
832040
9227465
102334155
1134903170
12586269025
139583862445
1548008755920
17167680177565
190392490709135
2111485077978050
23416728348467685
259695496911122585
2880067194370816120
Program ended with exit code: 0
seatea (37)
Thanks for all of your help, guys! Really appreciated!

JLBorges
Stats fibonacciTimer( std::string fib_type, std::size_t nthNumber ) {

// SET Stats.type
Stats st { fib_type, {} } ;


Not allowed to change the input there. fibonacciTimer() should just accept size_t nthNumber. Maybe it's doable without it as well?

againtry
I tried implementing your code to mine and I got somewhere! Could really use some explanations if someones got the time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
//------------------------------------------------------------------------------
// Name: fibonacciTimer
//------------------------------------------------------------------------------
std::vector<Stats> fibonacciTimer(size_t nthNumber)
{
    std::vector<Stats> tempVector;
    bool AGAIN = true;

    do
    {
        Stats Iteration;
        Iteration.type = "Iteration";
        auto timeStart = std::chrono::high_resolution_clock::now();

        do
        {
            Iteration.values.push_back(fibonacciIteration(nthNumber));

            // What are these? Just to get the first 0 and 1's in the series?
            long_type f0{0}, f1{1};                
            Iteration.values.push_back(f0);
            Iteration.values.push_back(f1);

            // Same here, what exactly is this doing?
            size_t last{0};                             

            for(int i = 0; i < nthNumber; i++)
            {
                last = Iteration.values.size() - 1;

                // What am I pushing to Iteration.values here?
                Iteration.values.push_back(Iteration.values.at(last) + Iteration.values.at(last-1)); 
            }
            for (auto i : Iteration.values)
            {
                cout << Iteration.type << " The value of " << nthNumber << " is: " << i << '\n';
            }
        } while (fibonacciIteration(nthNumber) == 0);

        auto timeStop = std::chrono::high_resolution_clock::now();
        long_type duration = std::chrono::duration_cast<std::chrono::microseconds>(timeStop - timeStart ).count();
        tempVector.push_back(Iteration);
        cout << "The duration of this task took: " << duration << " microseconds." << endl;
        AGAIN = false;

    } while (AGAIN);


    return tempVector;
}


This gives me this:

=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
2. Print - Test only
4. Exit
=====================
=====================

Make your choice:1
 Choose your number:6
 Iteration: The value of 6 is: 8
Iteration: The value of 6 is: 0
Iteration: The value of 6 is: 1
Iteration: The value of 6 is: 1
Iteration: The value of 6 is: 2
Iteration: The value of 6 is: 3
Iteration: The value of 6 is: 5
Iteration: The value of 6 is: 8
Iteration: The value of 6 is: 13
The duration of this task took: 9466 microseconds.


How would I make it show this instead:

=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
2. Print - Test only
4. Exit
=====================
=====================

Make your choice:1
Choose your number:6
Iteration: The value of 7 is: 13
Iteration: The value of 6 is: 8
Iteration: The value of 5 is: 5
Iteration: The value of 4 is: 3 
Iteration: The value of 3 is: 2
Iteration: The value of 2 is: 1
Iteration: The value of 1 is: 1 
Iteration: The value of 0 is: 0
The duration of this task took: 9466 microseconds.


Though, I don't want the 7 in this case, so I must have made a mistake somewhere. I just want what the user inputted and down to zero.
Last edited on
againtry (2313)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
// What are these? Just to get the first 0 and 1's in the series?
//YES, IN FACT YOU DON'T EVEN NEED THE 2 VARIABLES,
//JUST PUSH_BACK(0), PUSH_BACK(1)

long_type f0{0}, f1{1};
Iteration.values.push_back(f0);
Iteration.values.push_back(f1);

// Same here, what exactly is this doing?
// JUST INITIALIZES last = 0 TO BE USED LATER - AND ACTUALLY THE
// VARIABLE last ISN'T NEEDED I'LL POST THE REVISED VERSION IN A SECOND

size_t last{0};

for(int i = 0; i < nthNumber; i++)
{
    last = Iteration.values.size() - 1;

    // What am I pushing to Iteration.values here?
    //THE VECTOR STORES ALL VALUES SO FOR THE NEXT (NEW) VALUE IT'S JUST
    //THE SUM OF THE PREVIOUS TWO (THEY'RE ALREADY THERE SO WHY NOT USE THEM!!)
    
    Iteration.values.push_back(Iteration.values.at(last) + Iteration.values.at(last-1));
Last edited on
againtry (2313)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <iostream>
#include <vector>

int main()
{
    std::vector< long long> series;
    
    series.push_back(0);
    series.push_back(1);
    
    for(int i = 0; i < 90; i++)
    {
        series.push_back( series.at(series.size()-1) + series.at(series.size()-2));
    }
    
    for(auto i:series)
    {
        std::cout << i << '\n';
    }
    return 0;
}


0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025
20365011074
32951280099
53316291173
86267571272
139583862445
225851433717
365435296162
591286729879
956722026041
1548008755920
2504730781961
4052739537881
6557470319842
10610209857723
17167680177565
27777890035288
44945570212853
72723460248141
117669030460994
190392490709135
308061521170129
498454011879264
806515533049393
1304969544928657
2111485077978050
3416454622906707
5527939700884757
8944394323791464
14472334024676221
23416728348467685
37889062373143906
61305790721611591
99194853094755497
160500643816367088
259695496911122585
420196140727489673
679891637638612258
1100087778366101931
1779979416004714189
2880067194370816120
4660046610375530309
Program ended with exit code: 0
Last edited on
againtry (2313)
Or 'Fibonacci with the lot' - print every 5th as you go, then print the lot.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <iostream>
#include <vector>

int main()
{
    std::vector< long long> series;
    
    series.push_back(0);
    series.push_back(1);
    
    int counter{0};
    for(int i = 0; i < 90; i++)
    {
        series.push_back( series.at(series.size()-1) + series.at(series.size()-2));
        
        if(counter % 5 == 0)
            std::cout << series.back() << '\n';
        counter++;
    }
    
    
    std::cout << "****\n";
    for(auto i:series)
    {
        std::cout << i << '\n';
    }
    return 0;
}
dhayden (5799)
Please post the actual assignment. There's a whole lot that remains unsaid here. Looking at the pseudo-code you posted:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
REPEAT {
    DETERMINE type of approach
    SET Stats.type
    MARK start time
    REPEAT {
        CALL appropriate Fibonacci function
        ADD Fibonacci value to Stats container
        FOR EACH 5th sequence OUTPUT information on screen**
    } IF iteration IS NOT 0*
    MARK end time
    CALCULATE duration of all needed formats
    SET duration for relevant Stats members
} FOR each Fibonacci approach
RETURN container filled with two Stats objects


Line 2: Are there going to be multiple types of approaches? Does that mean they all need a similar calling interface?
Line 9. What is an "iteration?" When will it be zero? Is "iteration" different from "sequence" on line 8?
Line 11. What are "all needed formats?" I can understand calculating the duration of all needed "approaches" from lines 2 and 6, but in that case you'd only calculate the duration of the current approach here (inside the loop).
Line 14: Return container with 2 stats objects? Why 2? One for each of two "approaches?"

It looks to me like FobonacciIteration might not be required to add values to a vector at all: you're just timing this approach to computing the values, compared to some other approach.

So like I said, please post the actual assignment.
seatea (37)
dhayden
So like I said, please post the actual assignment.


The assignment is to develop a program which measures the execution time of finding fibonacci numbers using both iterative and recursive approaches.

The program needs to be function based and we have two headers; Stats.h and Prototypes.h

Stats.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#ifndef DT018G_STATS_H
#define DT018G_STATS_H

#include <string>
#include <vector>

typedef unsigned long long long_type;

struct Stats {
    std::string type;
    std::vector<long_type> values;
    long_type nanosec=0, microsec=0, millisec=0;
    double sec=0;
};

#endif //DT018G_STATS_H


Prototypes.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#ifndef DT018G_PROTOTYPES_H
#define DT018G_PROTOTYPES_H

#include "Stats.h"
#include <iostream>
#include <chrono>
#include <limits>
#include <iomanip>
#include <fstream>

long_type fibonacciIteration(size_t nthNumber);
long_type fibonacciRecursion(size_t nthNumber);
std::vector<Stats> fibonacciTimer(size_t nthNumber);

void printStats(const std::vector<Stats>& stats);
void writeToFile(const Stats& stats);

void mainMenu();
size_t subMenu();
void showMenu();

#endif //DT018G_PROTOTYPES_H


Int main() is only allowed to call void mainMenu(), that's it.

The functions fibonacciIteration() and fibonacciRecursion() are the two approaches. Both of these function are to be unchanged.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//------------------------------------------------------------------------------
// Name: fibonacciIteration
//------------------------------------------------------------------------------
long_type fibonacciIteration(size_t nthNumber) {
    size_t x = 0, y = 1, z = 0;
    for (size_t i = 0; i < nthNumber; i++) {
        z = x + y;
        x = y;
        y = z;
    }
    return x;
}

//------------------------------------------------------------------------------
// Name: fibonacciRecursion
//------------------------------------------------------------------------------
long_type fibonacciRecursion(size_t nthNumber) {
    if (nthNumber <= 1)
        return nthNumber;
    return fibonacciRecursion(nthNumber - 1) + fibonacciRecursion(nthNumber - 2);
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
REPEAT {
    DETERMINE type of approach
    SET Stats.type
    MARK start time
    REPEAT {
        CALL appropriate Fibonacci function
        ADD Fibonacci value to Stats container
        FOR EACH 5th sequence OUTPUT information on screen**
    } IF iteration IS NOT 0*
    MARK end time
    CALCULATE duration of all needed formats
    SET duration for relevant Stats members
} FOR each Fibonacci approach
RETURN container filled with two Stats objects

*Repeat execution from nthNumber until (and including) 0. If nthNumber to find is 30, then all Fibonacci values within the sequence range of 30...0 will be included.

**The information printed should contain type of approach, sequence and Fibonacci value. The value needs to be printed with right alignment.


mainMenu() should call fibonacciTimer(), and the fibonacciTimer should do the pseudo code above.

The time spent executing the full range of sequences for each Fibonacci approach will be measured and stored in Stats with various precision. A time stamp will mark the start before execution and another time stamp to mark the end when the full range of sequences has been calculated. The duration will be determined simply by subtracting the start time from end time and stored in a Stats structure with values for nanosec, microsec, millisec and sec. Note that the first three members is of type integer long_type
while the last member is a double!

There is also pseudo code for the menus, but I think I have them somewhat done:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Pseudo Code, mainMenu()

REPEAT {
PRINT menu
REPEAT {
user input
} IF input NOT valid
BREAK IF exit
CALL subMenu
CALL fibonacciTimer
CALL printStats
CALL writeToFile
} IF repeat is wanted


1
2
3
4
5
 
Pseudo Code, subMenu() Example output
REPEAT {
user input
} IF input NOT valid
return user input


When all of this is done, fibonacciTimer should return a vector with Stats object to mainMenu() which in turn calls printStats().

printStats() is supposed to print statistical information on the screen, something like this:


Duration of running Fibonacci sequences within the range of 30..0
===================================================================
                  Nanosec   Microsec   Millisec   Sec
Iteration:    4987200       4987             4   0.004
Recursion: 15133700     15133           15   0.015
===================================================================


All information needed should be pulled from the Stats object and at the top of the output there should be a header showing the range of the calculations. (0-30 in this case)
Seconds should be shown without trailing zeroes.

Each line of the table should consist of relevant data found in the Stats object, and based on above requirements the order should be:

stats.type | stats.nanosec | stats.microsec | stats.millisec | stats.sec

The last function is writeToFile:

mainMenu() should have a vector filled with two Stats objects both of which containing a vector of Fibonacci values, one for each sequence. The function writeToFile() accepts one
Stats object as parameter and needs to create a corresponding file containing these values.
Two files shall be created, one for each approach, and their names will consist of a composition between the value of Stats.type and .txt. Both files must be saved in the _Resources directory:

/_Resources/Iteration.txt
/_Resources/Recursion.txt

Both files must have identical contents and the information needs to be stored in conformity with the format: sequence: value.

Requirements

- You may not change or modify existing code, only add to stated entities. This includes the Stats structure which should not contain any methods or overloaded constructors / operators!

- You may create additional functions as deemed necessary.

- You may use as many variables and constants as you wish for the assignment, but variables may only be passed between entities as arguments and return values. Global variables will never be allowed!

- Each Fibonacci sequence calculated needs to be stored in std::vector<long_type> values in relevant Stats object.

- All members of Stats needs to have intended values.

- Every 5th Fibonacci sequence calculated must be printed to the screen in accordance to stated requirements.

- std::chrono must be used to measure time spent for executions.

- Each and every entity (function / struct) needs to have its responsibilities documented, for functions this also includes its full specification (parameters & return value). Place such comments together with declarations (prototypes) in header files.

- Any comments describing implementation needs to be placed in source files together with relevant definition.

- main() may not contain any code besides calling mainMenu():
int main() {
mainMenu();
return 0;
}

That is it! I thought I'd divide it into smaller pieces, but maybe it was stupid not to show you the full assignment!
Last edited on
seatea (37)
Made some progress:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
//------------------------------------------------------------------------------
// Name: fibonacciTimer
//------------------------------------------------------------------------------
std::vector<Stats> fibonacciTimer(size_t nthNumber)
{
    std::vector<Stats> tempVector;
    bool AGAIN = true;

    do
    {
        Stats Iteration;
        Iteration.type = "Iteration";
        auto timeStart = std::chrono::high_resolution_clock::now();

        do
        {
            for(int i = 0; i <= nthNumber; i++)
            {
                Iteration.values.push_back(fibonacciIteration(i));
                cout << Iteration.type << ":" << " The value of " << i << " is: " << Iteration.values[i] << "\n";
            }

        } while (fibonacciIteration(nthNumber) == 0);

        auto timeStop = std::chrono::high_resolution_clock::now();
        long_type duration = std::chrono::duration_cast<std::chrono::microseconds>(timeStop - timeStart ).count();
        tempVector.push_back(Iteration);
        cout << "The duration of this task took: " << duration << " microseconds." << endl;
        AGAIN = false;

    } while (AGAIN);


    return tempVector;
}


Give me output:


=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
2. Print - Test only
4. Exit
=====================
=====================

Make your choice:1
 Choose your number:30
 Iteration: The value of 0 is: 0
Iteration: The value of 1 is: 1
Iteration: The value of 2 is: 1
Iteration: The value of 3 is: 2
Iteration: The value of 4 is: 3
Iteration: The value of 5 is: 5
Iteration: The value of 6 is: 8
Iteration: The value of 7 is: 13
Iteration: The value of 8 is: 21
Iteration: The value of 9 is: 34
Iteration: The value of 10 is: 55
Iteration: The value of 11 is: 89
Iteration: The value of 12 is: 144
Iteration: The value of 13 is: 233
Iteration: The value of 14 is: 377
Iteration: The value of 15 is: 610
Iteration: The value of 16 is: 987
Iteration: The value of 17 is: 1597
Iteration: The value of 18 is: 2584
Iteration: The value of 19 is: 4181
Iteration: The value of 20 is: 6765
Iteration: The value of 21 is: 10946
Iteration: The value of 22 is: 17711
Iteration: The value of 23 is: 28657
Iteration: The value of 24 is: 46368
Iteration: The value of 25 is: 75025
Iteration: The value of 26 is: 121393
Iteration: The value of 27 is: 196418
Iteration: The value of 28 is: 317811
Iteration: The value of 29 is: 514229
Iteration: The value of 30 is: 832040
The duration of this task took: 24392 microseconds.


Which is basically what I want. Question is how I arrange for the numbers in the vector to go from highest to lowest and only output every fifth. If I do the:

1
2
3
4
5
 

if (i % 5 == 0)
{
   cout << whatever << endl;
}


That would mean only 0-5-10-15 gets shown. But if I understand the pseudo code it should be every fifth from what you entered? So if I input 14 it would want the output of:

14
9
4
0

Weeell, some progress at least! Getting there!
Last edited on
Handy Andy (5051)
Hello seatea,

After working with what you started with I came up with this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
//------------------------------------------------------------------------------
// Name: fibonacciTimer
//------------------------------------------------------------------------------
std::vector<Stats> fibonacciTimer(size_t nthNumber)
{
	std::vector<Stats> tempVector;
	bool again = true;
	size_t fibNum{};

	do
	{
		Stats Iteration;
		Iteration.type = "Iteration";
		auto timeStart = std::chrono::high_resolution_clock::now();

		do
		{
			//Iteration.values.push_back(fibonacciIteration(nthNumber));

			for (size_t i = 0, fibNum = nthNumber; i < nthNumber; i++, fibNum--)
			{

				Iteration.values.push_back(fibonacciIteration(fibNum));

				if (i % 5 == 0)
				{
					cout << "\n " << Iteration.type << " " << std::setw(2) << fibNum << "'th value is: ";
					cout << std::setw(6) << Iteration.values[i];
				}
			}
			//temp = fibonacciIteration(nthNumber); // <--- Used for testing.
		} /*while (fibonacciIteration(nthNumber) > 0);*/while (fibNum > 0);

		cout << "\n " << Iteration.type << " " << std::setw(2) << fibNum << "'th value is: ";
		cout << std::setw(6) << 0 << endl;

		auto timeStop = std::chrono::high_resolution_clock::now();

		long_type duration = std::chrono::duration_cast<std::chrono::microseconds>(timeStop - timeStart).count();

		tempVector.push_back(Iteration);

		cout << "\n The duration of this task took: " << duration << " microseconds." << endl;

		again = false;

	} while (again);

	return tempVector;
}


I also changed the "subMenu" function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
//------------------------------------------------------------------------------
// Name: subMenu
//------------------------------------------------------------------------------
int showMenu()
{
	int choice{};

	do
	{
		cout << "\n=====================";
		cout << "\n===== MAIN MENU =====";
		cout << "\n1. Measure";
		cout << "\n2. Timer - Test only";
		cout << "\n3. Print - Test only";
		cout << "\n4. Exit";
		cout << "\n=====================";
		cout << "\n=====================" << endl;

		cout << "\n Make your choice: ";
		std::cin >> choice;

		if (!std::cin)
		{
			std::cerr << "\n    Invalid choice! Must be a number\n";

			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');  // <--- Requires header file <limits>. Clears the input buffer.
		}
		else if (choice < 1 || choice > 4)
			std::cout << "\n    Wrong choice! Try again\n";

	} while (choice < 1 || choice > 4);

	return choice;
}

The comment is a bit misleading. I think you may have meant "showMenu"?

To me returning a valid choice makes more sense than trying to deal with it back where the function was called from.

I also noticed that "fibonacciTimer" returns a vector that is never captured where the function was call from in the switch (case 1) back in main. If you do not need it back in "main" that is fine, but there is no point in returning something that you can not use.

Based on something I read in a different topic I believe this is what was meant.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
switch (choice)
{
	case 1:
		nthNumber = subMenu();
		stats = fibonacciTimer(nthNumber);
		break;

	case 2:
		std::cout << "\n    Not ready yet.\n";
		break;

	case 3:
		std::cout << "\n    Not ready yet.\n";
		break;

	case 4: // <--- Because the menu shows 4 as Exit.
	//case q: // <--- Only you know this is available.
	//case Q: // <--- Only you know this is available.
		again = false;
		break;

	default:
		std::cout << "\n    Invalid Choice! Try again.\n";
		break;
}

Since the call to "showMenu" returns a valid choice the "default" is not really needed. I think I left it because it was there from the start.

Andy
Handy Andy (5051)
Hello seatea,

Should have mentioned that the output I get looks like this:


=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
3. Print - Test only
4. Exit
=====================
=====================

 Make your choice: 1
Choose your number: 30

 Iteration 30'th value is: 832040
 Iteration 25'th value is:  75025
 Iteration 20'th value is:   6765
 Iteration 15'th value is:    610
 Iteration 10'th value is:     55
 Iteration  5'th value is:      5
 Iteration  0'th value is:      0

 The duration of this task took: 5430 microseconds.

=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
3. Print - Test only
4. Exit
=====================
=====================

 Make your choice:


And this:


=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
3. Print - Test only
4. Exit
=====================
=====================

 Make your choice: 1
Choose your number: 14

 Iteration 14'th value is:    377
 Iteration  9'th value is:     34
 Iteration  4'th value is:      3
 Iteration  0'th value is:      0

 The duration of this task took: 3621 microseconds.

=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
3. Print - Test only
4. Exit
=====================
=====================

 Make your choice:

At this time I have not checked the numbers in the second example, but I think it is working correctly.

Andy
dhayden (5799)
IF iteration IS NOT 0*
I had an epiphany: this means that the loop is supposed to go backwards from nthNumber to 0, not forwards.

So the inner loop in fibonacciTimer should look sort of like:
1
2
3
4
5
6
7
8
9
10
 
        do
                cout << Iteration.type;
                cout << " " << nthNumber << "'th value: ";
                cout << e << " " << endl;
                
                long_type value = fibonacciIteration(nthNumber);
                Iteration.values.push_back(value);
                --nthNumber;
                // print every 5th number
        } while (value != 0);
againtry (2313)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <vector>

int main()
{
    std::vector< long long> series;
    
    series.push_back(0);
    series.push_back(1);
    
    std::cout << "Enter required fib number: ";
    int N_TH_FIB;
    std::cin >> N_TH_FIB;
    N_TH_FIB++;
    
    int counter{0};
    while(counter <= N_TH_FIB)
    {
        series.push_back( series.at(series.size()-1) + series.at(series.size()-2));
        counter++;
    }
    
    counter = 0;
    int position{0};
    while(counter < N_TH_FIB)
    {
        position = N_TH_FIB - counter - 1;
        
        if(position == 0 or position % 5 == 4)
        {
            std::cout
            << position << '\t'
            << series.at(position) << '\n';
        }
        counter ++;
    }
    
    return 0;
}
seatea (37)
You guys are the best, eternally grateful!

I looked at all the code you provided and came up with this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
//------------------------------------------------------------------------------
// Name: fibonacciTimer
//------------------------------------------------------------------------------
std::vector<Stats> fibonacciTimer(size_t nthNumber)
{
    std::vector<Stats> stats;

        Stats Iteration;
        Stats Recursion;
        Iteration.type = "Iteration";
        Recursion.type = "Recursion";
        size_t IterationCount{};
        size_t RecursionCount{};

        auto timeStartIteration = std::chrono::high_resolution_clock::now();

            for (size_t i = 0, IterationCount = nthNumber; i <= nthNumber; i++, IterationCount--)
            {
                Iteration.values.push_back(fibonacciIteration(IterationCount));

                if (i % 5 == 0)
                {
                    cout << "\n " << Iteration.type << " " << std::setw(2) << IterationCount << "'th value is: ";
                    cout << std::setw(6) << Iteration.values[i];
                }
            }

        auto timeStopIteration = std::chrono::high_resolution_clock::now();
        long_type durationIteration = std::chrono::duration_cast<std::chrono::microseconds>(timeStopIteration - timeStartIteration).count();

        Iteration.microsec = durationIteration;
        Iteration.millisec = durationIteration/1000;
        Iteration.nanosec = durationIteration*1000;
        Iteration.sec = durationIteration/1000000; //Convert to double somehow

        stats.push_back(Iteration);

        cout << "\n";
        cout << "The duration of this task took: " << Iteration.microsec << " microseconds." << endl;
        cout << "The duration of this task took: " << Iteration.millisec << " milliseconds." << endl;
        cout << "The duration of this task took: " << Iteration.nanosec << " nanoseconds." << endl;
        cout << "The duration of this task took: " << Iteration.sec << " seconds." << endl; //Convert to double somehow?


        auto timeStartRecursion = std::chrono::high_resolution_clock::now();

            for(size_t i = 0, RecursionCount = nthNumber; i <= nthNumber; i++, RecursionCount--)
            {
                Recursion.values.push_back(fibonacciRecursion(RecursionCount));

                if(i % 5 == 0)
                {
                    cout << "\n " << Recursion.type << " " << std::setw(2) << RecursionCount << "'th value is: ";
                    cout << std::setw(6) << Recursion.values[i];
                }
            }

        auto timeStopRecursion = std::chrono::high_resolution_clock::now();
        long_type durationRecursion = std::chrono::duration_cast<std::chrono::microseconds>(timeStopRecursion - timeStartRecursion).count();

        Recursion.microsec = durationRecursion;
        Recursion.millisec = durationRecursion/1000;
        Recursion.nanosec = durationRecursion*1000;
        Recursion.sec = durationRecursion/1000000; //Convert to double somehow

        stats.push_back(Recursion);

        cout << "\n";
        cout << "The duration of this task took: " << Recursion.microsec << " microseconds." << endl;
        cout << "The duration of this task took: " << Recursion.millisec << " milliseconds." << endl;
        cout << "The duration of this task took: " << Recursion.nanosec << " nanoseconds." << endl;
        cout << "The duration of this task took: " << Recursion.sec << " seconds." << endl;

    return stats;
}


I decided to ditch the do-while-loop, was that a dumb move? But looks like it works without it..

My big problem now is to convert the unsigned long long to a double, since seconds in the Stats object is in double.

And how do I print the vector in the printStats later? When I try to print it I only get 0 1..

Output for my code right now:


=====================
===== MAIN MENU =====
1. Measure
2. Timer - Test only
2. Print - Test only
4. Exit
=====================
=====================

Make your choice:1
 Choose your number:30

 Iteration 30'th value is: 832040
 Iteration 25'th value is:  75025
 Iteration 20'th value is:   6765
 Iteration 15'th value is:    610
 Iteration 10'th value is:     55
 Iteration  5'th value is:      5
 Iteration  0'th value is:      0
The duration of this task took: 13960 microseconds.
The duration of this task took: 13 milliseconds.
The duration of this task took: 13960000 nanoseconds.
The duration of this task took: 0 seconds.

 Recursion 30'th value is: 832040
 Recursion 25'th value is:  75025
 Recursion 20'th value is:   6765
 Recursion 15'th value is:    610
 Recursion 10'th value is:     55
 Recursion  5'th value is:      5
 Recursion  0'th value is:      0
The duration of this task took: 22679 microseconds.
The duration of this task took: 22 milliseconds.
The duration of this task took: 22679000 nanoseconds.
The duration of this task took: 0 seconds.
Pages: 12