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?

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.

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?)

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.

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.";
}