CODEWITHSUNDEEP
c
Martin
Martin

Reputation: 1090

Finding all combinations of a^2 + b^2 in C

I'm trying to find all combinations of x, where x = a^2 + b^2, and x is between 100 and 999.

So far i've got:

#include <stdio.h>
#include <stdlib.h>

#define MAX 31 // given that 31^2 = 961

int main(){
    int i = 0;
    int poss_n[] = {0};

    for (int a=0; a <= MAX; a++){
        for (int b=0; b <= MAX; b++){
            if (a*a + b*b >= 100 && a*a + b*b <= 999){ 
                poss_n[i] = a*a + b*b;
                printf("%i\n", poss_n[i]);
                i++;
            }
        }
    }
}

However it's giving only partially correct output, and also prematurely ends with segmentation fault 11:

100 1380405074 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 101 122 145 170 197 226 257 290 325 362 401 442 485 530 577 626 677 730 785 842 901 962 104 125 148 173 200 229 260 293 328 365 404 445 488 533 580 629 680 733 788 845 904 965 109 130 153 178 205 234 265 298 333 370 409 450 493 538 585 634 685 738 793 850 909 970 116 137 160 185 212 241 272 305 340 377 416 457 500 545 592 641 692 745 800 857 916 977 106 125 146 169 194 221 250 281 314 349 386 425 466 509 554 601 650 701 754 809 866 925 986 100 117 136 157 180 205 232 261 292 325 360 397 436 477 520 Segmentation fault: 11

What modifications should I make to my code?

UPDATE

Other than the the array issue, is there anything else wrong with my code? for instance it's still printing 100 as the first value which doesn't appear to be any combination of a^2 + b^2, even when b = 0.

UPDATE 2

Never mind, forgot a = 10, b = 0, which would be 100.

Upvotes: 5

Views: 477

Answers (6)

TrueY
TrueY

Reputation: 7610

As others already said you allocate too few space on stack. Stack goes from high addresses decreasing. So at first You overwrite the stack data corrupting it and then You reach the end of the stack and You try to write to a memory space not allocated to You, or not allocated at all. The CPU generates an exception and that's why the Segmentation fault error occurs.

Also You could allocate some memory with malloc(3) on the heap and not on the stack, and when You found more result You can extend using realloc. It uses more system CPU resources, but reduces the memory overallocation.

On some un*ces You can also dynamically allocate memory on stack, using the alloca(3) function. It behaves very similar then some_type array[some_value], but some_value can be calculated runtime and not compile time.

Also You can use C++ STL containers, like vector and list and You can push the found elements. The allocate memory segments automatically on the heap.

Some comments: Addition can be used instead of multiplication counting squares. (a+1)^2 - a^2 = 2a + 1. So add (a<<1) + 1 to a temp variable starting from 0. Similar can be applied to b. Also from the inner loop can be jumped with break if the sum is over 999. You do not need to check the remaining values. The value b could start from (int)sqrt(100-a*a) (or use a temp varible to keep track of the first b value) to reduce the number of inner loops.

Upvotes: 0

Gossamer
Gossamer

Reputation: 309

Lots of answers here, but none quite accurate.

Ff we assume that only unique output is printed out, loop should look like this (as Roee Gavirel stated):

for (int a=0; a <= MAX; a++){
    for (int b=a; b <= MAX; b++){

poss_n will hold this number of elements: (32+(32-1)+(32-2)+..+1)=1/2*32*(32+1)

So it should be defined as:

int elements = MAX+1;
int *poss_n = (int*)malloc ((1/2)*(elements)*(elements+1));

It will have more elements because of rule 100< value <999, but without that rule it will hold exact number of elements.

Upvotes: 0

user2247801
user2247801

Reputation: 145

Try this , it will work 

#include <stdio.h>
#include <stdlib.h>

#define MAX 31 // given that 31^2 = 961

int main(){
    int i = 0;
    int poss_n[301];
int a,b;
    for (a=0; a <= MAX; a++){
        for (b=0; b <= MAX; b++){
            if (a*a + b*b >= 100 && a*a + b*b <= 999){ 
                poss_n[i] = a*a + b*b;
                printf("%i\t i = %d , a = %d , b = %d\n", poss_n[i],i,a,b);
                i++;
            }
        }
    }
}

Upvotes: 0

Roee Gavirel
Roee Gavirel

Reputation: 19445

Your error is that you don't allocate place to save you results.

try this:

#include <stdio.h>
#include <stdlib.h>

#define MAX 31 // given that 31^2 = 961

int main(){
    int i = 0;
    int poss_n[(MAX + 1) * (MAX + 1)] = {0}; //<<- Give it a size
    int result; //<<- Using this to reduce calculation of the value multiple times.

    for (int a=0; a <= MAX; a++){
        for (int b=0; b <= MAX; b++){
            result = a*a + b*b;
            if (result  >= 100 && result  <= 999){ 
                poss_n[i] = result ;
                printf("%i\n", result);
                i++;
            }
        }
    }
}

Upvotes: 1

alexrider
alexrider

Reputation: 4463

int poss_n[] = {0};

This will define array holding one element, leading to Segfault later when you will try to access element with index > 1

Upvotes: 0

sje397
sje397

Reputation: 41812

Try:

int poss_n[(MAX + 1) * (MAX + 1)] = {0};

This way you allocate enough memory to store your answers.

Upvotes: 5

Related Questions