Big powers using vectors

[DDomjosa]

Hi, I am trying to write a program that would take a number (in this case 2) and raise it to some power (in this case 16) and store every digit separately in a vector. I'll need for this to work with huge powers like 2000+. This is what I have so far:

#include <iostream>
#include <vector>
int main()
{
    std::vector<int> digits;
    int number = 2, power = 16, counter = 0;
    digits.push_back(number);
    for (int i=0;i<power;i++)
    {
        if (((digits.size()-1)-counter) > 9)
        {
            digits.insert(digits.begin(), 0);
            digits[0] += (digits.size()-1)/10;
            digits[((digits.size()-1)-counter)] %= 10;
            counter++;
        }
        else digits[digits.size()-1] *= number;
    }
    for (int i=0;i<digits.size();i++)
        std::cout << digits[i];
}

This gets the value of 2^17 for some odd reason, instead of 2^16. Also it stops working after the value becomes bigger than 2^31 (at this, it returns a negative value, although the right one). After that it just gets a value of 0. I can't understand why this is, since I'm storing every digit separately there really shouldn't be any problem dealing with huge powers. Could someone look at my code and point out my mistakes? Thanks!

[Kevin C]

There are several problems with your code, but the biggest is that this task is in general more complex than you think it is (it is not very complex).

The real solution to this problem is explained thoroughly in my book:
http://www.amazon.com/Programming-Beginners-C-Kevin-Compton/dp/1511806982/

The reason why you are getting the wrong power is the line 7, which should go:
digits.push_back(1);
(otherwise you are adding one factor extra)

The reason why it doesn't work for numbers higher than 2^31 is that the condition in line 10 is never true. So, the array digits always ends up having a single element, which cannot be greater than 2^31.

If you want to solve this task by yourself, I suggest that you learn how to use a debugger.

[DDomjosa]

I did it by myself without a debugger (whatever that's supposed to be), here it is for others to find:

#include <iostream>
#include <vector>
bool singleDigits(std::vector<int>&);
void sortDigits(std::vector<int>&), fixDigits(std::vector<int>&);
int main()
{
    std::vector<int> digits;
    int number = 2, power = 1000;
    digits.push_back(1);
    for (int i=0;i<power;i++)
    {
        for (int j=0;j<digits.size();j++)
            digits[j] *= number;
        sortDigits(digits);
    }
    sortDigits(digits);
    for (int i=0;i<digits.size();i++)
        std::cout << digits[i];
}
void sortDigits(std::vector<int>& digits)
{
    if (!(singleDigits(digits)))
        fixDigits(digits);
}
bool singleDigits(std::vector<int>& digits)
{
    for (int i=0;i<digits.size();i++)
        if (digits[i] > 9)
            return false;
    return true;
}
void fixDigits(std::vector<int>& digits)
{
    for (int j=digits.size()-1;j>=0;j--)
    {
        if (digits[0] > 9)
            digits.insert(digits.begin(), 0);
        digits[j-1] += (digits[j]/10);
        digits[j] %= 10;
    }
}

Also, telling people to buy your book for one problem without actually helping them is kind of a dick move if you ask me.

[Kevin C]

Your original solution had too many problems. I didn't know where to start. I gave you the best recommendation that I know of.

By the way, it is not true that I didn't help you or that I didn't attempt to help you.

Also, don't you think it would be quite unfair to just give you a solution without you even trying?

Also, your new code doesn't work correctly, it crashes due to out-of-bounds array access. I recommend that you use a debugger.

[DDomjosa]

Ok, you helped me. You told me to push back a 1 instead of the number and that line 10 is useless. Thank you for that.

You attempted to give me the solution without me even trying, I just had to pay for it so there's that.

Also, my new code works perfectly, in cpp.sh it can calculate up to 2^75000 without any problems. On my computer, it calculated 2^200000 in 140 seconds. Couldn't show the full result because of it being 60k+ digits long, but the first 20 or so digits were correct so I assume it works. No idea how you manage to get a crash.

EDIT: Found a problem in my code that prevents it from working when using bigger numbers like 50. It requires a fix in lines 14-16 and one function is unnecessary. Here's the fixed version:

#include <iostream>
#include <vector>
bool singleDigits(std::vector<int>&);
void fixDigits(std::vector<int>&);
int main()
{
    std::vector<int> digits;
    int number = 2, power = 1000;
    digits.push_back(1);
    for (int i=0;i<power;i++)
    {
        for (int j=0;j<digits.size();j++)
            digits[j] *= number;
        while (!(singleDigits(digits)))
            fixDigits(digits);
    }
    for (int i=0;i<digits.size();i++)
        std::cout << digits[i];
}
bool singleDigits(std::vector<int>& digits)
{
    for (int i=0;i<digits.size();i++)
        if (digits[i] > 9)
            return false;
    return true;
}
void fixDigits(std::vector<int>& digits)
{
    for (int j=digits.size()-1;j>=0;j--)
    {
        if (digits[0] > 9)
            digits.insert(digits.begin(), 0);
        digits[j-1] += (digits[j]/10);
        digits[j] %= 10;
    }
}

[Kevin C]

I somehow guess that you are compiling with gcc/g++. To spot the error, define _GLIBCXX_DEBUG .

The program will crash at line 38. (Line 33 in new code)

I guess that the problem is in the expression digits[j-1], since j can go to 0.

[DDomjosa]

I am using a GCC compiler (Code::Blocks IDE), true. Don't know how to define that thing you told me, but I think I figured it out. This is the fixDigits function:

void fixDigits(std::vector<int>& digits)
{
    for (int j=digits.size()-1;j>=0;j--)
    {
        if (digits[0] > 9)
            digits.insert(digits.begin(), 0);
        if (j)
        {
            digits[j-1] += (digits[j]/10);
            digits[j] %= 10;
        }
    }
}

Now it doesn't try to access digits[-1], but still gives the right answer. Interestingly, setting the for loop to run while j>0 doesn't work, but the above code does (even though I'm pretty sure doing either is equivalent to doing the other).

[Kevin C]

Instructions for code::blocks can be found in a frame on this page:

http://www.programming4beginners.com/tutorial/chapter10/index-out-of-bounds

Then run the code to check whether it crashes or not.

Code::Blocks has a built-in debugger (gdb) accessible from the 'Debug' item on the menu.

I'm not sure whether the fixDigits function is actually correct now. There are several issues:
1. Inserting a new element will make the index j skip a digit.
2. If the digits[0] element changes, it's hard to see whether the first 'if' will be able to insert a new element correctly.

[DDomjosa]

Here, now if it inserts a new element it won't skip an element:

void fixDigits(std::vector<int>& digits)
{
    for (int i=digits.size()-1;i>=0;i--)
    {
        if (digits[0] > 9)
        {
            digits.insert(digits.begin(), 0);
            i++; //I think this is better for now, because i = digits.size()-1; would start the checking process all over again when it's already done.
        }
        if (i)
        {
            digits[i-1] += (digits[i]/10);
            digits[i] %= 10;
        }
    }
}

This doesn't crash the program when it runs with the define flag. Thanks for the help!

Oh, and all of the options in the debug menu are grayed out and I can't select them for some reason.

[Kevin C]

It seems to me that the code will work now.

And thanks for the thanks.