4
\$\begingroup\$

Recently I started learning c++ and I had an idea to make a calculator, that can take any imaginable number and I wrote this code:

#include <iostream>
#include <string>
#include <vector>

// Advanced calculator by xxnoflz;
// This calculator works best with summation, subtraction and multiplication
// and can work with numbers with ricilous amout of digits;
// But division and modulo works worse because of principle how division works;

void pause() {
    std::cout << '\n' << "Press <Enter> to continue...";
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    //std::cin.get(); // Use when not debug
} // PAUSE

int find_first_digit(std::vector<int>& vctr) {
    int iter{ int(vctr.size())-1 }; // Get the position of last number of array
    while (vctr[iter] == 0 && iter > 0) { --iter; } // Iterate while numbers are zeroes
    return iter;
} // Function to find and return the position of the first digit that is not zero

std::vector<int> operator+(std::vector<int>& first, std::vector<int>& second) {
    int f1{ find_first_digit(first) }; // Position of first digit of first num
    int f2{ find_first_digit(second) }; // Position of first digit of second num
    int first_digit_pos{ (f1 > f2) ? f1 : f2 }; // Get the largest number first position
    for (int iter{}; iter <= first_digit_pos; ++iter) { // Don't need to iterate through zeroes, just the numbers that matter
        first[iter] += second[iter];
        if (first[iter] >= 10) { // Overflow control
            first[iter] -= 10;
            first[iter + 1]++;
        }
    }
    return first;
}

std::vector<int> operator-(std::vector<int>& first, std::vector<int>& second) {
    bool negative{ false }; // Bool for negative check
    int size{ int(first.size()) };
    int f1{ find_first_digit( first ) }; // Position of first digit of first num
    int f2{ find_first_digit( second )}; // Position of first digit of second num
    int check{(f1 > f2) ? f1 : f2}; // Get the largest number first position
    if (first[check] < second[check]) { std::swap(first, second); negative = true; } // If the first num is smaller the second then result is negative
    for (int iter{}; iter <= check; ++iter) { // Don't need to iterate through zeroes, just the numbers that matter
        if (first[iter] - second[iter] < 0) {
            first[iter] += 10;
            first[iter+1]--;
        }
        first[iter] -= second[iter];
    }
    if (negative) { first[find_first_digit(first)] *= -1; } // Add to the first significant digit negative sign if number should be negative
    return first;
}

std::vector<int> operator*(std::vector<int>& first, std::vector<int>& second) {
    int size{ int(first.size()) };
    int f1{ find_first_digit(first) }; // Position of first digit of first num
    int f2{ find_first_digit(second) }; // Position of first digit of second num
    std::vector<int> result(size); // Create a vector to store answer in it
    for (int second_it{}; second_it <= f2; ++second_it) { // First: iterate through the second number to last significant digit
        int pos{ second_it }; // Create an integer with first position to add answer to
        for (int first_it{}; first_it <= f1 && pos < size; ++first_it, ++pos) { // Second: iterate through the first number to last significant digit 
            result[pos] += first[first_it] * second[second_it]; // And add the multiply of first and second digit to result with start position
            if (result[pos] >= 10) { // Overflow control
                result[pos + 1] += result[pos] / 10;
                result[pos] %= 10;
            }
        }
    }
    return result;
}

std::vector<int> operator/(std::vector<int>& first, std::vector<int>& second) {
    std::vector<int> result(first.size());
    bool stop{ true }; // Check to continue the subtraction or not
    while (stop) {
        first = first - second; // Subtract the second number from first
        stop = false;
        for (int digit : first) { if (digit > 0) { stop = true; } if (digit < 0) { return result; } } // If even one digit is positive then continue, but if one is negative return the
        result[0]++;                                                                                  // answer, and if all digits are zeroes then add 1 to answer and then return         

        for (int iter{}; iter < result.size(); ++iter) { //Overflow control with check of every digit
            if (result[iter] >= 10) {
                result[iter] -= 10;
                result[iter+1]++;
            }
        }
    }

    return result;
}

std::vector<int> operator%(std::vector<int>& first, std::vector<int>& second) {
    std::vector<int> check{ second }; std::vector<int> zero{0}; // Interesting feature here that I noticed is that when number evenly divides by another the second number
    first = first / second;                                     // stays unchanged, but when there is remainder it is stored in the second number. Pretty neat, huh!
    return (second == check) ? zero : second;                   // All we need to do here is compare the values of second number, when unchanged return zeroes but when changed  
}                                                               // return the second number.          

