C++ Program abruptly ends after cin

Question

I am writing code to get the last digit of very large fibonacci numbers such as fib(239), etc.. I am using strings to store the numbers, grabbing the individual chars from end to beginning and then converting them to int and than storing the values back into another string. I have not been able to test what I have written because my program keeps abruptly closing after the std::cin >> n; line. Here is what I have so far.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using namespace std; 

char get_fibonacci_last_digit_naive(int n) {
cout << "in func";
if (n <= 1)
    return (char)n;

string previous= "0";
string current= "1";

for (int i = 0; i < n - 1; ++i) {
    //long long tmp_previous = previous;
    string tmp_previous= previous; 

    previous = current;

    //current = tmp_previous + current; // could also use previous instead of current
    // for with the current length of the longest of the two strings
    //iterates from the end of the string to the front
    for (int j=current.length(); j>=0; --j) {
        // grab consectutive positions in the strings & convert them to integers
        int t;
        if (tmp_previous.at(j) == '\0') 
            // tmp_previous is empty use 0 instead
            t=0;  
        else
            t = stoi((string&)(tmp_previous.at(j))); 
        int c = stoi((string&)(current.at(j)));
        // add the integers together
        int valueAtJ= t+c;
        // store the value into the equivalent position in current
        current.at(j) = (char)(valueAtJ); 
    }
    cout << current << ":current value"; 
}

return current[current.length()-1];
}

int main() {
int n;
std::cin >> n;

//char& c = get_fibonacci_last_digit_naive(n);  // reference to a local variable returned WARNING
// http://stackoverflow.com/questions/4643713/c-returning-reference-to-local-variable
cout << "before call";
char c = get_fibonacci_last_digit_naive(n);
std::cout << c << '\n';

return 0;
}

The output is consistently the same. No matter what I enter for n, the output is always the same. This is the line I used to run the code and its output.

$ g++ -pipe -O2 -std=c++14 fibonacci_last_digit.cpp -lm

$ ./a.exe
10

There is a newline after the 10 and the 10 is what I input for n. I appreciate any help. And happy holidays!

Answer 1

I'm posting this because your understanding of the problem seems to be taking a backseat to the choice of solution you're attempting to deploy. This is an example of an XY Problem, a problem where the choice of solution method and problems or roadblocks with its implementation obfuscates the actual problem you're trying to solve.

You are trying to calculate the final digit of the Nth Fibonacci number, where N could be gregarious. The basic understanding of the fibonacci sequence tells you that

fib(0) = 0 
fib(1) = 1 
fib(n) = fib(n-1) + fib(n-2), for all n larger than 1.

The iterative solution to solving fib(N) for its value would be:

unsigned fib(unsigned n)
{
    if (n <= 1)
        return n;

    unsigned previous = 0;
    unsigned current = 1;
    for (int i=1; i<n; ++i)
    {
        unsigned value = previous + current;
        previous = current;
        current = value;
    }
    return current;
}

which is all well and good, but will obviously overflow once N causes an overflow of the storage capabilities of our chosen data type (in the above case, unsigned on most 32bit platforms will overflow after a mere 47 iterations).

But we don't need the actual fib values for each iteration. We only need the last digit of each iteration. Well, the base-10 last-digit is easy enough to get from any unsigned value. For our example, simply replace this:

current = value;

with this:

current = value % 10;

giving us a near-identical algorithm, but one that only "remembers" the last digit on each iteration:

unsigned fib_last_digit(unsigned n)
{
    if (n <= 1)
        return n;

    unsigned previous = 0;
    unsigned current = 1;
    for (int i=1; i<n; ++i)
    {
        unsigned value = previous + current;
        previous = current;
        current = value % 10; // HERE
    }
    return current;
}

Now current always holds the single last digit of the prior sum, whether that prior sum exceeded 10 or not really isn't relevant to us. Once we have that the next iteration can use it to calculate the sum of two single positive digits, which cannot exceed 18, and again, we only need the last digit from that for the next iteration, etc.. This continues until we iterate however many times requested, and when finished, the final answer will present itself.

