Divide two many-digit numbers digit-by-digit!!!

[roise0r]

Hello all! i am taking a Computer Science 2 class at a local community college and we have this simple C++ program to write that divides two large integers. The catch is that the numbers are represented by single digits sitting in an array of integers, so actually there is no real big number, there are only a bunch of single-digit integers sitting in their own space in a array. As you can imagine, that makes the division as we know it - impossible!
Throw any suggestions that you might have on how can i divide any two large integers digit-by-digit. for example 2115/28 you would start by taking in consideration only the digit '2' in the number '28'. The divisor can be larger then 'int' type or even 'long'. These big numbers can have as much digits as the max_int_type value permits - up to 65535 digits.

I will welcome any suggestions

[BlahBlah]

Does each number have its own array?

[helios]

Impossible? Hardly.
For a/b:

div;
for (div=0;a>=b;a-=b,div++);
//div now holds the result of the integral division. 

Of course, you would need to first implement the subtraction algorithm.

[Zaita]

Here is a quick and dirty subtraction algo. It doesn't work if array2 is greater than array1. But meh, it's quick and dirty to show you it can be accomplished.

void subtractArrays(int array1[], int length1, int array2[], int length2) {
  // Array1 / Array2;
  int *answer = new int[length1];
  memset(answer, 0, sizeof(int)*length1);

  for (int i = length1-1; i >= 0; --i) {
    if (array1[i] < 0) {
        array1[i-1]--;
        array1[i] += 10;
    }

    int temp = array1[i] - array2[i];
    if (temp < 0) {
      temp = 10 + temp;
      array1[i-1]--;
    }
    answer[i] = temp;
  }
  
  delete [] answer;
}

[xabnu]

Have you thought of ways to represent good ol' fashion long division?

Would it be legal to loop through and add something to the value of the next element? (as in, the remainder)

[int main]

Why don't you create the "real" Integers first?

I mean, it's quite simple. Loop through the array and add the digits after multiplication with 10 raised to the digits power.

So, if you got three digits

"real" Integer = first digit * 10^2 + second digit * 10^1 + third digit * 10^0

or more dynamic: digit * 10^(length of array - 1 - position of digit in array)


int main

[buffbill]

How about this:
1. Combine the elements of each array into a string with a loop. Say s1 for number and s2 for devisor.
2. Apply atol to convert strings to long type numbers.
like long n = atol(s1) and m=atol(s2)
3. divide n by m.
You probably need #include<iostream> and #include<stdlib>

[helios]

O_O
Arbitrary precision values may be thousands of digits long.

[Zaita]

@xabnu: Helios's method is a simple implementation of how to divide the numbers. You just need a subtraction method (as I provided a basic one)

@int main: that won't work. no data type supports a number with a length of 65535 digits maintaining each digit correctly. This is why an array was picked (I assume).

@bufbill: A long isn't big enough to hold a number with 65535 digits.


This is an array of integers (0-9) that together make a number upto 65535 digits long. No standard data type supports this. So it's really building a new larger numeric data-type by using an array of ints (albeit, I'd use an array of bytes (or an array of an array of bits) to save space).

[satm2008]

Though I saw this post lately, it is interesting.
About the number of digits, any length larger than regular data types like long, long long etc, it does not matter how big it is, may be 65535 digit long.
It would be no different if it is a 20 digit number or 65535 digit number. Same logic would apply.
Example, look at the desktop calculator that can take a number normally longer than a regular data type could hold in C++.

@roise0r
This can be done, but not in a simple C++ code. Writing code to perform such repetitive divisions, it would be another array of (single digit) integers that keeps holding the resultant values during the calculation.

And question is, if I give 1247539425008 that divided by 28 it would start taking digits from right to left, meaning, starting with 8 and then 2, right?
And, then would the result be divided further by 2 and storing the resultant array/variable???
For instance, 1247539425008 divided by 8 gives 155942428126 and then the 155942428126 divided by 2 will give 77971214063. Is that the way, you want to see? I guess so.

However this is possible, but not in a simple code. In fact, putting the digit numbers in array subscripts would be easier than other way in one number form. And about the code, have an idea popped in mind but not in code the code form yet. If time permits, I would come back with a code snippet.

Good luck :)

[Zaita]

satm2008: Helios's code does the division, my sample is the basis of the subtraction required for Helios's division.

That code will work.

[buffbill]

Thanks Zaita. I'm out. I miss read the last bit. I've never heard of a number this big.

[satm2008]

Here is another simple way, in one loop calculation.

where fArray is the first array has values to be divided (dividend)
sArray is the divisor
and rArray is the resultantArray storing the quotient.



for (j = 0, d = sArray[i], k =0; j < fArrLength; j++)
{
//check leading digit has a value, if so, combine it with the current digit
// placing the leading digit in 10's place of the current number
num = (j > 0) ? (fArr[j-1]*10)+fArr[j] : fArr[j];

//if the current dividend (ie, num) is lower than the divisor, then skip it
if (num < d) {
rArr[k++] = 0;
continue;
}

r = num % d; // note the reminder, if any
c = num / d; // find the result/quotient too
rArr[k++] = c; // store the result in resultantArray
fArr[j] = r; // and reset the divident in firstArray with the current reminder
}


But I am not sure starting bit from the divisor is from left to right, as you said, 2115/28 is 2, or starting from right-to-left is 8.
I would check this for accurate results.

Good luck :)

[Zaita]

satm2008:

Your way assumes that when you generate num, r and c none of them will exceed the limits of their data-types. Try dividing 2 numbers of about 10,000 digits long and see if it works.

[satm2008]

@Zaita

In the logic above, the num holds utmost 2 digits. (If you see that it takes leading one and current one utmost) hence r and r will give you a result of one digit numbers. Check it out.

Good luck :)

[Zaita]

Would it work if you were dividing:

122222222222222222222222222222222222222222222222222222222 by
112222222222222222222222222222222222222222222222222222222

For example?