Thread: Having to comment out loop for program to work correctly

  1. #1
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    123

    Having to comment out loop for program to work correctly

    Hey all, this is a problem on project euler #6. I did all of this code myself. With the for() loop comment removed the two printf() functions are resulting in wrong calculations (wrong). With the for() commented out the printf is resulting in the correct calculation for sum*sum (3025). also, i know to work the problem correctly I am going to need to set const int limit to 101; Here's problem on project euler
    Code:
    #include <stdio.h>
    
    
    int main (void)
    {
    	int j, k;
    	int i;
    	const int limit = 11;	
    	int squares_sum;
    	int sum;
    
    
    	/*
    	for (j = 1; j < limit; j++)
    	{
    		// 1^2 + 2^2 + ... +10^2 = 385
    		squares_sum = squares_sum += j*j;
    	}
    
    
    	printf("%d\n", squares_sum);
    	*/
    
    
    	while (i < limit) // let i itierate limit times then print sum
    	{
    		// 1+2+3+4+5+6+7+8+9+10
    		sum = sum += i;	
    		i++; // loop while loop limit times
    	}
    
    
    	printf("%d", sum*sum); // sum^2
    
    
    	printf("\n");
    
    
    	return 0;
    }

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    You need to initialize your sums to 0.

    In your second loop (which for some reason you've made a while loop) you forgot to start i at 1.

    This is wrong
    Code:
    sum = sum += i;
    It's just
    Code:
    sum += i;
    Similarly for the other use of +=.

    Code:
    #include <stdio.h>
     
    int main()
    {
        const long long limit = 100;
     
        long long sum_of_squares = 0;
        for (long long i = 1; i <= limit; ++i)
            sum_of_squares += i * i;
     
        // Or use the formula (if it doesn't overflow):
        //long long sum_of_squares = limit * (limit + 1) * (2 * limit + 1) / 6;
     
        printf("sum_of_squares: %9lld\n", sum_of_squares);
     
        long long sum = 0;
        for (long long i = 1; i <= limit; ++i)
            sum += i; 
        // Or use the formula (if it doesn't overflow):
        //long long sum = limit * (limit + 1) / 2;
     
        long long square_of_sum = sum * sum;
     
        printf("square_of_sum : %9lld\n", square_of_sum);
     
        printf("difference    : %9lld\n", square_of_sum - sum_of_squares);
      
        return 0;
    }
    Last edited by john.c; 02-04-2020 at 11:06 PM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  3. #3
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    123
    Code:
    #include <stdio.h>
    
    
    int main (void)
    {
    	long long j;
    	long long i;
    	const long long limit = 100;	
    	long long squares_sum = 0;
    	long long sum_squares = 0;
    
    
    	for (j = 1; j <= limit; j++)
    	{
    		// 1^2 + 2^2 + ... +10^2 = 385
    		squares_sum += j*j;
    	}
    
    
    	//printf("%lld\n", squares_sum);
    
    
    	for (i = 1; i <= limit; i++)
    	{
    		// 1+2+3+4+5+6+7+8+9+10
    		sum_squares += i;
    	}
    	sum_squares *= sum_squares;
    
    
    	// printf("%lld\n", sum_squares);
    
    
    	printf("Difference: %lld\n", sum_squares-squares_sum);
    
    
    	printf("\n");
    
    
    	return 0;
    }
    john.c, Should I do a calculation on my on my calculator (bc on linux or a generic calculator on a android smart phone) to prepare for the "long long" data type when seeing I will be getting a max value too big for the int to prevent a "overflow" that you mentioned? Someone a few days ago posted a limits.h program I ran and I saw the MAX range for each data type, I can find this on my post history here on the forum. Also, i learned the <= operator is letting me define limit as 100 instead of 100 therefore not using the < in the for loop. Thanks for clearing up the compound assignment operator issues, i will study these, and clearing up I needed to set the variables to '0'. Also instead of using a while and for loop as I did in my first program, now I know to just use two for loops as i believe this is why the program was getting confused. I've read in my book about the difference and similarities and why to choose one or the other.

    I believe my code gets the right answer, I don't have access to my bookmarks at current computer but looks familiar.

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Your code does get the correct answer.
    There's no reason to worry about overflow with limit set to 100, alghouth if it was necessary you can calculate it using the forumula for the sum of numbers from 1 to Limit and the quadratic formula.

    But you shouldn't declare all your variables at the top of a function.
    I might write it more like this:
    Code:
    #include <stdio.h>
     
    typedef unsigned long long ull;
     
    int main()
    {
        const ull Limit = 100;    
     
        ull squares_sum = 0;
        // 1**2 + 2**2 + 3**2 + ... + Limit**2
        for (ull i = 1; i <= Limit; ++i)
            squares_sum += i * i;
     
        //printf("%llu\n", squares_sum);
     
        ull sum_square = 0;
        // 1 + 2 + 3 + ... + Limit
        for (ull i = 1; i <= Limit; i++)
            sum_square += i;
        sum_square *= sum_square;
     
        //printf("%llu\n", sum_square);
     
        printf("%llu\n", sum_square - squares_sum);
     
        return 0;
    }
    And here's the way to do it using formulas instead of loops.
    I calculated the highest Limit that won't overflow an unsigned 64-bit value.
    Code:
    #include <stdio.h>
     
    #define FORMAT "%20llu"
    typedef unsigned long long ull;
     
    int main()
    {
        const ull Limit = 92681; // as high as we can go using 64-bit unsigned
     
        ull sum = Limit * (Limit + 1) / 2;
        ull sum_of_squares = sum * (2 * Limit + 1) / 3;
        ull square_of_sum = sum * sum;
     
        printf("sum_of_squares: "FORMAT"\n", sum_of_squares);
        printf("sum           : "FORMAT"\n", sum);
        printf("square_of_sum : "FORMAT"\n", square_of_sum);
        printf("difference    : "FORMAT"\n", square_of_sum - sum_of_squares);  
     
        return 0;
    }



    A little inaccuracy saves tons of explanation. - H.H. Munro

  5. #5
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    For reference, the concepts this question relies on are:

    (a) sum of consecutive natural numbers
    (b) triangle numbers and the sum of consecutive triangle numbers (this is because the formula for concept (c) can be derived from the triangle number equation)
    (c) square numbers and the sum of consecutive square numbers (see Square number - Wikipedia)

    The equation for (a) is (n * (n + 1)) / 2
    The equation for (c) is (n * (n + 1) * (2 * n + 1)) / 6

    Using pen and paper you can arrive at solution = (n * (n * n - 1) * (3 * n + 2)) / 12 or come up with other intermediate equations to maximise, how big an answer you can get given the size of, say, unsigned long ( by keeping the numerator as small as possible, for example, as john.c has apparently done). That said, if I was writing a program for this problem I think I'd keep the calculations simple and do it in steps like john.c has because that results in code that's more self-documenting.

    Reading:

    1 + 2 + 3 + 4 + ⋯ - Wikipedia
    Triangular number - Wikipedia
    Square number - Wikipedia
    Last edited by Hodor; 02-05-2020 at 07:51 PM.

  6. #6
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    123
    Quote Originally Posted by Hodor View Post
    For reference, the concepts this question relies on are:

    (a) sum of consecutive natural numbers
    (b) triangle numbers and the sum of consecutive triangle numbers (this is because the formula for concept (c) can be derived from the triangle number equation)
    (c) square numbers and the sum of consecutive square numbers (see Square number - Wikipedia)

    The equation for (a) is (n * (n + 1)) / 2
    The equation for (c) is (n * (n + 1) * (2 * n + 1)) / 6

    Using pen and paper you can arrive at solution = (n * (n * n - 1) * (3 * n + 2)) / 12 or come up with other intermediate equations to maximise, how big an answer you can get given the size of, say, unsigned long ( by keeping the numerator as small as possible, for example, as john.c has apparently done). That said, if I was writing a program for this problem I think I'd keep the calculations simple and do it in steps like john.c has because that results in code that's more self-documenting.

    Reading:

    1 + 2 + 3 + 4 + ⋯ - Wikipedia
    Triangular number - Wikipedia
    Square number - Wikipedia
    thanks for the response Hodor

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by _jamie View Post
    thanks for the response Hodor
    You're welcome. I guess I should have also mentioned that there is nothing "wrong" with your approach, especially for all the PE problems rated at 5% difficulty. All the 5% problems can be brute forced AFAIK (and at least one that I know of has to be brute forced). I guess I expanded on what john.c wrote because lots of the later PE problems cannot be brute forced (or cannot be brute forced in a reasonable amount of time; I admit that I "cheated" on at least one and let the computer run overnight hehe but in general the 1 minute rule should be observed otherwise the only one you're cheating is yourself). I don't know how much programming and mathematics experience you have so keep implementing the way you've been doing them, because so far there is nothing wrong with your approach, but I think it's useful to always ask yourself "is there a better or other way I can solve this". You're gaining experience no matter what your current experience is just by working on problems in your own way, so keep it up. Even if you cannot solve a particular problem (and there are lots of PE problems I've skipped over because I didn't -- or still don't -- have the experience) you're still gaining experience just by attempting a problem even if you don't solve it.

  8. #8
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    123
    Quote Originally Posted by Hodor View Post
    You're welcome. I guess I should have also mentioned that there is nothing "wrong" with your approach, especially for all the PE problems rated at 5% difficulty. All the 5% problems can be brute forced AFAIK (and at least one that I know of has to be brute forced). I guess I expanded on what john.c wrote because lots of the later PE problems cannot be brute forced (or cannot be brute forced in a reasonable amount of time; I admit that I "cheated" on at least one and let the computer run overnight hehe but in general the 1 minute rule should be observed otherwise the only one you're cheating is yourself). I don't know how much programming and mathematics experience you have so keep implementing the way you've been doing them, because so far there is nothing wrong with your approach, but I think it's useful to always ask yourself "is there a better or other way I can solve this". You're gaining experience no matter what your current experience is just by working on problems in your own way, so keep it up. Even if you cannot solve a particular problem (and there are lots of PE problems I've skipped over because I didn't -- or still don't -- have the experience) you're still gaining experience just by attempting a problem even if you don't solve it.
    Thanks for the support and encouragement

  9. #9
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    123
    Quote Originally Posted by Hodor View Post
    You're welcome. I guess I should have also mentioned that there is nothing "wrong" with your approach, especially for all the PE problems rated at 5% difficulty. All the 5% problems can be brute forced AFAIK (and at least one that I know of has to be brute forced). I guess I expanded on what john.c wrote because lots of the later PE problems cannot be brute forced (or cannot be brute forced in a reasonable amount of time; I admit that I "cheated" on at least one and let the computer run overnight hehe but in general the 1 minute rule should be observed otherwise the only one you're cheating is yourself). I don't know how much programming and mathematics experience you have so keep implementing the way you've been doing them, because so far there is nothing wrong with your approach, but I think it's useful to always ask yourself "is there a better or other way I can solve this". You're gaining experience no matter what your current experience is just by working on problems in your own way, so keep it up. Even if you cannot solve a particular problem (and there are lots of PE problems I've skipped over because I didn't -- or still don't -- have the experience) you're still gaining experience just by attempting a problem even if you don't solve it.

    Hodor, please, what do you mean "brute force" (method) for the 5% difficulty Euler problems? What is this referred to as? Thanks!

  10. #10
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by _jamie View Post
    Hodor, please, what do you mean "brute force" (method) for the 5% difficulty Euler problems? What is this referred to as? Thanks!
    Edit: the 5% project euler problems are those that are rated at 5% difficulty. I guess this means that are easy. They can all be solved using brute force (exhaustive calculation) as far as I know. The harder problems can't because they take too long


    Brute force: Basically it means calculating every single step without using any shortcuts.

    For example, and keeping with the theme of this thread, to sum the natural numbers <= 100 a brute force approach iterates over each number and adds them to a result. E.g.

    Code:
    /* untested */
    
    /* Find the sum of natural numbers <= N; i.e. 1 + 2 + 3 ... + N 
     * Brute force method... iterate over every number.
     */
    unsigned long sumNaturalNums(size_t N)
    {
        unsigned long sum = 0;
        for (size_t i = 1; i <= N; i++)
            sum += i;
        return sum;
    }
    The brute force method, above, for this is going to be pretty fast anyway but say N was 4 billion (for the sake of explanation assume that the sum of the first 4 billion natural numbers will fit into an unsigned long) the code above has to loop 4 billion times.

    An approach that is not brute force might be

    Code:
    unsigned long sumNaturalNums(size_t N)
    {
        return N * (N + 1) / 2;   // Ignore that N is size_t and the function is returning an unsigned long... this is just an example
    }
    This uses mathematics to arrive at the solution in one step. It doesn't step over every single number and it will get the result for N = 4 billion, in effect, instantly. Both the above functions give the same answer... the second is quite a lot faster though

    Brute-force search - Wikipedia
    Proof by exhaustion - Wikipedia
    Last edited by Hodor; 02-06-2020 at 10:17 PM.

  11. #11
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Comparing the brute force and the smarter solution for an input of 4 billion:
    * the first does 4 billion additions to sum, 4 billion increments of i, 4 billion comparisons, and 4 billion jumps back to the beginning of the loop; so about 16 billion operations.
    * the second does 3 (an addition, a multiplication, and a division).
    A little inaccuracy saves tons of explanation. - H.H. Munro

  12. #12
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Quote Originally Posted by Hodor View Post
    Using pen and paper you can arrive at solution = (n * (n * n - 1) * (3 * n + 2)) / 12
    I didn't even think of boiling it down to a single equation. That's pretty nifty. As written it will overflow at a lower value (49796), which I guess is an advantage of doing it in pieces. Your equation can be broken down into pieces to make it work for the same limit:
    Code:
    #include <stdio.h>
     
    typedef unsigned long long ull;
     
    int main()
    {
        const ull n = 92681;
     
        ull x = n;
        ull y = n * n - 1;
        ull z = 3 * n + 2;
     
        if (x % 2 == 0) { x /= 2; z /= 2; }
        else              y /= 4;
     
        if (x % 3 == 0)   x /= 3;
        else              y /= 3;
     
        printf("%llu\n", x * y * z);
     
        return 0;
    }
    The limit of 92681 can be calculated like this:
    Code:
    s = (n * (n + 1)) / 2
    2s = n**2 + n
    0 = n**2 + n - 2s    (quadratic form)
     
    answer = s * s
    So s can't go above sqrt(2**64) = 2**32 = 4294967296 (actually, one less)
     
    0 = n**2 + n - 2(4294967295)
     
    In the quadratic formula
    a = 1
    b = 1
    c = -8589934590
     
    (-b +- sqrt(b**2 - 4*a*c)) / (2 * a)         (quadratic formula)
    (-1 +- sqrt(1 - -34359738360)) / 2
    (-1 +- sqrt(34359738361)) / 2
    (-1 + 185363) / 2   (only + of +- makes sense)
    185362 / 2
    92681
    Last edited by john.c; 02-07-2020 at 12:12 AM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  13. #13
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by john.c View Post
    Comparing the brute force and the smarter solution for an input of 4 billion:
    * the first does 4 billion additions to sum, 4 billion increments of i, 4 billion comparisons, and 4 billion jumps back to the beginning of the loop; so about 16 billion operations.
    * the second does 3 (an addition, a multiplication, and a division).
    Yeah, that's a good way of expressing it as well. I have to admit I was a little lost for words and my explanation is a bit lacking. I often use methods to narrow down the range of possibilities and then brute force the last stretch (better to brute force over a few thousand numbers than 4 billion). I guess algorithm choice is related (or the same?) as well. I.e. a brute force search will check every item but that's not necessary depending on the data and the algorithm.

  14. #14
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    Quote Originally Posted by john.c View Post
    I didn't even think of boiling it down to a single equation. That's pretty nifty. As written it will overflow at a lower value (49796), which I guess is an advantage of doing it in pieces. Your equation can be broken down into pieces to make it work for the same limit:
    Code:
    #include <stdio.h>
     
    typedef unsigned long long ull;
     
    int main()
    {
        const ull n = 92681;
     
        ull x = n;
        ull y = n * n - 1;
        ull z = 3 * n + 2;
     
        if (x % 2 == 0) { x /= 2; z /= 2; }
        else              y /= 4;
     
        if (x % 3 == 0)   x /= 3;
        else              y /= 3;
     
        printf("%llu\n", x * y * z);
     
        return 0;
    }
    The limit of 92681 can be calculated like this:
    Code:
    s = (n * (n + 1)) / 2
    2s = n**2 + n
    0 = n**2 + n - 2s    (quadratic form)
     
    answer = s * s
    So s can't go above sqrt(2**64) = 2**32 = 4294967296 (actually, one less)
     
    0 = n**2 + n - 2(4294967295)
     
    In the quadratic formula
    a = 1
    b = 1
    c = -8589934590
     
    (-b +- sqrt(b**2 - 4*a*c)) / (2 * a)         (quadratic formula)
    (-1 +- sqrt(1 - -34359738360)) / 2
    (-1 +- sqrt(34359738361)) / 2
    (-1 + 185363) / 2   (only + of +- makes sense)
    185362 / 2
    92681
    Thanks for the programs and making it work for the same limit. I didn't intend to boil it down to a single equation but I was scribbling on paper and got carried away I think I'd approach it the way you originally did... easier to make things fit (and maybe the sum of natural numbers could be a reusable function whereas my single equation has a pretty narrow range of uses... probably just one use :P)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-16-2016, 11:48 PM
  2. Hello! Can someone help me? My code doesn't work correctly!
    By Eugen Hoxha in forum C Programming
    Replies: 11
    Last Post: 06-04-2015, 11:19 AM
  3. My addition program doesn't work correctly.
    By tmac619619 in forum C Programming
    Replies: 1
    Last Post: 11-04-2012, 02:05 AM
  4. I made a program but it doesn't work correctly
    By jeremy duncan in forum C Programming
    Replies: 30
    Last Post: 11-01-2011, 01:57 PM
  5. WM_KEYDOWN wont work correctly
    By maxorator in forum Windows Programming
    Replies: 11
    Last Post: 10-04-2005, 12:53 PM

Tags for this Thread