Facts first, from draft standard N4800 §7.1/P4 [expr.pre] (Emphasis Mine):
If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for
its type, the behavior is undefined. [Note: Treatment of division by
zero, forming a remainder using a zero divisor, and all floating-point
exceptions vary among machines, and is sometimes adjustable by a
library function. — end note]
Also the clause §6.7.1/p2 Fundamental types [basic.fundamental] (Emphasis Mine):
For each of the standard signed integer types, there exists a
corresponding (but different) standard unsigned integer type:
“unsigned char”, “unsigned short int”, “unsigned int”, “unsigned long
int”, and “unsigned long long int”. Likewise, for each of the extended
signed integer types, there exists a corresponding extended unsigned
integer type. The standard and extended unsigned integer types are
collectively called unsigned integer types. An unsigned integer type
has the same range exponent N as the corresponding signed integer
type. The range of representable values for the unsigned type is 0
to 2^N − 1 (inclusive); arithmetic for the unsigned type is performed
modulo 2^N . [Note: Unsigned arithmetic does not overflow. Overflow
for signed arithmetic yields undefined behavior (7.1). — end note]
Also §5.13.2/p2 Integer literals [lex.icon]
The type of an integer literal is the first of the corresponding list
in Table 7 in which its value can be represented.
Also §7.4 Usual arithmetic conversions [expr.arith.conv]
(1.5) — Otherwise, the integral promotions (7.3.6) shall be performed
on both operands60. Then the following rules shall be applied to the
promoted operands:
(1.5.1) — If both operands have the same type, no further conversion is needed.
(1.5.2) — Otherwise, if both operands have signed integer types or both have unsigned integer types, the operand with the type of lesser
integer conversion rank shall be converted to the type of the operand
with greater rank.
(1.5.3) — Otherwise, if the operand that has unsigned integer type has rank greater than or equal to the rank of the type of the other
operand, the operand with signed integer type shall be converted to
the type of the operand with unsigned integer type.
(1.5.4) — Otherwise, if the type of the operand with signed integer type can represent all of the values of the type of the operand with
unsigned integer type, the operand with unsigned integer type shall be
converted to the type of the operand with signed integer type.
(1.5.5) — Otherwise, both operands shall be converted to the unsigned integer type corresponding to the type of the operand with
signed integer type
So the question is: Are the arithmetic results in this program mathematically defined and within the range of representable values for its types. More specifically, is the expression 1442695040888963407 + compute(t * 6364136223846793005) within the range of representable values for its types?
For this to happen the type of integer literals 1442695040888963407 and 6364136223846793005 must fall to lesser or equal conversion rank with std::uint64_t so that the results convert to std::uint64_t. Unfortunatelly, there's no such guarantee.
Thus, for your program to avoid UB I would mark the integer literals with LU.
bigint compute(bigint t)
{
if (t > 1) {
return 1442695040888963407LU + compute(t * 6364136223846793005LU);
} else {
return 1;
}
}
Now, as to why you get segmentation fault, is due to the fact that you overflow your stack. Although, the above program theoretically doesn't have infinite number of recursions which is UB, the number of recursions exhausts your machine's resources.
