Standardly deviated Fibonacci

Question

I'm new to C++ (about 4 weeks with no prior programming experience in other languages) and am writing a program that's supposed to do the following:

• Define an array of 100 sequential numbers of type float.
• Define an array of 20 Fibonacci numbers of type int.
• Use an overloaded function to compute the mean of the array containing 100 numbers.
• Use an overloaded function to compute the standard deviation of an array containing 100 numbers.
• Use an overloaded function to compute the mean of the array containing 20 Fibonacci numbers.
• Use an overloaded function to compute the standard deviation of the array containing 20 Fibonacci numbers.

#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
const int SIZE_OF_GENERIC_ARRAY = 100;
const int SIZE_OF_FIBONACCI_ARRAY = 20;
double arithmeticAverage;
char sequenceType;
float Array[SIZE_OF_GENERIC_ARRAY];
int Fibonacci[SIZE_OF_FIBONACCI_ARRAY];
void fillGenericArray(int SIZE_OF_GENERIC_ARRAY);
void fillFibonacciArray(int SIZE_OF_FIBONACCI_ARRAY);
double mean(float[], int);
double mean(int[], int);
double standardDeviation(float[], int);
double standardDeviation(int[], int);
void outputMean();
void outputStandardDeviation();
int _tmain(int argc, _TCHAR* argv[])
{
 cout << "Would you like to generate a generic sequence or a Fibonacci sequence?"
 << endl
 << "\n"
 << "Type [G] + [ENTER] for a generic sequence, or;" << endl
 << "Type [F] + [ENTER] for a Fibonacci sequence: ";
 cin >> sequenceType;
 if (sequenceType == 'G' || sequenceType == 'g')
 {
 fillGenericArray(SIZE_OF_GENERIC_ARRAY);
 outputMean();
 outputStandardDeviation();
}
 else if (sequenceType == 'F' || sequenceType == 'f')
 {
 fillFibonacciArray(SIZE_OF_FIBONACCI_ARRAY);
 outputMean();
 outputStandardDeviation();
 }
 else
 cout << "\n"
 << "Invalid input. Please type 'F' or 'G'. Thank you.";
 return 0;
}
void fillGenericArray(int SIZE_OF_GENERIC_ARRAY)
{
 int i = 0;
 Array[0] = { 1 };
 for (int i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
 Array[i] = i + 1;
 return;
}
void fillFibonacciArray(int SIZE_OF_FIBONACCI_ARRAY)
{
 int i;
 Array[0] = { 0 };
 Array[1] = { 1 };
 for (int i = 2; i < SIZE_OF_FIBONACCI_ARRAY; i++)
 Array[i] = Array[i - 1] + Array[i - 2];
 return;
}
double mean(float Array[], int SIZE_OF_GENERIC_ARRAY)
{
 double sumOfElements = 0;
 int i;
 for (i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
 {
 sumOfElements += Array[i];
 }
 arithmeticAverage = sumOfElements / i;
 return (arithmeticAverage);
}
double mean(int Array[], int SIZE_OF_FIBONACCI_ARRAY)
{
 double sumOfElements = 0;
 int i;
 for (i = 0; i < SIZE_OF_FIBONACCI_ARRAY; i++)
 {
 sumOfElements += Array[i];
 }
 arithmeticAverage = sumOfElements / i;
 return (arithmeticAverage);
}
double standardDeviation(float Array[], int SIZE_OF_GENERIC_ARRAY)
{
 double standardDeviation;
 double tempSum = 0;
 for (int i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
 {
 tempSum += pow((Array[i] - mean(Array, SIZE_OF_GENERIC_ARRAY)), 2);
 }
 standardDeviation = sqrt(tempSum / (SIZE_OF_GENERIC_ARRAY));
 return (standardDeviation);
}
double standardDeviation(int Array[], int SIZE_OF_FIBONACCI_ARRAY)
{
 double standardDeviation;
 double tempSum = 0;
 for (int i = 0; i < SIZE_OF_FIBONACCI_ARRAY; i++)
 {
 tempSum += pow((Array[i] - mean(Array, SIZE_OF_FIBONACCI_ARRAY)), 2);
 }
 standardDeviation = sqrt(tempSum / (SIZE_OF_FIBONACCI_ARRAY));
 return (standardDeviation);
}
void outputMean()
{
 cout << "\n";
 cout << "The mean is: " << mean(Array, SIZE_OF_GENERIC_ARRAY);
 cout << endl;
}
void outputStandardDeviation()
{
 cout << "\n";
 cout << "The standard deviation is: " << standardDeviation(Array,
 SIZE_OF_GENERIC_ARRAY);
 cout << endl;
}

This code compiles and outputs the correct results. But, I feel that I've written a lot of code and have some redundancies.

Am I applying the concept of overloading properly? Is there a better way to call the mean() and and standardDeviation() functions from inside the void outputMean() and void outputStandardDeviation() functions? Is there a way that I can streamline any of this and make it more efficient?

• Malachi: Welcome to CodeReview! This is a good question, thank you for taking the time to form it so that we can help show you the proper coding styles and techniques. We all look forward to seeing more of your posts!
• shuttle87: I thought that this code raised a bunch of interesting points so I blogged about it: lesinskis.com/code_repair_02a_fibonacci_homework.html

Answer 1

I have found a couple of things that could help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Avoid the use of global variables

It may make some sense to have SIZE_OF_GENERIC_ARRAY as a global variable, but not arithmeticAverage. It's generally better to explicitly pass variables your function will need rather than using the vague implicit linkage of a global variable.

Pass needed variables explicitly

This is basically the other way of stating the previous item. As an example, you have a function fillGenericArrray() which takes an integer argument which is the size of the array. That's good, but it should also take the array to be filled as another argument. Putting that into practice, we get this:

void fillGenericArray(float array[], int arraysize)
{
 for (int i = 0; i < arraysize; ++i)
 array[i] = i + 1;
}

Note too that the initialization of the first element is already done within the loop and need not be done explicitly.

Use a function template for nearly identical functions

Your two versions of mean are identical except for the fact that one takes an array of float and the other an array of int. You could simplify that by using a template:

template<typename T>
double mean(T array[], int arraysize)
{
 double sumOfElements = 0;
 for (int i = 0; i < arraysize; ++i)
 sumOfElements += array[i];
 return sumOfElements / arraysize;
}

Note also that I have also made a few other changes.

• moved the declaration of i within the loop
• changed the names of the passed variables
• eliminated the arithmeticMean local variable
• removed the spurious parentheses from the return statement
• change from postincrement to preincrement for the loop variable

Precalculate loop invariants

A loop invariant is a value used within a loop construct that doesn't change. Right now your code recalculates the mean for every iteration of the for loop in the standardDeviation function. Since it doesn't change, it's better to calculate it just once and then use it repeatedly within the loop. Combining that with the ideas in the previous point, those two functions become this single templated function:

template<typename T>
double standardDeviation(T array[], int arraysize)
{
 double tempSum = 0;
 double mymean = mean(array, arraysize);
 for (int i = 0; i < arraysize; ++i)
 {
 tempSum += pow((array[i] - mymean), 2);
 }
 return sqrt(tempSum / arraysize);
}

Eliminate unused variables

This code declares a variable i at the top of both fillGenericArray and fillFibonacciArray but then redefines it within the scope of the for loop in each. You can (and should) eliminate the redundant declaration of i at the top of each of those functions. Also, note that your compiler is smart enough to help you find this kind of problem if you know how to ask it to do so.

Have functions do just one thing

Your function outputMean() does two things: it calculates and outputs the mean. Better would be to do something like this:

 std::ostream& outputMean(std::ostream &out, double mean)
 {
 return out << "\nThe mean is: " << mean << '\n';
 }

Or, because it's now quite simple, eliminate the function entirely and call it from within main() like this:

 std::cout << "\nThe mean is: " << mean(Array, SIZE_OF_GENERIC_ARRAY) << '\n';

Note, too, that this eliminates an error in your existing code -- regardless of which selection is made, outputMean() and outputStandardDeviation() both always calculate the mean of Array and never that of Fibonacci.

Don't use std::endl when \n will do

Emitting std::endl actually flushes the stream as well as emitting a newline character. This takes extra time and code which you don't really need in your code. Instead just use \n in all cases in this particular code.

Update:

I have noticed that the code uses the same names for global variables, local variables and function parameters. This makes things confusing and would be best avoided. For example, your code has a global variable:

const int SIZE_OF_FIBONACCI_ARRAY = 20;

This is then used within main as:

fillFibonacciArray(SIZE_OF_FIBONACCI_ARRAY);

The code for that function is:

void fillFibonacciArray(int SIZE_OF_FIBONACCI_ARRAY)
{
 int i;
 Array[0] = { 0 };
 Array[1] = { 1 };
 for (int i = 2; i < SIZE_OF_FIBONACCI_ARRAY; i++)
 Array[i] = Array[i - 1] + Array[i - 2];
 return;
}

The problem is that there are two different things called SIZE_OF_FIBONACCI_ARRAY here, and I think the difference may be confusing you. Let's rewrite the the function a bit to make it easier to talk about:

void fillFibonacciArray(int mysize)
{
 int i;
 Array[0] = 0;
 Array[1] = 1; // note that we don't need braces here
 for (int i = 2; i < mysize; i++)
 Array[i] = Array[i - 1] + Array[i - 2];
 // we don't need an explicit return at the end of a void function
}

When this function is called as fillFibonacciArray(SIZE_OF_FIBONACCI_ARRAY), the formal parameter mysize is replaced with the actual parameter SIZE_OF_FIBONACCI_ARRAY which was declared globally with the value of 20. What is confusing about your original code is that there is a formal parameter named SIZE_OF_FIBONACCI_ARRAY that then gets the actual parameter which just happens to have the same name. Unfortunately, the code then refers to Array which is a global variable. The effect is that instead of creating a series of 20 int values in the Fibonacci array, your code is actually putting 20 float values in the first 20 slots in Array and the Fibonacci array is never used. See this article on Wikipedia for a longer and more complete explanation of the terms formal parameter and actual parameter and what they mean.

• Malachi: I totally missed the double declaration of i. nice answer
• Loki Astari: The term is "Avoid Global mutable state". Global constants are fine and don't cause issues. Global mutable state is what causes problems.
• Edward: @LokiAstari: I'd agree that global mutable state is more of a problem. However, it seems to me that avoiding global variables entirely (including constants) is generally good advice. They pollute the global namespace and can cause annoying collisions in larger programs if not used very judiciously. In this particular case, the code is very easily rewritten with those constants moved to within main or at the very least declared static to limit them to file scope.
• Loki Astari: Your argument against global static const are not good. They don't need to pollute the global namespace they can just as easily be placed in a specific namespace and still be global. There is nothing technically wrong with global constants (if fact they are encouraged). Google the famous google programming talk about "global mutable state".
• Snowbody: In general it's good advice to "Use a function template for nearly identical functions", but the instructor wants to see an overloaded function, not a templated function.

Answer 2

Yes, the code's terrible and yes you've used overloading incorrectly, but it's hard for me to see how you were supposed to fill your project spec without using it incorrectly. Your lecturer must be awful if this stuff is what he teaches.

using namespace std;

Don't, ever. std is full of an ever-increasing number of unconstrained template algorithms with generic names. The price of writing std::cout instead of cout is nothing, and the price of having the compiler pick std::distance instead of your own distance will make you cry.

const int SIZE_OF_GENERIC_ARRAY = 100; 
const int SIZE_OF_FIBONACCI_ARRAY = 20;

All upper case names are conventionally reserved for macros. You don't want to know what happens if you clash with a macro. In addition, these are known as "magic buffer sizes"- they're constants with no logic or reason behind them. You should, at the absolute minimum, comment on why these specific sizes were required.

double arithmeticAverage;
char sequenceType;

Do not ever declare mutable variables at namespace scope. They are the worst kind of sin. They're awful, uncontrollable, and are incredibly difficult to clean up later.

float Array[SIZE_OF_GENERIC_ARRAY];
int Fibonacci[SIZE_OF_FIBONACCI_ARRAY];

Do not ever use C-style arrays. They are that way for compatibility with B or BCPL, not because their behaviour is good. It isn't. They are tremendously unsafe. You can use std::array<float, size> or std::array<int, size> instead. std::array lives in <array> and acts like a real value type and Standard container.

Also, the whole _tmain thing is totally unnecessary, it's a legacy holdover from 1995 that has no use anymore. Use main unless you know what this stuff actually is. You also don't need that stdafx crap, although it takes a little knowledge to convince Visual Studio to shut up about it.

Now, as you've correctly noticed, your mean and standardDeviation functions are complete duplicates w.r.t. float and int versions. You can easily re-implement them as one template function for both, but they can also be much more easily defined by using the appropriate Standard algorithms, which live in <algorithm> and <numeric>.

Finally, outputMean and outputStandardDeviation are worthless junk, their logic should just be in main (also, don't they always use the terribly-named Array, instead of the Fibonacci array, even if the user asked for Fib?)

• Simon Forsberg: I can't help but feel that you sound a bit aggressive in your answer. I think your answer is entirely correct though.
• Elizabeth C.: Honestly, I was a bit put off by Dead's response. But, it was incredibly instructive. I want to learn this language. And, if it takes some 'tough love' to do so, then so be it... :)
• Elizabeth C.: Honestly, the teacher isn't very good at all. Mostly, I'm trying to learn on my own. I think this site is an excellent resource. In this one post alone, I learned at least 5 to 7 new concepts. Very much appreciated!!
• Loki Astari: But to be a great teacher you need to teach arrays first. Because a great teacher will show you "WHY" std::array<> is better and to do that you must first teach your students about arrays so that they can compare and contrast the differences. Learning std::array<> is better by rote does not help educate the next generation of programmers.
• Loki Astari: Also I must disagree that outputX() functions are junk. This goes to having self documenting code. Well named functions that replace a section of code make the code more maintainable by self documenting what they are doing. Are they badly written? yes. But you can at least explain why they are badly written (in my opinion because they only use std::cout I would have parameterized them).

Answer 3

Your code is generally correct, but your calculation of the standard deviation is inefficient.

for (int i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
{
 tempSum += pow((Array[i] - mean(Array, SIZE_OF_GENERIC_ARRAY)), 2);
}

This will call the mean function once for each element of the array, and mean likewise iterates through the array. If the array contains a million elements, this could take a while.

A better way is to call mean once:

float arrayMean = mean(Array, SIZE_OF_GENERIC_ARRAY);
for (int i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
{
 tempSum += pow((Array[i] - arrayMean), 2);
}

In the language of algorithms, your solution is \$O(n^2)\,ドル while the second version is \$O(n)\$.

There are more advanced techniques that will allow you to forgo the use of global variables and raw arrays, but I understand that your purpose for now is to learn the basics.

P.S. You can also calculate the mean and standard deviation in a single pass, if you're mathematically inclined.

• DeadMG: If by "better" you mean "The compiler can optimize it to that easily, but it's less readable", then I agree.
• DeadMG: You might want to leave more than ten seconds before asking for comments, since it takes more than that to actually write one.
• DeadMG: Also, I highly doubt that O(n^2) will be a problem for a 100-element array of floats on modern hardware.
• Beta: @DeadMG: So what do you think the word "efficient" in the question means?
• Vogel612: @DeadMG let me barge in here. I disagree. If you can see directly that something can be executed more efficiently, then it's not efficiently written. That aside, I find the "corrected" version much more readable than the original code. Furthermore, just because it's 100 elements now, that doesn't mean it will be 100 elements forever. think big

Answer 4

you should be consistent in your use of brackets on your loops, the first two don't use brackets for one-liners but the others do? I suggest that you always use brackets

for (int i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
 Array[i] = i + 1;

And

for (int i = 2; i < SIZE_OF_FIBONACCI_ARRAY; i++)
 Array[i] = Array[i - 1] + Array[i - 2];

Versus

for (i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
{
 sumOfElements += Array[i];
}

And

for (int i = 0; i < SIZE_OF_GENERIC_ARRAY; i++)
{
 tempSum += pow((Array[i] - mean(Array, SIZE_OF_GENERIC_ARRAY)), 2);
}

---

there are other fluke formatting issues which I am sure have something to do with typos or copy paste issues as well...

 if (sequenceType == 'G' || sequenceType == 'g')
 {
 fillGenericArray(SIZE_OF_GENERIC_ARRAY);
 outputMean();
 outputStandardDeviation();
}
 else if (sequenceType == 'F' || sequenceType == 'f')
 {
 fillFibonacciArray(SIZE_OF_FIBONACCI_ARRAY);
 outputMean();
 outputStandardDeviation();
 }
 else
 cout << "\n"
 << "Invalid input. Please type 'F' or 'G'. Thank you.";

• Carriage returns in between elements of the if statement
• No brackets on the else statement
• Bad indentation on the if statement

this is what it should look like

 if (sequenceType == 'G' || sequenceType == 'g')
 {
 fillGenericArray(SIZE_OF_GENERIC_ARRAY);
 outputMean();
 outputStandardDeviation();
 }
 else if (sequenceType == 'F' || sequenceType == 'f')
 {
 fillFibonacciArray(SIZE_OF_FIBONACCI_ARRAY);
 outputMean();
 outputStandardDeviation();
 }
 else
 {
 cout << "\n"
 << "Invalid input. Please type 'F' or 'G'. Thank you.";
 }

---

I don't know how to code it, but I think it can be done, you should convert the input to uppercase and then just check for 'G' or 'F' it would eliminate an extra check, but at what cost I do not know.

so I would convert the input to upper case and then eliminate the check for a lowercase letter.

sequenceType = std::toupper(sequenceType);
if (sequenceType == 'G')
{
 fillGenericArray(SIZE_OF_GENERIC_ARRAY);
 outputMean();
 outputStandardDeviation();
}
else if (sequenceType == 'F')
{
 fillFibonacciArray(SIZE_OF_FIBONACCI_ARRAY);
 outputMean();
 outputStandardDeviation();
}
else
{
 cout << "\n"
 << "Invalid input. Please type 'F' or 'G'. Thank you.";
}

• DeadMG: Brace style is the least of his problems. This does nothing but focus him on totally the wrong issues.
• Malachi: I respectfully disagree, it is harder to find issues if the code is cluttered and hard to read, writing clean code makes it easier to debug.
• jliv902: +1 for recommending the use of brackets. Not sure if I agree with the too many newline characters part. For case conversion, there is std::toupper(). It would technically be less efficient performance-wise, but that wouldn't make a difference.
• Jamal: There are not that many newline characters, but it is worth mentioning that std::endl is not needed; "\n" is preferred.
• Loki Astari: @jiv902: Technically less efficient. Actually I don't know if I would not make that bet. To upper is simply an array access operation. So it boils down to: if (sequenceType == 'F' || sequenceType == 'f') Vs if (ToUpper[sequenceType] == 'F') Thats a very hard one to call. So I would go for the most readable one as my argument.