1

I am working on a non homework question that I just can't solve no matter what I try.

The problem is one from Project Euler that involves solving for even Fibonacci numbers and summing them together, I chose this one as a chance to learn more about functions, pointers, and working with large numbers that would be best served by not copying their value but instead passing a memory address.

I currently have the following:

/*Second attempt at fibo 4mil
problem.*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>

//MAX is 20 for testing reasons
//Actual value is MAX 0X3D0900
#define MAX 20 

//Function will accept even fibo numbers
//then sum them together for output later
void evenCount (double* evenPoint);

int main(void){
    double firstVar = 0;
    double secondVar = 1;
    double thirdVar;
    double modVar = 2;
    double sumVar;
    double count;

    for(count = 0; count < MAX; count++){

        thirdVar = firstVar + secondVar;
        secondVar = firstVar;
        firstVar = thirdVar;
        if(fmod(firstVar, modVar) == 0){
            evenCount(&firstVar);
        }
        printf("Currently: %.2f\n", firstVar);      
    }
    sumVar = &evenCount();

    printf("Final even sum is: %f\n", sumVar);

    return 0;
}

void evenCount (double* evenPoint){
    double tempOne, tempTwo, tempThree;

    tempOne = *evenPoint;

    tempThree = tempOne + tempTwo;
    tempTwo = tempOne;
    tempOne = tempThree;

    evenPoint = &tempOne;
}

I can't tell if the data from main() is being properly passed to the evenCount function for them to be summed and have it's value updated to be printed at the end of main().

My questions are:

  1. Do I need a second double pointer in evenCount to pass the final value or can I just reference one value updating it as it loops through?
  2. Does main() need a pointer so that pointer can reference evenCount pointer?

I would really appreciate any help because I have bought a Safari online subscription, have the "C A Reference Manual" sitting next to me but I just can't figure this out. Plus i read over this question and it kind of answered my question, but the person is using multiple function prototypes.

too few arguments to function and can't be used as a function---- beginning C

Thanks to anybody that looks

3
  • 1
    Note that you probably don't want to use double when you're wanting to work only with integers. You can actually represent more integers with a 64-bit long than with a 64-bit double. The extra range of the double comes with the cost of exact precision.
    – Tyler
    Oct 30, 2014 at 13:46
  • I apologize for not properly commenting my code, but MAX is 20 just for testing purposes it's real value is intended to be 0X3D0900
    – nif12
    Oct 30, 2014 at 20:34
  • @nif12 or you could just say "4000000" Either way, you really don't want that many iterations of the loop. You read the question wrong. Finding the solution requires 33 iterations. (11 even numbers)
    – Baldrickk
    Oct 31, 2014 at 10:24

3 Answers 3

1

I am not completely clear about what the evenCount() function is supposed to do.

Fact is that you are calling it the wrong way - sumVar = &evenCount(); is even twice wrong, as it is missing an argument and the & doesn't make sense - and that it doesn't do what you probably want.

Let's have a look:

void evenCount (double* evenPoint){
    double tempOne, tempTwo, tempThree;

Here you define three auto variables, but they haven't got a value yet.

    tempOne = *evenPoint;

    tempThree = tempOne + tempTwo;

What do you expect to be tempTwo here?

    tempTwo = tempOne;
    tempOne = tempThree;

    evenPoint = &tempOne;

You might mean *evenPoint = tempOne here, but I am not sure.

}

I suppose you want a way to make a "step" in terms of Fibonacci numbers. So let's look:

In order to create the "next" Fib number, you need the two previous ones and add them together. So a "step" could be done in a function like

void fibStep(double * curr, double *prev) {
    double new = *curr + *prev;
    *prev = *curr;
    *curr = new;
}

and then

int main(void){
    double firstVar = 0;
    double secondVar = 1;
    double sumVar = 0;
    int count; // no need to have this as a double...

    for(count = 0; count < MAX; count++){

        fibStep(&secondVar, &firstVar);

        if(fmod(secondVar, 2) == 0){
            sumVar += secondVar);
        }

        printf("Currently: %.2f\n", secondVar);

    }

    printf("Final even sum is: %f\n", sumVar);
    return 0;
}
4
  • Hmm. You hadn't posted your answer when I started writing mine. Yet we still started with almost the same first line... Our answers are different though, yours focuses on fixing problems, I focused more on how to do it right from the start.
    – Baldrickk
    Oct 30, 2014 at 14:30
  • @Baldrickk I suppose it is due to the fact that nobody actually knows what this function is about...
    – glglgl
    Oct 30, 2014 at 14:32
  • That's true , I just found it interesting that it was the first thing we both approached in our answers, with an almost identical sentence structure.
    – Baldrickk
    Oct 30, 2014 at 14:37
  • I failed to properly comment but my intent with evenCount was simply a means of learning more about working with functions and pointers. Because in my other comment above MAX is actually supposed to be 0X3D0900 thus why I required using double values(which I suspect should be unsigned).
    – nif12
    Oct 30, 2014 at 20:36
0

I'm not quite sure what evenCount is meant to do as it is. Edit: see below.

From your description of the problem, it seems like you could just do:

int isEven(unsigned int number)
{
    return !(number%2);
}

int main()
{
    unsigned int first = 1, second = 1, next, sum = 0;

    //we already have the first two numbers so start at 2
    for(count = 2; count < MAX; count++) 
    {
        next = first+second;
        first = second;
        second = next;

        //we know the starting values are odd (1 & 1) and won't need to be summed so we can test the new value - 
        if (isEven(second))  //if even (no remainder when dividing by 2)
        {   sum+=first;}
    }
    printf("Final even sum is: %f\n", sum);
}

Note, there is no need for double here (yet). The sum (at n=20) is still far too low to exceed what int can store. (although at this point it is growing quickly)

As for your actual questions:

note: when you don't need a pointer, it is recommended that you don't use one, as all you are going to do is make the code more complex than needed

Do I need a second double pointer in evenCount to pass the final value?

If the function is meant to keep track of the sum, then I'd do it like this:

unsigned int evenSum(unsigned int num = 0)
{
    static unsigned int sum = 0;    //initialised on first use of function. Value is retained between function calls.
    //we test for even here - no longer need to test in calling code 
    // - making the algorithm simpler
    if (isEven(num))
        sum += num;
    return sum;
}

which can then be called like this:

//adding values:
evenSum( new_value );
//retrieving sum
sum = evenSum();
//or do both:
sum = evenSum( new_value );

If you wanted to store the sum 'locally' though (i.e. as a variable in main, but modify it in the evenSum() function), then yes, you would then need to pass it into the funtion too as a pointer:

void evenSum(unsigned int num, unsigned int * sum)
{
    if (isEven(num))
        *sum += num;
}

It would be called like this:

sum = 0;
num = 56;
evenSum(num, &sum); //sum is now sum+num

As you pass the address of sum in, when the function de-references it, it modifies the value and not a copy. The number passed in does not need to be passed in as a pointer as it is a (forgetting correct word here, but it means 'basic') type, and passing it by value is actually slightly more efficient as at runtime it can just be loaded into a register, and doesn't rely on memory lookup. Plus, it is easier to read.

Does main() need a pointer so that pointer can reference evenCount pointer?

To be honest, I'm not 100% sure what you are asking here.

If you are asking:

Do I need to store a pointer to the sum in main() to pass into the evenSum() function?

then no.

You can pass a pointer to a 'thing' using the "address of" operator &. I've used it above in the second calling example in the above answer:

unsigned int * sum_pointer = &sum;//    <--- not needed
evenSum(num, &sum); //sum is now sum+num
              ^
              This passes a pointer to sum

Edit: looking at your code again, is evenCount meant to find the next fibonachi number?

If so, you could do:

void next_fib(unsigned int *previous, unsigned int *current)
{
    unsigned int next = *previous+*current;
    *previous = *current;
    *current = next;
}

And you would call this like so:

unsigned int val1 = 1, val2 = 1;
next_fib(&val1, &val2);        //val2 is now the 3rd fib. #
next_fib(&val1, &val2);        //val2 is now the 4th fib. #

To add this to my code from above, the program becomes:

int isEven(double number)
{
    return !(number%2);
}

unsigned int evenSum(double num = 0)
{
    static double sum = 0;
    //we test for even here - no longer need to test in calling code 
    // - making the algorithm simpler
    if (isEven(num))
        sum += num;
    return sum;
}

void next_fib(unsigned int *previous, unsigned int *current)
{
    unsigned int next = *previous+*current;
    *previous = *current;
    *current = next;
}

int main()
{
    unsigned int first = 1, second = 1;
    //we already have the first two numbers so start at 2
    for(count = 2; count < MAX; count++) 
    {
        next_fib(&first, &second);
        evenSum(second);
    }
    printf("Final even sum is: %f\n", evenSum());
}

Edit 2:

After reading your edit and some of your comments, and then taking a look at the actual task, you have interpreted the question incorrectly.
The question asks for the sum of all even numbers in the fibbonachi sequence, where the number is less than 4x106. This is thankfully easier and quicker to do than the sum of all the even Fibonacci numbers up to the 4x106th.

Obviously, we need to change the algorithm. Luckily, we split the main bits into functions already, so it's pretty simple, mainly just a change in the loops, though I made a couple more changes too:

bool isEven(unsigned long number)
{
    return !(number%2);
}

void next_even_fib(unsigned long *previous, unsigned long *current)
{
    do
    {
        unsigned int next = *previous+*current;
        *previous = *current;
        *current = next;
    } while (!isEven( *current));
    //we could just do 3 passes here without needing the isEven() function
    //as the Fibonacci sequence is always O,O,E,O,O,E...
    //but this is a more general form
}

int main()
{
    //as there is less constraint on knowing which term we are on, we can skip straight to the first even number.
    unsigned long first = 1, second = 2;
    unsigned long sum = 0;
    do
    {
        //with the sum calculation first, we can break out of the loop before the sum
        //we've changed the algorithm so when we get here, second is always even
        sum += second;
        next_even_fib(&first, &second);
    } while (second < 4000000);
    printf("Final even sum is: %d\n", sum);
}

Note that I changed the types to unsigned long. This is still an integer value, but one that is guaranteed to be long ( :-P ) enough to store the numbers we need.

3
  • I am regretting not using comments early on especially considering how helpful they would have been. evenCount was just intended to pick up the even number from the main() if fmod loop and would then add it to a running sum total in the function.
    – nif12
    Oct 30, 2014 at 22:52
  • @nif12 I've added another section (edit 2:) based on the comments you have made on this question. If there is anything you don't understand about it, just ask.
    – Baldrickk
    Oct 31, 2014 at 9:26
  • OK, that was wierd. I was missing the ! from the next_even_fib function. It was skipping all the equal fibonacci numbers. The wierd thing is that the answer it gave was exactly the same. It turns out that because every even number is the sum of the previous two odd numbers, the sum of odd numbers is equal to the sum of even numbers, as long as the number of fibonacci numbers calculated is a multiple of 3. Still, it's fixed now
    – Baldrickk
    Oct 31, 2014 at 10:30
0

Passing of the value is correct but you can't do evenPoint = &tempOne; to return a value from the function. There are two problems in doing that: first is that C supports only pass by value, so when you pass a pointer you are in fact creating a copy of the pointer for the callee. Any modification of the data pointed will be visible to the caller but not modifications to the pointer argument itself. When you modify the pointer argument you are in fact modifying a stack variable that the caller has no access to.

What's the difference between passing by reference vs. passing by value?

You could change your code in the following way:

void evenCount (double** evenPoint){
    double tempOne, tempTwo, tempThree;

    tempOne = **evenPoint;

    tempThree = tempOne + tempTwo;
    tempTwo = tempOne;
    tempOne = tempThree;

    *evenPoint = &tempOne;

}

But that would mean that *evenPoint points to a variable allocated on the stack, precisely on the frame of evenCount. When evenCount returns the frame get popped out of the stack. Accessing that variable after it is outside the stack will cause undefined behavior. Consider the following example where you call another function A() after evenCount before using evenPoint. A() function frame would be placed in memory at the same location of where evenCount frame was and its local variables might overwrite the value of evenPoint. When you subsequently read evenPoint you will find its value changed.

C++ Returning reference to local variable

Finally, you read the variable tempTwo which is an uninitialized automatic variable so you'll end up reading garbage.

7
  • "But that would mean that *evenPoint points to an automatic variable, this can cause problems if you call another function and overwrite that value." It not only "can cause problems", it is merely undefined behaviour.
    – glglgl
    Oct 30, 2014 at 13:27
  • Which can cause problems... Given that the question is quite basic I tried to explain things thoroughly without using "big" words. I'll edit that paragraph..
    – igon
    Oct 30, 2014 at 13:40
  • My point was, it cannot only cause problems, it is a problem.
    – glglgl
    Oct 30, 2014 at 13:42
  • I just couldn't figure out how to initialize tempTwo, tempThree because everytime evenCount is called on and passed an even number they would be reset. I think I will malloc an array that increments a counter each time it is run. That way each value would be stored successively.
    – nif12
    Oct 30, 2014 at 20:45
  • @nif12 If it's only about outputting the values, an array is unneeded. All you need is access to the last 2 values, and that's what is already achieved - e. g. in my solution.
    – glglgl
    Oct 31, 2014 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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