[jink]

i have written this code for question from project euler:
Q)The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

/*if sequence is 13,40,20,10,5,16,8,4,2,1 remember the indexes 13->1,40->2,20->3,10->4,5->5,16->6,8->7,4->8,2->9,1->10
now if we want to know length of sequence starting at 20 we do 10-3+1 */
/*and if we have completed numbers till 17 then we have the record of the lengths of all the
sequences from 1 to 17 plus the lengths of the sequences of , numbers that occured in those
1 to 17 sequences*/
/*a number cannot appear more than once in a sequence,otherwise the sequence will not converge,so no
worry about saving the same number twice*/
/*how much big should be the array which stores the elements of the current sequence*/
/*that is how big can be a sequence??*/
/*so make a linked list for the sequence*/

#include<stdio.h>
#include<stdlib.h>
#define MAX 1000000 	//1 million
#define PARITY 2

struct element{
	unsigned long int number,pos;//pos is the position of that number in the sequence
	struct element *next;
};

void add_ele_end(struct element *,struct element *);
void *give_mem(void);
unsigned long int big_give(unsigned long int,unsigned long int);

int main(){
	/*0th position in the lengths array is vacant since numbers start from 1*/
	unsigned long int i=0,number,lengths[MAX+1],maxlen=0;//check the range,lengths is for storing what is the length of sequence atarting with that number

	/*initialise the lengths array to zero*/
	while(i<=MAX)
		lengths[i++]=0;

	number=1;
	/*start the loop of numbers*/
	while(number<=MAX){
	/*start the inner loop*/
		char seq_over='0';
		struct element *first=NULL,*iterate=NULL,*temp=NULL;
		unsigned long int position=1,arr_num=number;//position is for number of elements already counted in the array

		while(seq_over!='1'){
			struct element *filled;
			//arr_num is the number in the array,which can be incremented or decremented
			/*if got the number in lengths array or got 1 exit the loop*/
			if(lengths[number]!=0){
				big_give(maxlen,position+lengths[arr_num]);
				seq_over='1';
			}
			else{
				++position;
				if( (filled=(struct element *)give_mem()) == NULL){
					printf("Memory allocation failed\n");
					return 1;
				}
				if(position==1)
					first=filled;
				filled->number=arr_num;
				filled->number=position;
				filled->next=NULL;
				/*adding the number in the linked list*/
				add_ele_end(first,filled);
			}
			if(arr_num==1){
				big_give(maxlen,position);
				seq_over='1';
			}
			/*if not find next element and add previous element to seq array*/
			if(seq_over!='1'){//find next element in the sequence,add it,increment the position
				if(arr_num%PARITY==0)//even number
					arr_num=arr_num/2;
				else
					arr_num=arr_num*3+1;
			}
			else{	//add the elements and the corresponding length of array in lengths array
				iterate=first;
				if(iterate==NULL)//no elements filled
					;
				else{
					while((iterate->next)!=NULL){
						lengths[iterate->number]=filled->pos;
						iterate=iterate->next;
					}
				}
			}
		}
		/*free the linked list*/
		iterate=first;
		if(iterate==NULL)
			;
		else{
			while( (iterate->next) !=NULL){
				temp=iterate;
				iterate=iterate->next;
				free((void*)temp);
			}
			free((void*)iterate);//last element remaining free
		}
		++number;
	}

	printf("The maximum lenth of sequence is:%ld\n",maxlen);
	return 0;
}

void add_ele_end(struct element *start,struct element *fill){//add element at the end
	struct element *pointer=start;
	if(pointer==NULL)//means that first element itself is not there
		pointer=fill;
	else{
		while(pointer->next!=NULL)
			pointer=pointer->next;
		pointer->next=fill;
		fill->next=NULL;
	}
	return;
}

void *give_mem(void){
	return malloc(sizeof(struct element));
}

unsigned long int big_give(unsigned long int a1,unsigned long int a2){
	return a1>=a2?a1:a2;
}

No compile time error.
program gets killed.

terminal message after running the program:
Killed

using gdb
Program terminated with signal SIGKILL, Killed.
The program no longer exists.

