Square Root Code C++ without sqrt()

Question

I have to create a code where the user inputs a number which is a perfect square, and I have to show its root. I've made this code, but I'm getting Segmentation Fault 11 , in this piece: int j = squareRootVector[i]; squareRoot.push_back(j);. I can't change the code too much, so is there a way that I can do that?

#include <iostream>
#include <vector>

using namespace std;


int main() {

cout <<

 "Enter the number:\n";

    int input;
    int number = input;
    int divider = 2;
    vector<int> squareRootVector;
    vector<int> squareRoot;

    cin >> number;

    for(int divider = 2; number > 1; divider++) {
        while((number % divider) == 0) {
            number /= divider;
            cout << number << endl;
            squareRootVector.push_back(divider); 
        }
    }


    for(int i = 0; i < squareRootVector.size(); i++) {
        cout << squareRootVector[i] << " ";

        /*******PROBLEM*******/
        if(squareRootVector[i] == squareRootVector[i+1]) {
            int j = squareRootVector[i];
            squareRoot.push_back(j);
        }
        /*********************/
    }

    int root;

    for (int i = 0; squareRoot.size(); i++) {
        root = root * squareRoot[i];
    }

    cout << "Square Root of " << input << " is: " << root << endl;


    return 0;
}

I suspect the problem is here: `squareRootVector[i+1]`. Since `i` is the last element of the vector, `i+1` is out of bounds — kmdreko, Sep 27 '17 at 07:33
`squareRootVector[i+1]` is out of bounds for `i == size()-1` — 463035818_is_not_an_ai, Sep 27 '17 at 07:33
After you will fix this problem (on which you already got some proposal), you should also be careful about variable `input` which is not initialized. It is supposed to remember user input, so you should better read the input in it (`cin >> input`), and then assign the value to `number` (which seems to be a working variable in your algorithm). I think the code will be clearer. — M. Yousfi, Sep 27 '17 at 08:15

score 3 · Answer 1 · answered Sep 27 '17 at 07:33

The behaviour on accessing squareRootVector[i+1] with i just one below size (which your loop constaint allows) is undefined.

Consider writing

for (std::size_t i = 1; i < squareRootVector.size(); i++) {

instead, and rebasing the for loop body accordingly. I've also slipped in a change of type for i.

score 1 · Answer 2 · edited Sep 27 '17 at 08:39

1

Shortly, the problem is that the last cycle in the last "for":

for(int i = 0; i < squareRootVector.size(); i++)

has the following line in it:

squareRootVector[i] == squareRootVector[i+1];

This is an "out of limits" error: squareRootVector only has squareRootVector.size() elements (let's say n), and the elements are indexed from 0 to n-1.

squareRootVector[i+1] in the last cycle points one element after the last one of squareRootVector, which is undefined behavior.

edited Sep 27 '17 at 08:39

YSC

38,212
9
96
149

answered Sep 27 '17 at 07:38

Calin Ceteras

206
1
4

1

"one element after the end" is misleading because usually it is `end` that points to one past the last element – 463035818_is_not_an_ai Sep 27 '17 at 07:41
So if I add `if( (i+1) < squareRootVector.size())` before `if(squareRootVector[i] == squareRootVector[i+1])` it should work, no? – Dudi Sep 27 '17 at 07:49
@tobi303: the "end()" points to past the last element. I was literally talking about the end. Dudi: It wouldn't crash. – Calin Ceteras Sep 27 '17 at 08:38
1

@CalinCeteras I took on me to slightly edit your answer, feel free to rollback it. – YSC Sep 27 '17 at 08:40
in c++ "end" literally refers to one past the last element. Saying `array[i+1]` is one past the end is confusing – 463035818_is_not_an_ai Sep 27 '17 at 08:41

score 0 · Answer 3 · answered Sep 27 '17 at 08:16

Using vector::iterator is proper way.

for(vector<int>::iterator it = squareRootVector.begin(); it != squareRootVector.end(); ++it)
{
    if( (it+1) == squareRootVector.end() )
    {
        //what to do if there's no next member???
        break;
    }

    if( *it == *(it+1) )
    {
        squareRoot.push_back(*it);
    }
}

score 0 · Accepted Answer · answered Sep 27 '17 at 08:50

Thanks for the answers, guys. I've ended up with this code:

#include <iostream>
#include <vector>

using namespace std;


int main() {

cout << "Enter the number:\n";

int input = 0;
int number = 0;
cin >> input;
number = input;
int divider = 2;
vector<int> squareRootVector;
vector<int> squareRoot;



for(int divider = 2; number > 1; divider++) {
    while((number % divider) == 0) {
        number /= divider;
        squareRootVector.push_back(divider); 
    }
}

int vectorSize = squareRootVector.size() - 1;


for(int i = 0; i < vectorSize; i++) {
    if(squareRootVector[i] == squareRootVector[i+1]) {
        int j = squareRootVector[i];
        squareRoot.push_back(j);
    }
}

int root = 1;

for (int i = 0; i < squareRoot.size(); i++) {
    root = root * squareRoot[i];
}

cout << "Square Root of " << input << " is " << root << endl;


return 0;
}

Square Root Code C++ without sqrt()

4 Answers4