int main() {
    int extra_carry{ 10 }; // If some error happens it can be that amount of extra carry is insufficient
    std::string input{};           
    std::getline(std::cin,input); // Get input

    std::string nums{ "0123456789" };
    std::string first_num{ input.begin(),input.begin() + input.find_first_not_of(nums)};
    std::string second_num{ input.begin() + input.find_first_of(nums,input.find_first_not_of(nums)), input.end() };
    char oprt{input[input.find_first_of("+-*/%")]};
    int size{ int((first_num.size() > second_num.size()) ? first_num.size() : second_num.size()) + extra_carry }; // Parse input into first and second numbers and operator

    std::vector<int> first(size);
    std::vector<int> second(size);
    std::reverse(first_num.begin(),first_num.end()); std::reverse(second_num.begin(), second_num.end()); // Reverse in order to do calculations
    for (int it{}; it < first_num.length(); ++it) { first[it] = first_num[it] - '0'; }
    for (int it{}; it < second_num.length(); ++it) {second[it] = second_num[it] - '0'; } // Convert string to vector to do the calculations
    
    std::vector<int> result(size);
    switch (oprt) {
    case '+':
        result = first+second;
        break; 
    case '-':
        result = first-second;
        break; 
    case '*':
        result = first*second;
        break;
    case '/':
        result = first/second;
        break;
    case '%':
        result = first%second;
        break;
    default:
        std::cout << "Uknown operator!\n";
        break;
    }
    
    int start{ find_first_digit(result) }; // Find the first digit of result
    for (; start >= 0; --start) {
        std::cout << result[start];
    } // Print in reverse
    pause();
    return 0;
}

I know it's a little big, but I will take any suggestions to improve this code, thanks!

PS: The the divide and modulo function works slow

\$\endgroup\$
9
  • \$\begingroup\$ For one, it would be useful for a reader if you had explained that the operations work on vectors of digits, least significant digit first, without having to delve down to main() to figure that out :) \$\endgroup\$
    – AKX
    Dec 30 '21 at 11:52
  • 1
    \$\begingroup\$ Also, your use of { } to initialize variables seems a little unconventional... \$\endgroup\$
    – AKX
    Dec 30 '21 at 11:52
  • \$\begingroup\$ My use of { } is from learncpp.com, it was stated there that it is better \$\endgroup\$
    – xxnoflz
    Dec 30 '21 at 11:53
  • 2
    \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly. \$\endgroup\$
    – Edward
    Dec 30 '21 at 13:10
  • 1
    \$\begingroup\$ A conference presentation made when C++11 was new points out that using { } is universal and better, but he still likes to use = for simple types with simple values because he's used to it. A while back I made a post (I don't remember where I'm afraid) where I showed his slide and asked if we're ready to re-evaluate that style yet and use { } more. I would not fault him for using it consistently, and this is indeed taught to newcomers who don't have that old inertia. (The spacing is weird and hurts readability, though.) \$\endgroup\$
    – JDługosz
    Dec 30 '21 at 17:23
3
\$\begingroup\$

This looks like a nice start! I’m going to post something belated, and long, not because your code is especially bad but because I was sick at home and found myself writing a lot of examples.

I agree with @JDlugosz that you should name your Bignum class, and should refactor your library into functions.

Additionally, there are some changes you should make for efficiency.

Use the Right Data Type

Currently, you’re storing decimal digits in an array. This was historically common (and instructions for a form of it, Binary-Coded Decimal, are still in the x86_64 architecture).

The most efficient format for a computer, or to output in hex/octal/binary/base64, is probably to store your number as uint32_t. (If you ever are called upon to roll your own bignum library on some mainframe from the ’70s that supports modern C++ but not an exact 32-bit type, feel free to ask for an update.) This is half as fast as it theoretically might be on a 64-bit machine, but makes it much, much easier to get the high bits of multiplication than if you tried to use 64-bit words.

If you care about quickly converting to decimal digits, the most memory-efficient way of storing your Bignum is to encode digits in both the upper and lower four bits of each byte (historically called packed BCD). Decent compromises are storing one decimal digit in a char, or storing nine decimal digits in a uint_least32_t.

