Факты в первую очередь, из проекта стандарта N4800 §7.1 / P4 [expr.pre] ( Emphasis Mine ):
Если во времяПри вычислении выражения результат не определяется математически или не находится в диапазоне представимых значений для его типа, поведение не определено. [Примечание: обработка деления на ноль, формирования остатка с использованием делителя нуля ивсе исключения с плавающей точкой различаются для разных машин и иногда настраиваются библиотечной функцией.- примечание к концу]
Также пункт §6.7.1 / p2 Основные типы [basic.fundamental] ( Акцент на шахте ):
Длякаждому из стандартных целочисленных типов со знаком существует соответствующий (но различный) стандартный целочисленный тип без знака: «unsigned char», «unsigned short int», «unsigned int», «unsigned long int» и «unsigned long long int»,Аналогично, для каждого из расширенных целочисленных типов со знаком существует соответствующий расширенный целочисленный тип без знака.Стандартные и расширенные целочисленные типы без знака вместе называются целочисленными типами без знака.Целочисленный тип без знака имеет тот же показатель диапазона N, что и соответствующий целочисленный тип со знаком. Диапазон представимых значений для типа без знака составляет от 0 до 2 ^ N - 1 (включительно);Арифметика для типа без знака выполняется по модулю 2 ^ N.[Примечание: Арифметика без знака не переполняется.Переполнение для подписанной арифметики приводит к неопределенному поведению (7.1).- конец примечания]
Также §5.13.2 / p2 Целочисленные литералы [lex.icon]
Тип целочисленного литерала является первым изсоответствующий список в Таблице 7, в котором может быть представлено его значение.
Также §7.4 Обычные арифметические преобразования [expr.arith.conv]
(1.5) - В противном случае интегральные преобразования (7.3.6) должны выполняться для обоих операндов 60 .Затем к повышенным операндам должны применяться следующие правила:
(1.5.1) - если оба операнда имеют одинаковый тип, дальнейшее преобразование не требуется.
(1.5.2) - В противном случае, если оба операнда имеют целочисленные типы со знаком или оба имеют целочисленные типы без знака, операнд с типом меньшего целого ранга преобразования должен быть преобразован в тип операнда с большим рангом.
(1.5.3) - В противном случае, если операнд с целочисленным типом без знака имеет ранг, больший или равный рангу типа другого операнда, операнд со знакомЦелочисленный тип должен быть преобразован в тип операнда с целым типом без знака.
(1.5.4) - В противном случае, если тип операнда со целым типом со знаком может представлять всезначения типа операнда с целым типом без знака, операнд с целым типом без знака должны быть преобразованы в тип операнда с целым числом со знаком type.
(1.5.5) - В противном случае оба операнда должны быть преобразованы в целочисленный тип без знака, соответствующий типу операнда с целым типом со знаком
Итак, вопрос: математически определены ли арифметические результаты в этой программе и находятся ли они в пределах представимых значений для ее типов.Более конкретно, находится ли выражение 1442695040888963407 + compute(t * 6364136223846793005) в диапазоне представимых значений для его типов?
Для этого тип целочисленных литералов 1442695040888963407 и 6364136223846793005 должен упасть до меньшего или равного ранга преобразования с std::uint64_t, чтобы результаты конвертировались в std::uint64_t.К сожалению, такой гарантии нет.
Таким образом, чтобы ваша программа избегала UB, я бы пометил целочисленные литералы LU.
bigint compute(bigint t)
{
if (t > 1) {
return 1442695040888963407LU + compute(t * 6364136223846793005LU);
} else {
return 1;
}
}
Теперь о том, почему вы получаете сегментациюошибка, из-за того, что вы переполняете свой стек.Хотя вышеупомянутая программа теоретически не имеет бесконечного количества рекурсий, которое является UB, количество рекурсий исчерпывает ресурсы вашей машины.