Assertion error while implementing a vector

[arun_lisieux]

QUESTION: The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

I was trying to solve this problem. I was previously suggested to use the "Sieve of Eratosthenes" Method to find the prime nos.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I came up with the following code. The code compiled without errors and warnings. But it has generated a run time error.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class factor
{
	public:
		int target;
		float target1;
		vector<int> buffer;
		vector<int> prime;
		vector<int>::iterator it;
		void primeno();
		void factors();
};

void factor::primeno()
{
	target = 120;
	target1 = 120.0;
	int flagprime = 3, count = 1, flagtrip = 0;
	for (int i=2; i<=target; i++)
	{
		buffer.push_back(i);
	}

	for (it = (buffer.begin()+count); it != buffer.end(); it++)
	{
		if ((*it)%2)
			buffer.erase(it);
	}
	count+=1;

	while (flagprime <= sqrt(target1))
	{
		for (it = (buffer.begin()+count); it != buffer.end(); it++)
		{
			if ((*it)%flagprime)
				buffer.erase(it);
		}
		count+=1;
		flagprime = *(buffer.begin()+count);
	}

	for (it = (buffer.begin()+count); it != buffer.end(); it++)
	{
		if ((*it)%flagprime)
			buffer.erase(it);
	}

	cout << "Prime No" << endl << endl;
	for (it = buffer.begin(); it != buffer.end(); it++)
	{
		cout << *it << "\t";
	}
	cout << endl << endl;
}

int main()
{
	factor inst;
	inst.primeno();
}

The error i obtained :

Debug Assertation failed!
Program : ......\project\Debug\Project.exe
File : C:\program files\microsoft visual studio 9.0\vc\include\vector
Line : 116

Expression : ("this->_Has_container()",0)

For information on how your program can cause an assertion failure, see the visual c++ documentations on asserts.

This is the part of the code that was present in the vector file at the line no mentioned during the error.