You want to store the digits in little-endian order, that is, from lowest digit to highest. This vastly simplifies addition, subtraction and multiplication. Think of your implementation as base 10, one that packs 9 decimal digits into a 32-bit word as base 1,000,000,000, and one that uses 32-bit binary arithmetic as using base 4,294,967,296. Then every little-endian bignum n is equal to the sum of the products n[i] times B to the power of i, for all indices i. Then the product of bignums m and n is the sum of m[i]*n[j] times B to the power of i+j for all indices i in m and j in n, and this just means iterating over both containers and storing the lower digit of each product in position [i+j] and the upper digit in position [i+j+1]. (Because (B**i * m_i) * (B**j * n_j) = B**(i+j) * m_i * n_j, and the product of the bignums is the sum of all such products of their chunks.)

To print the digits, you would iterate backwards, starting from the highest digit at rbegin(), until you reach rend(). Speaking of which,

Use const for Inputs You Don’t Modify

When I tried to write a few simple examples using constants, they didn’t compile, because your API doesn’t accept const Bignum.

Have a Function to Serialize Bignums

This is typically a member function named .to_string(), but you can also write a std::ostream& operator<< (ostream&, const Bignum&), which will make cout << someBignum; work.

But, to add a member function, you need to

Make Bignum a Class

In this case, you don’t want a Bignum to be a vector of int, you want it to have a vector of some kind of data. The rest of the application doesn’t need to know about this, and in fact, not exposing the rest of the program to implementation details makes it much easier for you to make changes that don’t break anything.

The skeleton of a Bignum class might look like this:

class Bignum {
  public:
  /* A Bignum can be initialized from the widest signed integral type
   * in <cstdint>, and defaults to 0.
   */
  Bignum() : Bignum(0) {};
  Bignum(std::intmax_t);
  // By the rule of 5:
  Bignum(const Bignum&) = default;
  Bignum(Bignum&&) = default;
  Bignum& operator= (const Bignum&) = default;
  Bignum& operator= (Bignum&&) = default;
  ~Bignum() = default;

When I tried an implementation, I added data members and several helper functions to the private: section of the class. Part of this was:

  private:
  using value_type = unsigned char;
  using buffer_type = std::vector<value_type>;
  using iterator = buffer_type::iterator;
  using const_iterator = buffer_type::const_iterator;
  using reverse_iterator = buffer_type::reverse_iterator;
  using const_reverse_iterator = buffer_type::const_reverse_iterator;

  bool is_negative; // Sign-and-magnitude representation.
  buffer_type buffer; // Each byte holds one base-10 digit, in little-endian order.

I also added a bit of syntactic sugar to simplify iterating through the container:

