[C] Quick Efficiency Check on Simple Program

[gloop]

Hey all, 

 

I've been starting programming using the CS50 course and have (I think?) finished Lab 1. 

 

Long story short this is what we have to do:

 

Quote

Say we have a population of n llamas. Each year, n / 3 new llamas are born, and n / 4 llamas pass away.

For example, if we were to start with n = 1200 llamas, then in the first year, 1200 / 3 = 400 new llamas would be born and 1200 / 4 = 300 llamas would pass away. At the end of that year, we would have 1200 + 400 - 300 = 1300 llamas.

To try another example, if we were to start with n = 1000 llamas, at the end of the year, we would have 1000 / 3 = 333.33 new llamas. We can’t have a decimal portion of a llama, though, so we’ll truncate the decimal to get 333 new llamas born. 1000 / 4 = 250 llamas will pass away, so we’ll end up with a total of 1000 + 333 - 250 = 1083 llamas at the end of the year.

 

Complete the implementation of population.c, such that it calculates the number of years required for the population to grow from the start size to the end size.

• Your program should first prompt the user for a starting population size.
  • If the user enters a number less than 9 (the minimum allowed population size), the user should be re-prompted to enter a starting population size until they enter a number that is greater than or equal to 9. (If we start with fewer than 9 llamas, the population of llamas will quickly become stagnant!)
• Your program should then prompt the user for an ending population size.
  • If the user enters a number less than the starting population size, the user should be re-prompted to enter an ending population size until they enter a number that is greater than or equal to the starting population size. (After all, we want the population of llamas to grow!)
• Your program should then calculate the (integer) number of years required for the population to reach at least the size of the end value.
• Finally, your program should print the number of years required for the llama population to reach that end size, as by printing to the terminal Years: n, where n is the number of years.

 

This is what I've written up:

 

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // Declare variables needed for population.c

    int startSize;
    int endSize;
    int currentPopulation;
    int years = 0;

    // Prompt user for the starting population size

    do
    {
        startSize = get_int("Start Size: ");
    }
    while (startSize < 9);

    // Set currentPopulation equal to startSize

    currentPopulation = startSize;

    // Prompt user for the ending population size

    do
    {
        endSize = get_int("End Size: ");
    }
    while (endSize < startSize);

    // Calculate number of years until we reach threshold

    for (; currentPopulation < endSize; years++)
    {
        currentPopulation = currentPopulation + ((currentPopulation / 3) - (currentPopulation / 4));
    }

    // Print number of years for population to reach the ending size

    printf("Years: %i\n", years);
}

 

It seems to work fine but I'm just wondering is there anyway I could make it cleaner or slightly more efficient. As always, any help is appreciated.

[Sauron]

It's just one operation in a for loop, I doubt there's anything to optimize...

[trag1c]

I am with @Sauronon this one. You're program is too simple and too small for there to be anything for you to optimize. Your console print and read operations will take more CPU time than your for loop ever will unless you enter an ungodly amount of llamas that you want to end up with.

 

Modern compilers are also highly intelligent when it comes to performing optimizations for you at compile time. If you were to look at the assembly instructions that are generated you would most likely see that your code is completely different to what you actually wrote. (You would need to set compiler options for 2 different builds, /Od, /Ot which are disabled and default for optimizations in MSVC respectively.)

 

As an example you might see that your currentPopulation / 4 would be simplified to a bitwise operation and your post increment would be changed to pre increment. 

[straight_stewie]

2 hours ago, Sauron said:

It's just one operation in a for loop, I doubt there's anything to optimize...

There is a slight optimization if we are being very nitpicky. If you are subtracting 1/4 and adding 1/3, then you are really adding 1/12 of the total population.

So, you do not need to calculate out the number of deceased llamas and new llamas, only the new population size, which is the current population size times 1 1/12

 

 

1 hour ago, trag1c said:

As an example you might see that your currentPopulation / 4 would be simplified to a bitwise operation and your post increment would be changed to pre increment. 

Didn't notice this was C at first.

[wanderingfool2]

9 hours ago, gloop said:

t seems to work fine but I'm just wondering is there anyway I could make it cleaner or slightly more efficient. As always, any help is appreciated.

You're code looks clean, and the code itself can't really be optimized much more.  In terms of the loop, you can't really optimize things...especially given the restriction that 333.333 floors to 333.  Otherwise you could do like n * 13/12 (represents the formula)...if you did something like that though, you would lose accuracy (due to the truncation).

 

Actually, if it weren't for the rule of truncating a loop might not have been necessary...as a year would be represented as startingPop * (13/12)^year, which would mean year = ceil( log(ending year/starting year)/log(13/12) )....assuming I did my math right...also I have no clue of the efficiency of log functions (so it could effectively be slower than a loop calculation)

[Sauron]

13 hours ago, straight_stewie said:

There is a slight optimization if we are being very nitpicky. If you are subtracting 1/4 and adding 1/3, then you are really adding 1/12 of the total population.

Compiler optimizations aside this is a situation where I'd rather have code clarity than ever so slightly higher speed.

[straight_stewie]

4 hours ago, Sauron said:

Compiler optimizations aside this is a situation where I'd rather have code clarity than ever so slightly higher speed.

I would think that both are clear enough:

int newPopulation = oldPopulation - (oldPopulation * (1/4)) + (oldPopulation * (1/3));
// Versus
int newPopulation = oldPopulation * (1 + 1/12);

// Versus
int newPopulation = oldPopulation * 1.0833;

 I might argue that options 2 and 3 are more clear than option one for this problem. Option 3 explicitly says that the population grows at a rate of 8.33%, offering far more insight to what's going on than option 1 does.

 

In a case where the function definition would be something like:

int GetPopulation(int year, float deathreate, float birthrate);

The I can see your argument. Of course, with that method signature, I'd probably opt for @wanderingfool2's closed form formula.