PSA: don't use these functions unless you really, really need to

Revision en3, by -is-this-fft-, 2022-10-07 21:29:39

When solving problems in competitive programming, it is almost never a good idea to use the following inbuilt C++ functions. You will be hacked or fail a pretest or worse, a systest.

Why? Because they use floating-point numbers. They are designed to be used with a floating-point input and a floating-point output. The issue is that on a floating-point number, the result may not be exact. Worse, floating-point numbers may not be able to accurately encode the integer.

##### To calculate $\lfloor \frac{a}{b} \rfloor$ for positive integers $a$ and $b$:
• Don't use floor((double) a / (double) b) or similar.
• Do use a / b. It will round down.
• Warning: be careful with negative numbers. The answer depends on whether we should round down or towards 0.
##### To calculate $\lceil \frac{a}{b} \rceil$ for positive integers $a$ and $b$:
• Don't use ceil((double) a / (double) b) or similar.
• Do use (a + b - 1) / b.
• Warning: the same caveat goes for negative numbers as before.
##### To calculate $\lfloor \sqrt{a} \rfloor$ for a nonnegative integer $a$:
• Don't use sqrt(a) or similar.
• Do use binary search to calculate the square root.
Implementation
##### To calculate $a^b$ for nonnegative integers $a$ and $b$:
• Don't use pow(a, b) or similar.
• Do use the naive algorithm. If you really want to do this and $a^b$ fits in a long long, then it will take no more than 64 steps, unless $a = 0$ or $a = 1$, in which case you can just return $a$.
##### To calculate $\lfloor \log_2 (a) \rfloor$ for a positive integer $a$:
• Don't use log2(a) or similar.
• Do use __lg or an approach based on __builtin_clz or __builtin_clzll. The "clz" stands for "count leading zeroes" and it does exactly what it says — on the binary representation of the number. If you have access to C++20, there is also the bit_width library function.
• Warning: __builtin_clz(0) and __builtin_clzll(0) are undefined behavior. Also all these functions starting with __ are specific to GCC and you're technically not meant to use them, but it's fine in competitive programming.

#### Exceptions

The only major exception is if floating-point numbers are an inherent part of your solution. Most commonly, this happens in problems where the output is itself a floating-point number (especially geometry problems, sometimes probability). There are also some algorithms where you need to work with floating-point numbers even if the input and output are integer (FFT, possibly some LP).

But even in these cases, it's always a good idea to do as much as possible with integers and move to floats as late as possible.

##### I got WA with one compiler, accepted with another

Most likely it has to do with 64-bit versus 32-bit. Also the widths of the various floating-point types vary. It's possible that in some circumstances your solution is actually correct. However, rely on this only if you know what you're doing.

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 -is-this-fft- 2022-10-07 21:29:39 14
en2 -is-this-fft- 2022-10-07 21:12:39 154
en1 -is-this-fft- 2022-10-07 21:09:04 3225 Initial revision (published)