  // Utility functions to simplify buffer access.
  std::size_t size() const noexcept { return  buffer.size(); }
  value_type& operator[] (const std::size_t i) { return buffer[i]; }
  const value_type& operator[] (const std::size_t i)  const {return buffer[i];}
  constexpr const_iterator begin() const noexcept  { return buffer.begin(); }
  constexpr const_iterator end() const noexcept { return buffer.end(); }
  constexpr const_reverse_iterator rbegin() const noexcept { return buffer.rbegin(); }
  constexpr const_reverse_iterator rend() const noexcept { return buffer.rend(); }

The following should now work, within a friend or member:

for ( size_t i - 0; i < num.size() && num[i] == 0; ++i )
for ( auto it = num.begin(); it != num.end() && *it == 0; ++it )

With this as a class, your helper functions can now be either friends or members. I ended up making the helper functions for arithmetic members that were always called on the result object.

Your Code Goes Out of Bounds. Use Iterators.

I’m not going to make a comprehensive list of bugs, but here’s one that jumped out at me. find_first_digit has the lines

int iter{ int(vctr.size())-1 }; // Get the position of last number of array
while (vctr[iter] == 0 && iter > 0)

The vctr argument is a std::vector<int>, so its .size() can be 0. When that happens, iter is set to -1. You then use this value in the expression vctr[iter] before you check iter > 0. Inside the brackets, -1 actually converts to a huge size_t value. This will probably crash your program.

One suggestion: if a Bignum is another class that has a vector of the appropriate type, your constructor can maintain the invariant that every Bignum has at least one word of storage, and zero size cannot happen.

You would be better off writing this function with an iterator than with an index, but storing in little-endian order probably means you don’t need it at all.

Use Correct Semantics

This holds for all the binary operators. Let’s look at + for example.

std::vector<int> operator+(std::vector<int>& first, std::vector<int>& second)

Let’s pretend we implemented the accepted answer’s suggestion and put in a Bignum class. This section doesn’t depend on implementation details. As a quick-and-dirty fix, you can add using Bignum = std::vector<int>; to get this to compile.

Bignum operator+( Bignum& first, Bignum& second )

This is incorrect. The following code does not compile:

const Bignum one = {1}, two = one + one;

On Clang++ 13.0.0, I get the error,

error: invalid operands to binary expression ('const Bignum' (aka 'const vector<int>') and 'const Bignum')
note: candidate function not viable: 1st argument ('const Bignum' (aka 'const vector<int>')) would lose const qualifier
std::vector<int> operator+(std::vector<int>& first, std::vector<int>& second) {

Why is it giving us this error? You’re trying to add a constant Bignum, and your code doesn’t allow that. It doesn’t accept const Bignum arguments.

Why doesn’t it? If you remove the const from that declaration to get

Bignum one = {1}, two = one + one;

This line of code sets one equal to 2. (Like the old version of IBM Fortran where procedures could change the value of the constant 1 to -1 and make all the loops run backwards.)

Why does it change one to 2? You’re attempting to implement += instead of +. It would be a good idea to have +=. But the semantics are not quite right for that, either. You would write that as

Bignum& operator+= (Bignum& first, const Bignum& second)

You’ll notice two differences here. the right-hand-side is now a const Bignum&, so it will accept counter += one;. The left-hand side now has a & after the return type. This is huge: with that, you’re returning a reference to an existing Bignum. Without, you’re making a new copy of a Bignum. And a Bignum can get big. Clobbering the left-hand side and then making an extra copy is the worst of both worlds!

Let’s compile this version of operator+ and see what kind of code we get (clang++ 13.0.0 for Linux with -Os -march=x86-64-v4). We’ll look only at the code at the end of the function, since that’s what we’ll be tweaking:

.LBB1_11:
        mov     rdi, r14
        call    std::vector<int, std::allocator<int> >::vector(std::vector<int, std::allocator<int> > const&) [base object constructor]
        mov     rax, r14
        add     rsp, 8
        pop     rbx
        pop     r14
        ret

Of particular importance is the call instruction. That invokes the copy constructor to create a deep copy of your Bignum, as well as needing a fair amount of glue around it. If your Bignum is big, this time and memory could really add up.

Let’s now take the same code and change only the type signatures, to

Bignum& operator+=( Bignum& first, const Bignum& second )

and to make find_first_digit, which does not modify its input, take a const Bignum& as input.

The end of the function now compiles to

.LBB1_11:
        ret

This is a major optimization! I’m going to leave aside for the moment how to improve the calculations themselves. But let’s look at how we might use this as a bulding block. The code for -=, *= and /= can be similar.

The following will now compile successfully.

const Bignum one = {1};
Bignum counter = {0};

counter += one;

Use Move and Copy

So, we’ve refactored slightly and now have the same code as before in a +=` operator that works. How can we get this to work?

const Bignum two = one + one;

You’ll recall that your original implementation used the same code as +=, but returned a copy of the first argument. Let’s do that, but modify the copy, instead of the first operand. We end up with,

Bignum operator+ ( const Bignum& first, const Bignum& second )
{
  Bignum to_return = first;
  to_return += second;

  return to_return;
}

You might have noticed that I still don’t have a & after the return type, so I’m still not returning by reference. Does this mean my program is making a copy of the copy? It turns out, the answer used to be yes, this was the classic example of how it could bite you. There were various tricks I would use back in the ’90s to work around it. This aggravated enough programmers that, today, compilers are required to be smart enough to figure out that to_return (or whatever it’s named) is really just an alias for the return object, and not make a copy of it. So that code works just fine.

But we’re stuck making that one copy—except when we don’t have to. The only reason we couldn’t get away with overwriting one was that we might need it later, so we made a temporary copy and overwrote that instead. But what if our first argument were already a temporary copy that would never be used by anything else again? Then we’d be free to clobber it. And C++ has a syntax for that, Bignum&&. So, we can add an overload,

Bignum operator+ ( Bignum&& first, const Bignum& second )
{
  first += second;    
  return first;
}

Now, if we compile the line

Bignum four = one + one + one + one;

we see only a single copy get made, followed by three calls to +=. The first call to + had two constants as arguments, so it called the version that makes a copy of the first argument and calls += on the copy. It then returns that temporary copy. That means, each time we write + one again, the compiler sees that the first operand is an expiring temporary copy that it can overwrite, so it calls the optimized version.

Since addition is commutative, we can also do this when the second operand is a temporary copy, likr

Bignum w = x * (y + z);

The function signature here is

Bignum Operator+ ( const Bignum& first, Bignum&& second )

However, this line now breaks, because the compiler can’t tell whether to use the version that clobbers the left operand, or the right.

const Bignum four = (one + one) + (one + one);

To solve this, we need to provide one other overload:

Bignum operator+ ( Bignum&& first, Bignum&& second )

Writing these out as friend declarations for a class, we get:

  // Arithmetic functions can be friends of the class.
  friend Bignum& operator+= (Bignum&, const Bignum&);
  friend Bignum operator+ (const Bignum&, const Bignum&);
  friend Bignum operator+ (Bignum&&, const Bignum&);
  friend Bignum operator+ (const Bignum&, Bignum&&);
  friend Bignum operator+ (Bignum&&, Bignum&&);

  friend Bignum& operator-= (Bignum&, const Bignum&);
  friend Bignum operator- (const Bignum&, const Bignum&);
  friend Bignum operator- (Bignum&&, const Bignum&);
  friend Bignum operator- (const Bignum&, Bignum&&);
  friend Bignum operator- (Bignum&&, Bignum&&);

  friend Bignum& operator*= (Bignum&, const Bignum&);
  friend Bignum operator* (const Bignum&, const Bignum&);
  friend Bignum operator* (Bignum&&, const Bignum&);
  friend Bignum operator* (const Bignum&, Bignum&&);
  friend Bignum operator* (Bignum&&, Bignum&&);

  friend Bignum& operator/= (Bignum&, const Bignum&);
  friend Bignum operator/ (const Bignum&, const Bignum&);
  friend Bignum operator/ (Bignum&&, const Bignum&);
  friend Bignum operator/ (const Bignum&, Bignum&&);
  friend Bignum operator/ (Bignum&&, Bignum&&);

Nearly all of these can be implemented in terms of another function, so you only need to write an addition or multiplication loop once.

Compute the Quotient and Remainder at the Same Time

Most division algorithms will give you both, and this is one of the longest computations to have to restart all over again. See, for example, div_t.

You Can Optimize in Other Ways

Since you know in advance what the maximum size of any arithmetic result will be, you might reserve sufficient space for your buffer to be sure that it won’t need to resize. To reclaim the memory, you can shrink_to_fit. You might not necessarily want to do this if you have a lot of addition or multiplication by tiny numbers, or if you have a long chain of operations where it would be wasteful to reserve and shrink the buffer over and over again.

\$\endgroup\$
3
  • \$\begingroup\$ It should be a non-member to_string function, so generic code can use it as well as the built-in integer types. \$\endgroup\$
    – JDługosz
    Jan 3 at 15:23
  • \$\begingroup\$ operator+= should be a member, so there is no first (it is the implicit *this instead). \$\endgroup\$
    – JDługosz
    Jan 3 at 15:28
  • \$\begingroup\$ @JDługosz Good suggestion. You could also write += that way (and might prefer the way that resolves overloads). In this case, I thought it was illustrative to show how just changing the declaration of the operator+ function in the OP, and leaving the body the same, improved the code. \$\endgroup\$
    – Davislor
    Jan 3 at 15:59
5
\$\begingroup\$

You should name your Bignum type, rather than using vector<int> directly everywhere. For example, if you changed it to use 8-bit values rather than 32-bit ints (or whatever they are on your platform), you will have to change it in many many places and track them all down. Using vector<int> can be confused with any other usage that happens to represent data that way. So, make it a class containing the vector. And put that in a namespace along with the functions, and/or declare the arithmetic operators as "hidden friends" that are found using ADL that will only apply to your class, not every vector a program happens to use.

std::vector<int> result(size);
switch (oprt) {
    case '+':

Wait a minute, this is dropped directly into main? You should make functions. How do you expect other code to call your calculator if it's built into main and not packaged to be called by anyone?

Likewise with the printing... that should be an operator on your Bignum type, not ad-hoc code inside main. Your test code and examples should work on any Bignum implementation and not need to know about the details of this class (or rather what should have been a class).

You seem to have a lot of repeated common code like "overflow control". Make some common primitives as helper functions and implement the operators by calling them. Also, know what's in the standard library and don't write explicit loops and such to re-implement standard algorithms.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.