_Myt& operator++()
		{	// preincrement
		_SCL_SECURE_VALIDATE(this->_Has_container());
		_SCL_SECURE_VALIDATE_RANGE(_Myptr < ((_Myvec *)(this->_Getmycont()))->_Mylast);

Plz point out where i went wrong and help me correct this code.

[_adam_]

The problem occurrs first on about line 31. (Then a few more times later)

What's happening here is you are erasing the iterator it. This makes it invalid!

Following this your for loop attempts to call the incremental operator '++', however, now the iterator is invalid, the operation will fail, causing the assertion error you're having problems with.

If you check the documentation for std::vector<T>::iterator::erase(...) you will see that erase as a function returns the next element.

Due to this, a better way of performing this for loop(s) would be to use a while loop like this:

it = (buffer.begin()+count);
while( it != buffer.end() )
{
	if ((*it)%2)
	{
		it = buffer.erase(it); // this increments for you!
	}
	else
	{
		iter++; // if we don't erase just keep going through the list!
	}
}

Hope this helps.

Regards,
Adam

[Rashakil Fol]

Whoever suggested using the sieve of eratosthenes was being extremely dumb. You just need to factor your number; there's no reason to generate a long list of primes.

[arun_lisieux]

The problem occurrs first on about line 31. (Then a few more times later)

What's happening here is you are erasing the iterator it. This makes it invalid!

Following this your for loop attempts to call the incremental operator '++', however, now the iterator is invalid, the operation will fail, causing the assertion error you're having problems with.

If you check the documentation for std::vector<T>::iterator::erase(...) you will see that erase as a function returns the next element.

Due to this, a better way of performing this for loop(s) would be to use a while loop like this:

it = (buffer.begin()+count);
while( it != buffer.end() )
{
	if ((*it)%2)
	{
		it = buffer.erase(it); // this increments for you!
	}
	else
	{
		iter++; // if we don't erase just keep going through the list!
	}
}

Hope this helps.

Regards,
Adam

Thanks Adam. I will try out wat you have suggested.

[arun_lisieux]

Whoever suggested using the sieve of eratosthenes was being extremely dumb. You just need to factor your number; there's no reason to generate a long list of primes.

To be honest, my math is below par. Im working on improving it. Can you suggest me a better approach to this problem plz?

[_adam_]

Code Error
The code should have read:

it = (buffer.begin()+count);
while( it != buffer.end() )
{
	if ((*it)%2)
	{
		it = buffer.erase(it); // this increments for you!
	}
	else
	{
		// edit: the following line previously read 'iter++' ( my bad :o) )
		it++; // if we don't erase just keep going through the list!
	}
}

[arun_lisieux]

Code Error
The code should have read:

Hey Adam, I tried this code(with the alteration of it++) in place of the for loop. But i keep getting the same error. Do i have to replace any other part of the code?

[StuXYZ]

I was the original person who suggested using a sieve of eratosthenes. Now does this still hold? I believe so and here is why.
You were required to find the factors. The only factors of importance are prime factors, all other factors will be bigger since they are a combination of two or more prime factors. Hence you only need to test prime factors.

You now need a way to generate prime factors upto (at a maximum) the sqrt of the number. Then test them.

The SIMPLEST TO CODE method of finding prime factors is the sieve of eratosthenes.

In addition, the SoE is progressive, so after finding a new prime, it is tested and if a factor, the target number is divided and if the new target number is less than the square of the newly found factor, then the new target number is prime and the problem is finished.

I did then suggest that testing if a number is prime is easier than factoring and it is a good idea to test the target number first (because if it is prime then that is the end of the problem). [but this is a refinement of the original problem solution]

If you look a typical Pollard Lenstra number sieves, code for finding prime factors you are at >1000+ lines, that is serious code.

So Rashakil Fol please explain to us WHAT else you would do? you have said that I am dumb now back it up with a little maths/code.

[Rashakil Fol]

So Rashakil Fol please explain to us WHAT else you would do? you have said that I am dumb now back it up with a little maths/code.

Just use successive trial division. There's no need to explicitly skip all the non-prime numbers.

[StuXYZ]

His original problem was that he was doing just THAT

use successive trial division. There's no need to explicitly skip all the non-prime numbers.

Obviously, if you can do that quicly with a number like 600851475143, you have a seriously quick computer. That is just and only just in the standard PC / half-hour range, for older hardware and 32bit hardward it is in the 2-3hour range.

The reason for the orginal post (2 week ago ?) was that arun_lisieux was running on a slowish machine, and wasn't getting any output after a couple of minutes and thought that his program was broken.

So I stand by my original statement. I feel that I haven't been shown to be extremely dumb in this instance. [Although I accept that I am often :) ]

p.s. If I had set this as an assignment and someone handed in a simple loop, I would accept it, then add an extra assignment next week to factor say 15241580725499173 and that would turn 30min into a year or so -- and make the lazy student do a lot of work in a short space of time, while the others just changed the constant in their code.

p.p.s A good factor program takes 0.078seconds on my PC to do the 15...3 number above, a SoE based program takes 1.8seconds.
Algorithm is everything.

[Rashakil Fol]

The sieve of eratosthenes is slower than trial division. It takes Omega(n log n) operations when implemented naively, and Omega(n) operations with the best algorithm, which is just as good as trial division-based factorization.

[StuXYZ]

I wish to appologise. I think I have been very dumb. The S.o.E method does have a fundermental draw back. The only advantage is that it keeps the inital search under the machine limit for a longer time. This is not sufficient to offset the cost.

A naive search without dividing the target number down is obviously wrong route.

so returning to the original posters problem:
Algorithm should be:

i loop over 2->sqrt(N);
   while (!(N % i ))
     { 
       store i;
        N/=i;
      }

Then store N.

Note the while you need to check that the number doesn't have two or more identical factors.

hmmm I learnt something useful..... (as well as use brain before posting.. although I keep forgetting that!)

Thanks Rashakil.

[Rashakil Fol]

Well, I was being a bit inaccurate when I said you were being "extremely dumb". Everybody is dumb from time to time.

[_adam_]

Hey Adam, I tried this code(with the alteration of it++) in place of the for loop. But i keep getting the same error. Do i have to replace any other part of the code?

Could you post what you've got so far with changes made so I can see where you're at?

[arun_lisieux]

His original problem was that he was doing just THAT

Obviously, if you can do that quicly with a number like 600851475143, you have a seriously quick computer. That is just and only just in the standard PC / half-hour range, for older hardware and 32bit hardward it is in the 2-3hour range.

The reason for the orginal post (2 week ago ?) was that arun_lisieux was running on a slowish machine, and wasn't getting any output after a couple of minutes and thought that his program was broken.

So I stand by my original statement. I feel that I haven't been shown to be extremely dumb in this instance. [Although I accept that I am often :) ]

p.s. If I had set this as an assignment and someone handed in a simple loop, I would accept it, then add an extra assignment next week to factor say 15241580725499173 and that would turn 30min into a year or so -- and make the lazy student do a lot of work in a short space of time, while the others just changed the constant in their code.

p.p.s A good factor program takes 0.078seconds on my PC to do the 15...3 number above, a SoE based program takes 1.8seconds.
Algorithm is everything.

I've pasted the code which i came up with when i was trying to implement SoE and there seems to be some problems with the vector. Can you look into it plz?

[arun_lisieux]

StuXYZ & Rashakil, I was about to do wat stuXYZ has suggested. But i thought that i would check if im able to find prime nos as given in the wikipedia link (a simpler version). And i ended up in getting some problem with the Vector. I will do wat stuXYZ says once im done with this one. :)

