std::_throw_out_of_range occurs from nowhere

Question

I'm an absolute beginner in c++. Literally. It's just been a week. Today I was writing a program to test how many iterations are needed to make a certain number palindromic. Here is the code:

#include <iostream>
#include <string>
#include <algorithm>

/*  This program calculates the steps needed
    to make a certain number palindromic.
    It is designed to output the values for
    numbers 1 to 1000
*/
using namespace std;

class number
{
public:
    string value;
    void reverse();
};

void number::reverse()
{
    std::reverse(value.begin(),value.end());
}

void palindrome(number num)
{
    string n=num.value;
    number reversenum, numsum, numsumreverse;
    reversenum=num;
    reversenum.reverse();
    numsum.value=num.value;
    numsumreverse.value=numsum.value;
    numsumreverse.reverse();
    int i=0;
    while (numsum.value.compare(numsumreverse.value) !=0)
    {
        reversenum=num;
        reversenum.reverse();
        numsum.value=to_string(stoll(num.value,0,10)+stoll(reversenum.value,0,10));
        numsumreverse.value=numsum.value;
        numsumreverse.reverse();
        num.value=numsum.value;
        i++;
    }
    cout << "The number " << n << " becomes palindromic after " << i << " steps : " << num.value << endl;
}

int main()
{
    number temp;
    int i;
    for (i=1; i<1001; i++)
    {
        temp.value=to_string(i);
        palindrome(temp);
    }
    return 0;
}

It goes on smooth for numbers upto 195. But, in case of 196 I get an error. It says:

terminate called after throwing an instance of 'std::out_of_range' what(): stoll

I cannot make out what to do. I tried starting from 196 but the error persisted. Any help will be greatly appreciated. :)

UPDATE: This time I tried to do it using ttmath library. But arghs! It again stops at 195 and doesn't even report an error! I might be doing something foolish. Any comments would be appreciated. Here's the updated code:

#include <iostream>
#include <string>
#include <algorithm>
#include <ttmath/ttmath.h>

/*  This program calculates the steps needed
    to make a certain number palindromic.
    It is designed to output the values for
    numbers 1 to 1000
*/
using namespace std;

class number
{
public:
    string value;
    void reverse();
};

void number::reverse()
{
    std::reverse(value.begin(),value.end());
}

template <typename NumTy>
string String(const NumTy& Num)
{
    stringstream StrStream;
    StrStream << Num;
    return (StrStream.str());
}

void palindrome(number num)
{
    string n=num.value;
    number reversenum, numsum, numsumreverse;
    reversenum=num;
    reversenum.reverse();
    numsum.value=num.value;
    numsumreverse.value=numsum.value;
    numsumreverse.reverse();
    ttmath::UInt<100> tempsum, numint, reversenumint;
    int i=0;
    while (numsum.value.compare(numsumreverse.value) !=0)
    {
        reversenum=num;
        reversenum.reverse();
        numint=num.value;
        reversenumint=reversenum.value;
        tempsum=numint+reversenumint;
        numsum.value=String<ttmath::UInt<100> >(tempsum);
        numsumreverse.value=numsum.value;
        numsumreverse.reverse();
        num.value=numsum.value;
        i++;
    }
    cout << "The number " << n << " becomes palindromic after " << i << " steps : " << num.value << endl;
}

int main()
{
    number temp;
    int i;
    for (i=196; i<1001; i++)
    {
        temp.value=to_string(i);
        palindrome(temp);
    }
    return 0;
}

UPDATE: It's solved. Some research suggested that 196 might be a Lychrel Number. And the result I was getting after implying the ttmath library is just reassuring that my algorithm works. I have tried it out for all the numbers upto 10000 and it gave out the perfect results. Here is the final code:

#include <iostream>
#include <string>
#include <algorithm>
#include <ttmath/ttmath.h>
#include <limits>

/*  This program calculates the steps needed
    to make a certain number palindromic.
    It is designed to output the values for
    numbers inside a desired range
*/
using namespace std;
string LychrelList;
int LychrelCount=0;

class number
{
public:
    string value;
    void reverse();
};

void number::reverse()
{
    std::reverse(value.begin(),value.end());
}

template <typename NumTy>
string String(const NumTy& Num)
{
    stringstream StrStream;
    StrStream << Num;
    return (StrStream.str());
}

void palindrome(number num)
{
    string n=num.value;
    number reversenum, numsum, numsumreverse;
    reversenum=num;
    reversenum.reverse();
    numsum.value=num.value;
    numsumreverse.value=numsum.value;
    numsumreverse.reverse();
    ttmath::UInt<100> tempsum, numint, reversenumint;
    int i=0;
    while ((numsum.value.compare(numsumreverse.value) !=0) && i<200)
    {
        reversenum=num;
        reversenum.reverse();
        numint=num.value;
        reversenumint=reversenum.value;
        tempsum=numint+reversenumint;
        numsum.value=String<ttmath::UInt<100> >(tempsum);
        numsumreverse.value=numsum.value;
        numsumreverse.reverse();
        num.value=numsum.value;
        i++;
    }
    if (i<200) cout << "The number " << n << " becomes palindromic after " << i << " steps : " << num.value << endl;
    else
    {
        cout << "A solution for " << n << " could not be found!!!" << endl;
        LychrelList=LychrelList+n+" ";
        LychrelCount++;
    }
}

