-2

I've created a program that sums up all possible individual sub-strings of given data. For example: 1 1 2 2 should return 30 because,

1
1 + 1
1 + 1 + 2
1 + 1 + 2 + 2
1
1 + 2
1 + 2 + 2
2
2 + 2
2

Sums up to 30, now the problem isn't creating such a program, the issue is when the big (10^15) numbers come in when there can be as many as 10^5 of them. Now my question is: How do I deal with such numbers? I can only use standard library, so no GMP for me unfortunately and I'm also forced to run on GCC 4.4.4 which makes it even worse.

This guy
  • 1
  • 2
  • 1
    You need to analyze at least roughly **how big** would your result be. For example, if it's on the order of a googool, then so called "big integers" won't help. – Cheers and hth. - Alf Nov 30 '16 at 19:39
  • I recommend using GMP since it's not part of the standard C++ library. – Thomas Matthews Nov 30 '16 at 20:29
  • Solve the problem "I can only use the standard library" rather than solving the problem "I only have 64-bit integers available". –  Nov 30 '16 at 21:50

2 Answers2

0

I think it would be pretty easy to do a bare bone (only what you need) implementation of a UINT_128. (your maximum answer would actually fit in a uint_96)

Assuming I know the way you are going to implement the program, all you need is constructor that take a uint64_t; addition operator; multiplication operator; and possibly a display.

I would store it internally as 4 uint32_t (words) and the operations could be implemented by just operating on the words the same way addition or long multiplication is done for decimals by hand. Multiplication could be simplified because I believe your factors would never exceed a uint64_t so you could take advantage of that.

If you need to display something other than binary or hex, you probably need to implement division also (or if you are really lazy you could get away with a digit by digit binary search style guess and check using only multiplication to get the decimal representation).

Tony Mulieri
  • 1
0

For anyone interested in answer I've figured it out just by moving number of overflows to separate unsigned long long int.

for(int i = 1; i <= n; i++){                        
        SUM += addends[i - 1] * (i * (n - i + 1));

    if(SUM > 10000000000000000000){     // If close to overflow of unsigned long long int
        SUM -= 10000000000000000000;    // Remove 10^17
        counter ++;                     // And boost counter, to make recreating true value possible
    }
}

Probably really ineffective, but it's good enough for my purposes. Thank you all for your help!

This guy
  • 1
  • 2