so i thought there must be some memory problems since there are no compile time errors.so i tried using valgrind plugin from code::blocks.

so i selected Run Valgrind::MemCheck and i got
valgrind --version
execvp(valgrind, --version) failed with error 2!
valgrind --leak-check=yes --xml=yes "bin/Debug/valtry"
execvp(valgrind, --leak-check=yes, --xml=yes, bin/Debug/valtry, ) failed with error 2!

then i selected Run Valgrind::Cachegrind and i got
valgrind --version
execvp(valgrind, --version) failed with error 2!
valgrind --tool=cachegrind "bin/Debug/valtry"
execvp(valgrind, --tool=cachegrind, bin/Debug/valtry, ) failed with error 2!

but i am not able to know what is happening with the memory or on which line error occurs.is this because valgrind is not able to detect the error or there is some problem with the valgrind plugin?

This post has been edited by jink: 27 July 2012 - 11:16 PM

[Salem_c]

> unsigned long int i=0,number,lengths[MAX+1],maxlen=0;
You're creating a very large array on the stack.

Most desktop operating systems limit each process to between 1MB and 8MB of stack space.
1M int's is going to be 4MB on many machines.

A simple fix is
static unsigned long int lengths[MAX+1];

Oh, and all the casting you're doing on pointers when calling malloc and free are a waste of time.

[jink]

if we declare it static i don't understand why the process can be allocated space which could not be allocated earlier?
also i dont understand why casting is a waste of time?you mean its automatically done by the compiler?
yeah,and i read this link on static variables.

[Skydiver]

By declaring it static, you are telling the compiler that you need access to the variable later when the scope is re-entered, and you expect the variable to be in the state that you last left it. This tells the compiler to allocate space for that variable in the data segment of your program, rather than allocate space for the variable at run time on the stack. Variables on the stack will be contain whatever was last using up that memory on the stack -- essentially random and uninitialized.

This is the downside of learning C/C++ without having at least a quick introduction to assembly language, or a rudimentary explanation of how traditional computer programs work.

This post has been edited by Skydiver: 28 July 2012 - 12:26 AM

[jink]

I didnt know that.let me try it.
No.its not working.program gets killed.

This post has been edited by jink: 28 July 2012 - 12:29 AM

[Skydiver]

Here is a good way to see static in action:

#include <iostream>

using namespace std;

int fi = 0;

void Fee()
{
    static int fo = 0;
    int fum = 0;

    cout << "fi: " << fi << endl;
    cout << "fo: " << fo << endl;
    cout << "fum: " << fum << endl;

    fi++;
    fo++;
    fum++;
}

int main()
{
    for(int i = 0; i < 10; i++)
        Fee();
    return 0;
}

But is it getting killed for the same reason? Have you tried running your program under a debugger?

[jink]

yeah.same reason.
Program terminated with signal SIGKILL, Killed.
The program no longer exists.

that's why i wanted to use valgrind to detect the problem.

I knew about the static variable lifetime but i didnt know about the memory allocation.

This post has been edited by jink: 28 July 2012 - 12:44 AM

[Skydiver]

Seems to work for me after I added static...

	unsigned long int i=0,number,maxlen=0;//check the range,lengths is for storing what is the length of sequence atarting with that number
	static unsigned long int lengths[MAX+1];

[jink]

still not working for me.i don't know why.i have definitely saved the file and compiled it again,so it can't happen that i am running the old file.

[Skydiver]

Try declaring lengths as a real global, then. Move line 2 from my post above up to line 21 in your original post. If it still doesn't work, post your current code, again.

This post has been edited by Skydiver: 28 July 2012 - 12:57 AM

[jink]

not working.

/*if sequence is 13,40,20,10,5,16,8,4,2,1 remember the indexes 13->1,40->2,20->3,10->4,5->5,16->6,8->7,4->8,2->9,1->10
now if we want to know length of sequence starting at 20 we do 10-3+1 */
/*and if we have completed numbers till 17 then we have the record of the lengths of all the
sequences from 1 to 17 plus the lengths of the sequences of , numbers that occured in those
1 to 17 sequences*/
/*a number cannot appear more than once in a sequence,otherwise the sequence will not converge,so no
worry about saving the same number twice*/
/*how much big should be the array which stores the elements of the current sequence*/
/*that is how big can be a sequence??*/
/*so make a linked list for the sequence*/