[arun_lisieux]

Could you post what you've got so far with changes made so I can see where you're at?

Sorry, i forgot to replace all the FOR loops with the WHILE loop you gave me. When i replaced all of them, the code was working. But it deletes elements other than multiples of 2 from the vector. Actually I want the converse of this. So i reversed the IF's condition. Now i altered the code as this.

it = (buffer.begin()+count);
	while( it != buffer.end() )
	{
		if (!((*it)%2))
		{
			it = buffer.erase(it); 
		}
		else
		{
			it++;
		}
	}
	count+=1;

	while (flagprime <= 11)//sqrt(target1))
	{
		flag = false;
		it = (buffer.begin()+count);
		while( it != buffer.end() )
		{
			if (!((*it)%flagprime))
			{
				it = buffer.erase(it); 
				if (!flag) //Selecting next prime no for next iteration
				{
					flagprime = (*it);
					flag = true;
				}
			}
			else
			{
				it++;
			}
		}
		count+=1;
		//flagprime = *(buffer.begin()+count);
	}

In this code, the first WHILE loop which checks for multiples of 2 works fine. Coming on to the second loop, when i comment the outer WHILE loop, the multiples of 3 are removed. When i include the Outer loop to generalize it to removing multiples of other prime nos, i again get another Debug Assertion Error. This time, a different piece of the code from vector file is displayed during the Run Time.

_Myt& operator+=(difference_type _Off)
		{	// increment by integer
		_SCL_SECURE_VALIDATE(this->_Has_container());
		_SCL_SECURE_VALIDATE_RANGE(
			_Myptr + _Off <= ((_Myvec *)(this->_Getmycont()))->_Mylast &&
			_Myptr + _Off >= ((_Myvec *)(this->_Getmycont()))->_Myfirst);
		_Myptr += _Off;
		return (*this);
		}

I understand this has something to do with me trying to access the vector with an offset it = (buffer.begin()+count); How can i overcome this?

[_adam_]

First of all, I'd advise writing the comparison to remove even numbers as something like this:

if(  (*it) % 2 == 0 )

(I know both work, but this tends to be clearer.)

Ok, you've correctly identified the problem, in your debugger have you checked the value of count?

You'll probably find that this value is putting your iterator out of the range of your vector, i.e. you have 50 elements in the array, and you've asked your iterator to access element 51 of your vector (which doesn't exist).

That should be enough to get you moving forward,

All the best,
Adam

[arun_lisieux]

First of all, I'd advise writing the comparison to remove even numbers as something like this:

if(  (*it) % 2 == 0 )

(I know both work, but this tends to be clearer.)

Ok, you've correctly identified the problem, in your debugger have you checked the value of count?

You'll probably find that this value is putting your iterator out of the range of your vector, i.e. you have 50 elements in the array, and you've asked your iterator to access element 51 of your vector (which doesn't exist).

That should be enough to get you moving forward,

All the best,
Adam

Thanks Adam. I will check for the out of bounds possibility while using count.