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

Правка en1, от -is-this-fft-, 2022-10-07 21:09:04

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.

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)