-3

There are 2 large integers, x and y such that z=x*y overflows. I would like to compute the first digit of x. Directly doing so isn't possible as the result overflows.

I was wondering if there was a certain technique for this.

Example: 10000000000000000000000000000000000 * 20579725928294522859735727575, here the first digit is 2 as I can see it directly, however, besides this special case, is there a way?

 #include <iostream>
using namespace std;

int main() {
long long int x,y,z;
cin>>x>>y;
z=x*y;
while(z>9)
{
    z/=10;
}
cout<<z;
    return 0;
 }

Above is a code that fails to work. For x=10000000000000000000000000000000000 y=20579725928294522859735727575

It gives output 5 as z overflows, and thus z=5240626126797720724 which is clearly wrong. I am looking to find a way out of this.

Cheers and hth. - Alf
  • 142,714
  • 15
  • 209
  • 331
Ramit Sawhney
  • 31
  • 1
  • 9
  • 4
    The first digit is 1. – Chiel Jun 07 '16 at 14:56
  • 1
    The first digit is 1 in binary unless the value is 0. – MikeCAT Jun 07 '16 at 14:57
  • 2
    I'm voting to close this question as off-topic. – Karoly Horvath Jun 07 '16 at 14:58
  • Can you **give a code example** where "10^10+8 * 10^8+14" overflows, please. – Cheers and hth. - Alf Jun 07 '16 at 14:59
  • I don't think so. (Famous last words, and a cue for someone to show how). A first approximation is convert both values to double, and multiply, and look at the first digit of the answer. This works with your example - the problem is that if your example had been (10^12+1) * (10^12-1) then the required result is "9", but any approximate method will give "1" – Martin Bonner supports Monica Jun 07 '16 at 15:00
  • Uh.. I think this has been misunderstood? I'm asking how do I calculate the first digit of any number that is obtained by the product of two large numbers such that the product overflows? Like an algorithm. If I have x>10^18 and y>10^18, then z=x*y, what is the first digit of x. This is the question. – Ramit Sawhney Jun 07 '16 at 15:00
  • 2
    Please revise your question with your clarification. Please add a concrete code example also. Voting to close as lacking example. – Cheers and hth. - Alf Jun 07 '16 at 15:01
  • @Cheersandhth.-Alf: Pretty sure '^' is to be read as the exponentation operator, not 'xor'. So 10,000,000,008 and 100,000,014. Typical implementations will store those as 32-bit int. Their product will overflow 32-bit int. – Martin Bonner supports Monica Jun 07 '16 at 15:02
  • 1
    There is of course the brute-force approach: use or write a bignum package, and use that. – Martin Bonner supports Monica Jun 07 '16 at 15:03
  • @MartinBonner: Yes, ^ is clearly exponentiation. The fact that your numbers do not appear even as computed entities in the question, attests to its lack of a reasonable example. – Cheers and hth. - Alf Jun 07 '16 at 15:03
  • I have edited it to be clearer. Also what is the brute force approach? – Ramit Sawhney Jun 07 '16 at 15:05
  • @RamitSawhney: The example is now more clear in that at least the numbers and mathematical operations are clear. However, when I try to compile this, Visual C++ 2015 says "constant too big". I.e. it's not valid C++ code. Please do post an example with **valid C++ code**. – Cheers and hth. - Alf Jun 07 '16 at 15:07
  • Please revise you code example to have the relevant values as literal constants, not input from the user. In your case most probably input fails. – Cheers and hth. - Alf Jun 07 '16 at 15:15
  • @Cheersandhth.-Alf I think it hardly matters. The point gets through, so it's okay. Thanks. – Ramit Sawhney Jun 07 '16 at 15:19
  • **−1** @RamitSawhney: You're the one asking for help. I was in the process of giving you an answer. But with such disrespect I won't. – Cheers and hth. - Alf Jun 07 '16 at 15:31
  • The brute force approach is to calculate every digit of the product using a bignum library (for example Boost Multiprecision). – Martin Bonner supports Monica Jun 07 '16 at 16:33
  • @RamitSawhney: What's the *real* problem you're trying to solve here? I can't help feeling that there's probably a better way. – Mark Dickinson Jun 07 '16 at 19:16

3 Answers3

4

You can do the multiplication with strings, like I learned in school many years ago

123456789987654321 * 998877665544332211

                    123456789987654321
                  * 998877665544332211
--------------------------------------
                    123456789987654321
                   123456789987654321
                  246913579975308642
                 246913579975308642
                370370369962962963
               370370369962962963
              493827159950617284
             493827159950617284
            617283949938271605
           617283949938271605
          740740739925925926
         740740739925925926
        864197529913580247
       864197529913580247
      987654319901234568
     987654319901234568
   1111111109888888889
+ 1111111109888888889
--------------------------------------
  123318230178465034444583004253633731
pmg
  • 106,608
  • 13
  • 126
  • 198
  • You could do something similar in base 10000. – Ian Abbott Jun 07 '16 at 15:32
  • Yep, finding all the digits when only the first is required is a bit of overkill. Filling the parcels from the bottom left and taking into account the possible error so as to calculate just enough digits is left as an exercise to the OP. – pmg Jun 07 '16 at 15:37
  • Ive tried exactly the same.But this implementation requires realloc... which might fail to assign memory in middle of process.. How do you effectively handle it? – Cherubim Jun 07 '16 at 15:41
  • If you need so much memory that `realloc()` might fail, maybe use slow disk files to keep temporary results. – pmg Jun 07 '16 at 15:43
1

In general; the most significant digit of the result depends on all the other digits, so you can't determine the most significant digit without determining all the other digits too.

For example, consider 3333334 * 3, where the carry would ripple all the way from the least significant digit all the way to the most significant digit.

Note that this is really:

     4 * 3 * 1
   + 3 * 3 * 10
   + 3 * 3 * 100
   + 3 * 3 * 1000
   + 3 * 3 * 10000
   + 3 * 3 * 100000
   + 3 * 3 * 1000000

..where the problem is that each addition can cause carries.

For multiple digits it gets worse. For example, 3333334 * 31 becomes:

   + 4 * 1 * 1
   + 3 * 1 * 10
   + 3 * 1 * 100
   + 3 * 1 * 1000
   + 3 * 1 * 10000
   + 3 * 1 * 100000
   + 3 * 1 * 1000000
   + 4 * 3 * 10
   + 3 * 3 * 100
   + 3 * 3 * 1000
   + 3 * 3 * 10000
   + 3 * 3 * 100000
   + 3 * 3 * 1000000
   + 3 * 3 * 10000000
Brendan
  • 35,656
  • 2
  • 39
  • 66
  • So is there a way to do this? Imagine I have 10^5 such multiplications, where numbers can be as big as 10^9 – Ramit Sawhney Jun 07 '16 at 15:18
  • @RamitSawhney: if the two numbers you're multiplying are bounded by `10^9`, then a C++ `long long` is big enough to hold the result of the multiplication. Or do you mean that you're multiplying 100 thousand numbers together into one gigantic product? – Mark Dickinson Jun 07 '16 at 19:15
-1

you can use Boost's Multiprecision Library to create big enough integers that would not overflow. But as to figuring out what the first digit is, you can turn your integer into string and then turn the first character of the string into integer. Having said that I fail to see why you would need such thing. If you are working with such big numbers that computation on them causes overflow, you should use something other than integer (Like BCD or boost) instead of regular int.

Sam

Sam
  • 2,473
  • 3
  • 18
  • 29