Как суммировать большие целые числа, которые не вписываются в unsigned long long? C++

Question

Я создал программу, которая суммирует все возможные отдельные подстроки данных. Например: 1 1 2 2 должен вернуть 30, потому что,

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

Суммы до 30, теперь проблема не создания такой программы, проблема, когда большие (10^15) числа приходят когда их может быть 10-5. Теперь мой вопрос: как я могу справиться с такими цифрами? Я могу использовать только стандартную библиотеку, поэтому для меня нет GMP, и я тоже вынужден работать на GCC 4.4.4, что делает его еще хуже.

Answer 1

Для всех, кто интересуется ответом, я понял это, переместив количество переполнений, чтобы отделить беззнаковый длинный длинный 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 
    } 
} 

Наверное, действительно неэффективно, но это достаточно хорошо для моих целей. Спасибо за вашу помощь!

Answer 2

Я думаю, что было бы довольно легко сделать голые кости (только то, что вам нужно) реализацию UINT_128. (ваш максимальный ответ действительно вписывается в uint_96)

Предполагая, что я знаю, как вы собираетесь внедрять программу, все, что вам нужно, это конструктор, который принимает uint64_t; оператор добавления; оператор умножения; и, возможно, дисплей.

Я бы сохранил его внутренне как 4 uint32_t (слова), и операции могут быть реализованы, просто работая над словами так же, как добавление или длительное умножение выполняется для десятичных знаков вручную. Умножение может быть упрощено, потому что я считаю, что ваши факторы никогда не превысят uint64_t, чтобы вы могли воспользоваться этим.

Если вам нужно отобразить что-то, отличное от двоичного или шестнадцатеричного, вам, вероятно, потребуется также реализовать разделение (или если вы действительно ленивы, вы можете уйти с помощью двоичного поиска по методу цифр по цифре и проверить, используя только умножение, чтобы получить десятичное представление).