c++- a very long integer promblem

Question

I'm trying to write a program that gets a really long number So at first I keep it as a string and am supposed to perform simple operators But I do not know how I'm supposed to store such a long number to do these things

Here's what I did, Header:

    class BigInteger
{
private:
    string number;

public:
    BigInteger();
    BigInteger(int);
    BigInteger(const char*);
    BigInteger(const BigInteger&);
    BigInteger(const BigInteger&&);
    //~BigInteger();

    void setValue(int);
    void setValue(const char*);
    //void setValue(const BigInteger&);

    string getnum();

    static BigInteger fromString(const char*);

    const BigInteger operator+(const BigInteger&) const;
    const BigInteger operator-(const BigInteger&) const;
    const BigInteger operator*(const BigInteger&) const;
    const BigInteger operator/(const BigInteger&) const; }

main:

    #include "BigInteger.h"

using namespace std;

int main()
{
    BigInteger a("2837456897658923563425345");

    BigInteger b("23784623874623874682736478236");

    BigInteger c = a + b; 

    c /= "4237467864237846"; 

    BigInteger d = a * b - c; 

}

thats the main and how i would like it to run, In the implementation of the functions, I managed to get all the constractors to work, but i dont know how to build the operators to work because there is no type that can contain that long numbers... what can i do?

maybe this can help https://stackoverflow.com/questions/10492820/summing-large-numbers — magicleon94, Aug 18 '17 at 10:21
You certainly _do_ know a type that can contain long numbers - it's a string, and you're already using it. Admittedly doing arithmetic on strings is tedious and inefficient, but it's obviously feasible if you can do addition and long division by hand. — Useless, Aug 18 '17 at 10:23
Pretty much like you'd do it by hand, For division, you can have a look at the synthetic division algorithm. Or you can use `boost.cpp_int` and enjoy your week end. — Michaël Roy, Aug 18 '17 at 10:46
I tried using a simple connection (a = c + c) but what happens is a concatenation for example 45 + 45 = 4545 rather than 90 — 420Friendlly, Aug 18 '17 at 10:50

KjMag · Answer 1 · 2017-08-18T11:22:39.630

1

Just keep it as a string and use the schemes for addition, subtraction, multiplication and division that you were taught at school. Remember adding and multiplying numbers while one of them is written under the other one? Basically this is what you have to implement as these algorithms process the number digit by digit just like you are about to process your string number char by char.

There are also some more clever algorithms e.g. for multiplication if you search the net for alternatives, but the methods that you know from school will do.

See this Wikipedia article that summarizes these basic methods:

https://en.wikipedia.org/wiki/Elementary_arithmetic

EDIT:

Addition example as requested: let's say that we want to add two numbers converted to strings and write the result as the variable called std::string res. if you have two numbers converted to string, e.g. "10" and "18", and you want to add them, take the last char of each of your strings (i.e. rightmost digits of the numbers - that is 0 and 8), add 0 + 8 and write it as the last char of the result string (i.e. the rightmost digit), then do the same with the next digits, i.e. 1 + 1, and write it as the next digit. Then res[0] == 2 and res[1] == 8, so the resulting string is "28".

Refer to your old school algorithms to learn what to do if the numbers have different number of digits or the result of digit addition is greater than 9.

edited Aug 18 '17 at 11:22

answered Aug 18 '17 at 10:35

KjMag

2,650
16
16

I do not know how to do it like you said I tried using a simple connection (a = c + c) but what happens is a concatenation for example 45 + 45 = 4545 rather than 90 – 420Friendlly Aug 18 '17 at 10:47
That's because this is how std::string's operator+ works - it was created specifically for concatenating two strings, not for adding numbers written as strings. Imagine what would happen if this operator worked the way you want and you used it on strings that don't contain digits, but letters or other characters? That wouldn't make sense. You have to implement this algorithm yourself. See the link I've provided. – KjMag Aug 18 '17 at 10:50
I understand what you're saying But still do not understand how I can implement the algorithm, then what I have is a string and I do not have a type that can hold a number so large that I will convert to it – 420Friendlly Aug 18 '17 at 10:59
But what do you need this type for? You can just hold your large number as string forever and not convert it at all. You can do all the arithmetic operations on this string representation. You have your BigInteger class - you can add/subtract/multiply/divide two numbers that belong to that class, you can print the result easily, you can compare these numbers using standard string operators and who cares that inside this class the number is represented as string if in the end people get the results they want? The user won't even be aware of that. This is the whole point of encapsulation. – KjMag Aug 18 '17 at 11:06
"You can do all the arithmetic operations on this string representation. You have your BigInteger class - you can add/subtract/multiply/divide two numbers that belong to that class", im new at c++ and i really dont know how to do it right can you please give me a simple exemple? – 420Friendlly Aug 18 '17 at 11:13
I've updated the answer and included the example you've requested. – KjMag Aug 18 '17 at 11:24
still dont get it its not works – 420Friendlly Aug 18 '17 at 11:49
You don't get the idea or your implementation gives incorrect results? These are two different things. – KjMag Aug 18 '17 at 11:51
The idea I understand but its use in so large numbers when they are not the same length is something I do not understand How do I even go to the last digit of any number? How I sum them at all are still chars rather than numbers If one number is greater than the other, the other digits must be copied as they are and that does not work out And what about a carrier? And how can I take the answer of each digit and put it in the right place in the result? What will be the size of the result at all? I just think it's not possible that way – 420Friendlly Aug 18 '17 at 12:06
It is possible and people do that - it's a very popular excercise. I've done it myself. The last digit of any number CONVERTED TO STRING is the last char of that string. I think you should start with some basic C++ course before doing anything else because the question you are asking now suggest that you lack the basic knowledge of string manipulation and ASCII representation. As for the carrier etc., it's really simple and I'm sure you can figure that out yourself if you put some effort into understanding how the school algorithm works. It's all described in the article I've linked. – KjMag Aug 18 '17 at 12:16

score 0 · Answer 2 · answered Aug 18 '17 at 10:32

There are libraries already implemented for this issue. What I can suggest to you if you want to implement your own code is to store the digits in vectors and learn about some operation algorithms. For example you may want to use Karatsuba's multiplication algorithm. https://en.wikipedia.org/wiki/Karatsuba_algorithm

c++- a very long integer promblem

2 Answers2