int main()
{
    cout << "From where to start?" << endl << ">";
    int lbd,ubd;
    cin >> lbd;
    cout << endl << "And where to stop?" << endl <<">";
    cin >> ubd;
    cout << endl;
    number temp;
    int i;
    for (i=lbd; i<=ubd; i++)
    {
        temp.value=to_string(i);
        palindrome(temp);
    }
    if (LychrelList.compare("") !=0) cout << "The possible Lychrel numbers found in the range are:" << endl << LychrelList << endl << "Total - " << LychrelCount;
    cout << endl << endl << "Press ENTER to end the program...";
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    string s;
    getline(cin,s);
    cout << "Thanks for using!";
    return 0;
}

It's a really awesome community. Special thanks to Marco A. :)

UPDATE AGAIN: I've devised my own add() function that cuts the program's dependency on external libraries. It resulted in a smaller executable and faster performance too. Here is the code:

#include <iostream>
#include <string>
#include <algorithm>
#include <limits>

/*  This program calculates the steps needed
    to make a certain number palindromic.
    It is designed to output the values for
    numbers inside a desired range
*/
using namespace std;
string LychrelList;
int LychrelCount=0;

string add(string sA, string sB)
{
    int iTemp=0;
    string sAns;
    int k=sA.length()-sB.length();
    int i;
    if (k>0){for (i=0;i<k;i++) {sB="0"+sB;}}
    if (k<0) {for (i=0;i<-k;i++) {sA="0"+sA;}}
    for (i=sA.length()-1;i>=0;i--)
    {
        iTemp+=sA[i]+sB[i]-96;
        if (iTemp>9)
        {
            sAns=to_string(iTemp%10)+sAns;
            iTemp/=10;
        }
        else
        {
            sAns=to_string(iTemp)+sAns;
            iTemp=0;
        }
    }
    if (iTemp>0) {sAns=to_string(iTemp)+sAns;}
    return sAns;
}

void palindrome(string num)
{
    string n=num;
    string reversenum, numsum, numsumreverse;
    numsum=num;
    numsumreverse=numsum;
    reverse(numsumreverse.begin(),numsumreverse.end());
    int i=0;
    while ((numsum.compare(numsumreverse) !=0) && i<200)
    {
        reversenum=num;
        reverse(reversenum.begin(),reversenum.end());
        numsum=add(num,reversenum);
        numsumreverse=numsum;
        reverse(numsumreverse.begin(),numsumreverse.end());
        num=numsum;
        i++;
    }
    if (i<200) cout << "The number " << n << " becomes palindromic after " << i << " steps : " << num << endl;
    else
    {
        cout << "A solution for " << n << " could not be found!!!" << endl;
        LychrelList=LychrelList+n+" ";
        LychrelCount++;
    }
}

int main()
{
    cout << "From where to start?" << endl << ">";
    int lbd,ubd;
    cin >> lbd;
    cout << endl << "And where to stop?" << endl <<">";
    cin >> ubd;
    cout << endl;
    string temp;
    int i;
    for (i=lbd; i<=ubd; i++)
    {
        temp=to_string(i);
        palindrome(temp);
    }
    if (LychrelList.compare("") !=0) cout << "The possible Lychrel numbers found in the range are:" << endl << LychrelList << endl << "Total - " << LychrelCount;
    cout << endl << endl << "Press ENTER to end the program...";
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    string s;
    getline(cin,s);
    cout <<endl << "Thanks for using!";
    return 0;
}

You guys here have helped me a lot to find my own way. Thanks everyone. :)

Answer 1

You're overflowing long long since the last two valid values of num.value and reversenum.value are 7197630720180367016 and 6107630810270367917 which, added together, are way above the maximum size of a long long (9223372036854775807 on my machine). That will yield a negative value and spoil your next call to stoll

std::out_of_range is thrown if the converted value would fall out of the range of the result type or if the underlying function (std::strtol or std::strtoll) sets errno to ERANGE.

(reference)

• If you're trying to get the next smallest palindrome, you should use another approach like the one I explained here.

You can find a Live Example here

• If you prefer to/must continue with your approach you should either do the addition manually on the strings or use a bigint library (again take a look at here and modify the plusOne() function to your liking)

Answer 2

From http://www.cplusplus.com/reference/string/stoll/

If the value read is out of the range of representable values by a long long, an out_of_range exception is thrown.

The ll data type cant handle the string length. My debugger tells me 196 breaks on the value std::stoll (__str=\"9605805010994805921-\", __idx=0x0, __base=10)

The long long is too small.

You might want to do the addition on the strings themselves, without resorting to a numeric type.