From 61795232f4bab46f4f9fccc542ef7ec1ebcac02f Mon Sep 17 00:00:00 2001 From: Yawning Angel Date: Fri, 25 Oct 2024 11:46:47 +0900 Subject: src/big_int.cpp: Use square-multiply for exponentiation For utterly unrealistic constant sizes, this still crashes on my system, but it crashes fast due to the OOM killer, and people using rediculously large exponents get what they deserve. --- src/big_int.cpp | 17 ++++++++++++++--- 1 file changed, 14 insertions(+), 3 deletions(-) (limited to 'src/big_int.cpp') diff --git a/src/big_int.cpp b/src/big_int.cpp index 83235483c..8e476f090 100644 --- a/src/big_int.cpp +++ b/src/big_int.cpp @@ -62,6 +62,7 @@ gb_internal void big_int_shl (BigInt *dst, BigInt const *x, BigInt const *y); gb_internal void big_int_shr (BigInt *dst, BigInt const *x, BigInt const *y); gb_internal void big_int_mul (BigInt *dst, BigInt const *x, BigInt const *y); gb_internal void big_int_mul_u64(BigInt *dst, BigInt const *x, u64 y); +gb_internal void big_int_exp_u64(BigInt *dst, BigInt const *x, u64 y, bool *success); gb_internal void big_int_quo_rem(BigInt const *x, BigInt const *y, BigInt *q, BigInt *r); gb_internal void big_int_quo (BigInt *z, BigInt const *x, BigInt const *y); @@ -250,9 +251,7 @@ gb_internal void big_int_from_string(BigInt *dst, String const &s, bool *success exp *= 10; exp += v; } - for (u64 x = 0; x < exp; x++) { - big_int_mul_eq(dst, &b); - } + big_int_exp_u64(dst, &b, exp, success); } if (is_negative) { @@ -328,6 +327,18 @@ gb_internal void big_int_mul_u64(BigInt *dst, BigInt const *x, u64 y) { big_int_dealloc(&d); } +gb_internal void big_int_exp_u64(BigInt *dst, BigInt const *x, u64 y, bool *success) { + if (y > INT_MAX) { + *success = false; + return; + } + + // Note: The cutoff for square-multiply being faster than the naive + // for loop is when exp > 4, but it probably isn't worth adding + // a fast path. + mp_err err = mp_expt_n(x, int(y), dst); + *success = err == MP_OKAY; +} gb_internal void big_int_mul(BigInt *dst, BigInt const *x, BigInt const *y) { mp_mul(x, y, dst); -- cgit v1.2.3