Validation

We know the first 20 or so fibonacci numbers look like this, run through fib:

0:0
1:1
2:1
3:2
4:3
5:5
6:8
7:13
8:21
9:34
10:55
11:89
12:144
13:233
14:377
15:610
16:987
17:1597
18:2584
19:4181
20:6765

Here's what we get when we run the algorithm through fib_last_digit instead:

0:0
1:1
2:1
3:2
4:3
5:5
6:8
7:3
8:1
9:4
10:5
11:9
12:4
13:3
14:7
15:0
16:7
17:7
18:4
19:1
20:5

That should give you a budding sense of confidence this is likely the algorithm you seek, and you can forego the string manipulations entirely.

Answer 2

Running this code on a Mac I get:

libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: basic_string before callin funcAbort trap: 6

The most obvious problem with the code itself is in the following line:

for (int j=current.length(); j>=0; --j) {

Reasons:

1. If you are doing things like current.at(j), this will crash immediately. For example, the string "blah" has length 4, but there is no character at position 4.
2. The length of tmp_previous may be different from current. Calling tmp_previous.at(j) will crash when you go from 8 to 13 for example.

Additionally, as others have pointed out, if the the only thing you're interested in is the last digit, you do not need to go through the trouble of looping through every digit of every number. The trick here is to only remember the last digit of previous and current, so large numbers are never a problem and you don't have to do things like stoi.

Answer 3

As an alternative to a previous answer would be the string addition. I tested it with the fibonacci number of 100000 and it works fine in just a few seconds. Working only with the last digit solves your problem for even larger numbers for sure. for all of you requiring the fibonacci number as well, here an algorithm:

std::string str_add(std::string a, std::string b)
{
    // http://ideone.com/o7wLTt

    size_t n = max(a.size(), b.size());
    if (n > a.size()) {
        a = string(n-a.size(), '0') + a;
    }

    if (n > b.size()) {
        b = string(n-b.size(), '0') + b;
    }

    string result(n + 1, '0');

    char carry = 0;

    std::transform(a.rbegin(), a.rend(), b.rbegin(), result.rbegin(), [&carry](char x,  char y)
    {
        char z = (x - '0') + (y - '0') + carry;
        if (z > 9) {
            carry = 1;
            z -= 10;
        } else {
            carry = 0;
        }
        return z + '0';
    });

    result[0] = carry + '0';

    n = result.find_first_not_of("0");
    if (n != string::npos) {
        result = result.substr(n);
    }

    return result;
}

std::string str_fib(size_t i)
{
    std::string n1 = "0";
    std::string n2 = "1";
    for (size_t idx = 0; idx < i; ++idx) {
        const std::string f = str_add(n1, n2);
        n1 = n2;
        n2 = f;
    }
    return n1;
}

int main() {
    const size_t i = 100000;
    const std::string f = str_fib(i);
    if (!f.empty()) {
        std::cout << "fibonacci of " << i << " = " << f << " | last digit: " << f[f.size() - 1] << std::endl;
    }

    std::cin.sync(); std::cin.get();
    return 0;
}

Answer 4

Try it with first calculating the fibonacci number and then converting the int to a std::string using std::to_string(). in the following you can extract the last digit using the [] operator on the last index.

int fib(int i)
{
    int number = 1;
    if (i > 2) {
        number = fib(i - 1) + fib(i - 2);
    }
    return number;
}

int main() {
    const int i = 10;
    const int f = fib(i);
    const std::string s = std::to_string(f);

    if (!s.empty()) {
        std::cout << "fibonacci of " << i << " = " << f << " | last digit: " << s[s.size() - 1] << std::endl;
    }

    std::cin.sync(); std::cin.get();
    return 0;
}

Avoid duplicates of the using keyword using.

Also consider switching from int to long or long long when your numbers get bigger. Since the fibonacci numbers are positive, also use unsigned.