This guy - 4 months ago 31

C++ Question

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.

Answer

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).