#include<stdio.h>
#include<stdlib.h>
#define MAX 1000000 	//1 million
#define PARITY 2

static unsigned long int lengths[MAX+1];

struct element{
	unsigned long int number,pos;//pos is the position of that number in the sequence
	struct element *next;
};

void add_ele_end(struct element *,struct element *);
void *give_mem(void);
unsigned long int big_give(unsigned long int,unsigned long int);

int main(){
	/*0th position in the lengths array is vacant since numbers start from 1*/
	unsigned long int i=0,number,maxlen=0;//check the range,lengths is for storing what is the length of sequence atarting with that number
	/*initialise the lengths array to zero*/
	while(i<=MAX)
		lengths[i++]=0;
	
	number=1;
	/*start the loop of numbers*/
	while(number<=MAX){
	/*start the inner loop*/
		char seq_over='0';
		struct element *first=NULL,*iterate=NULL,*temp=NULL;
		unsigned long int position=1,arr_num=number;//position is for number of elements already counted in the array
		
		while(seq_over!='1'){
			struct element *filled;
			//arr_num is the number in the array,which can be incremented or decremented
			/*if got the number in lengths array or got 1 exit the loop*/
			if(lengths[number]!=0){
				big_give(maxlen,position+lengths[arr_num]);
				seq_over='1';
			}
			else{
				++position;
				if( (filled=(struct element *)give_mem()) == NULL){
					printf("Memory allocation failed\n");
					return 1;
				}
				if(position==1)
					first=filled;
				filled->number=arr_num;
				filled->number=position;
				filled->next=NULL;
				/*adding the number in the linked list*/
				add_ele_end(first,filled);
			}
			if(arr_num==1){
				big_give(maxlen,position);
				seq_over='1';
			}
			/*if not find next element and add previous element to seq array*/
			if(seq_over!='1'){//find next element in the sequence,add it,increment the position
				if(arr_num%PARITY==0)//even number
					arr_num=arr_num/2;
				else
					arr_num=arr_num*3+1;	
			}
			else{	//add the elements and the corresponding length of array in lengths array
				/*filled is now used so we can now use it for iteration along the list*/
				iterate=first;
				if(iterate==NULL)//no elements filled
					;
				else{
					while((iterate->next)!=NULL){
						lengths[iterate->number]=filled->pos;
						iterate=iterate->next;
					}
				}
			}
		}
		/*free the linked list*/
		iterate=first;
		if(iterate==NULL)
			;
		else{
			while( (iterate->next) !=NULL){
				temp=iterate;
				iterate=iterate->next;
				free((void*)temp);
			}
			free((void*)iterate);//last element remaining free
		}
		++number;
	}
	
	printf("The maximum lenth of sequence is:%ld\n",maxlen);
	return 0;
}

void add_ele_end(struct element *start,struct element *fill){//add element at the end
	struct element *pointer=start;
	if(pointer==NULL)//means that first element itself is not there
		pointer=fill;
	else{
		while(pointer->next!=NULL)
			pointer=pointer->next;
		pointer->next=fill;
		fill->next=NULL;
	}
	return;
}

void *give_mem(void){
	return malloc(sizeof(struct element));
}

unsigned long int big_give(unsigned long int a1,unsigned long int a2){
	return a1>=a2?a1:a2;
}

i am now trying manually to find some error,in allocation and freeing up memory.will take some time to get the error.will keep this thread open.if i get the error i will tell immediately.

[Skydiver]

Does it also crash for you when MAX is 100?

BTW, your line #74 computes new values of arr_num that make it go beyond MAX.

jink, on 28 July 2012 - 01:07 AM, said:

not working.

Not working as in you are still getting: "Program terminated with signal SIGKILL, Killed." ?

Or not working as in your program isn't computing your expected results?

[jink]

works for MAX 100(in the sense running without getting killed).thanks.i will figure out the rest.