Multiplying two ridiculously large number stored in an array of chars C++

Question

I have an assignment which requires me to write a program that multiplies two large numbers that are each stored in an array of characters with the maximum length of 100. After countless efforts and debugging and multiplying 10 digit numbers step by step and by hand I have now written the following piece of messy code:

#include <iostream>
#include <string.h>

using namespace std;

const int MAX_SIZE = 100;
int charToInt(char);
char IntToChar(int);
long long int pow10(int);
bool isNumber(char[]);
void fillWith0(char[], int);
void multiply(char[], char[], char[]);

int main(){

    char first_num[MAX_SIZE + 1], second_num[MAX_SIZE + 1], product[2 * MAX_SIZE + 1];
    cout << "A =\t";
    cin.getline(first_num, MAX_SIZE);
    cout << "B =\t";
    cin.getline(second_num, MAX_SIZE);
    multiply(first_num, second_num, product);
    cout << "A * B = " << product << endl;

    return 0;

}

int charToInt(char ch){
    return ch - '0';
}

char intToChar(int i){
    return i + '0';
}

long long int pow10(int pow){
    int res = 1;
    for (int i = 0; i < pow ; i++){
        res *= 10;
    }
    return res;
}

bool isNumber(char input[]){
    for (int i = 0; input[i] != '\0'; i++){
        if (!(input[i] >= '0' && input[i] <= '9')){
            return false;
        }
    }
    return true;
}

void fillWith0(char input[], int size){
    int i;
    for (i = 0; i < size; i++){
        input[i] = '0';
    }
    input[i] = '\0';
}

void multiply(char first[], char second[], char prod[]){
    _strrev(first);
    _strrev(second);
    if (isNumber(first) && isNumber(second)){
        fillWith0(prod, 2 * MAX_SIZE + 1);
        int i, j, k;
        long long int carry = 0;
        for (i = 0; second[i] != '\0'; i++){
            for (j = 0; first[j] != '\0'; j++){
                long long int mult = (pow10(i) * charToInt(first[j]) * charToInt(second[i])) + carry + charToInt(prod[j]);
                prod[j] = intToChar(mult % 10);
                carry = mult / 10;
            }
            k = j;
            while (carry != 0){
                carry += charToInt(prod[k]);
                prod[k] = intToChar(carry % 10);
                carry = carry / 10;
                k++;
            }
        }
        prod[k] = '\0';
        _strrev(first);
        _strrev(second);
        _strrev(prod);
    }
}

My problem is that it does not work with numbers that have more than 10 digits (1234567891 * 1987654321 works fine but nothing with more digits than that), as the output in those cases is a set of weird characters I presume the issue is somewhere something is overflowing and causing weird issues, although I have used long long int to store the only two numeric integers in the algorithm, doing so helped me bump from 6 digits to 10 but nothing more. Is there any suggestions or possibly solutions I can implement?

P.S. : As I mentioned before this is an assignment, so using libraries and other stuff is not allowed, I've already seen this implemented using vectors but unfortunately for me, I can't use vectors here.

Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackoverflow.com/rooms/245629/discussion-on-question-by-lonely-glitch-multiplying-two-ridiculously-large-numbe). — Machavity, Jun 15 '22 at 11:42
100 digits is not ridiculously big at all ... see [fast squaring](https://stackoverflow.com/q/18465326/2521214) ... I suggest to start with naive `O(n^2)` multiplication and once working port to Karatsuba ... advanced stuff like [Schönhage-Strassen multiplication](https://stackoverflow.com/questions/18577076) is for much much bigger numbers ... back to your code storing bigint stuff inside single `int` is a problem ,... using `pow(10,...)` for multiplication is ridiculous remember pow is higher operation than multiplication (instead just shift the char position in array...) — Spektre, Jun 16 '22 at 16:54

score 2 · Answer 1 · answered Jun 15 '22 at 10:06

The core mistake is using a long long int to store the intermediate multiplied number. Instead, use another char[] so the core of your multiply becomes simply:

for (i = 0; second[i] != '\0'; i++){
  char scratch[2 * MAX_SIZE + 1];
  // Fill up the first i positions with 0
  fillWith0(scratch, i);
  // Store second[i] * first in scratch, starting at position i.
  // Make sure to 0-terminate scratch.
  multiplyArrWithNumber(&scratch[i], intToChar(second[i]), first);
  // Add pairwise elements with carry, stop at the end of scratch
  addArrays(scratch, prod);
}

Multiplying two ridiculously large number stored in an array of chars C++

1 Answers1