sqrt is fine just check your answer once after doing it

The code given in spoiler is dirty take a look at it -is-this-fft-

lol in hindsight me failing pretest 4 on B 3 times and switching from sqrt() to binary search helped me since I didn't fail sys test 11 xd

I'm glad that my contest helped raise competitors awareness to this matters. Many people are still using built-ins without caution or understanding the imprecision it could bring. Especially floating-point related!

Very usefull, now

Thanks for your benefit blog .can you make another blog about precision errors but in python since this blog about c++ ?
Thanks in advance .

Very helpful blog for the newcomers, thank you! I will definitely link this to my students.

Some thoughts:

• in the section about $$$a^b$$$, maybe add a special case for $$$-1$$$? I know that you've written about non-negative integers, but with this additional case, it works for negative $$$a$$$ as well.

• maybe add a section about comparing fractions? Like, if you want to check that $$$\frac{a}{b} = \frac{c}{d}$$$, you shouldn't divide in floating-point numbers; instead either check $$$a*d == b*c$$$ (if it fits in the integer types you use) or normalize the fractions.

• isn't it possible to estimate $$$sqrt(n)$$$ almost perfectly with the standard function and then search for the answer in something like $$$[sqrt(n)-5, sqrt(n)+5]$$$? I know it's kinda advanced, but so is binary search.

Reading this makes me feel very thankful that I AC'd Dytechlab's contest question B using normal std::sqrt()

sqrt(x) is fine, just do something like this:

int64_t x;
cin >> x;
int64_t r = sqrtl(x) + 1;
while (r * r > x) r--;

sqrtl() use long double instead of double, and might not be necessary.

+1 should be enough, but if you are paranoid then +small would be better.

Generally this should be better than binary search.

If you for some reason what to avoid having any floating point at all, then try to implement the search as $$$r_{i+1} = (r_{i} + x/r_{i}) / 2$$$ instead, it might be faster than just binary search.

You can compute $$$\lfloor \sqrt a \rfloor$$$ faster and easier than with binary search:

long long x = sqrt(a) + 2;
while (x * x > a) x--;

For the round-up, I use this.

ans=ceil(a*1.00/b);

I never got an error in this (till now), but is there a possibility that this way can fail?

Thanks!

Why am I being downvoted? (Sorry if I commented something wrong)

for $$$log_2$$$ this way may be more useful:
f[0]=0;for(int i=1;i<=N;i++) f[i]=f[i>>1]+1;

However,my friends told me "__builtin_clz()" is as fast as the integer operator "+".

THanks for the blog!

-is-this-fft-, could you please fix (again?) the comment in the attached code? For me, it is shown as // works for at least up to (2**31 — 1)**2

Also, one might want to use binary exponentiation instead of pow. The fun fact is that in this case even $$$0$$$ or $$$1$$$ to some enormous power are calculated as fast as $$$2^{62}$$$ is suggested to be calculated. So it is not obligatory to if them, and if it's done, the code is even faster. Probably this part is "advanced" too...

You can also use the Babylonian method to find the square root. It converges quadratically and is very fast.

int isqrt(int x)
{
    // Integer square root of x.
    // 
    // Use the Babylonian method, adapted to integers. The next estimate will
    // be less than the current one, as long as the latter is greater than √x.
    // In the end, either the estimates will match, or they will trade places.
    // At this point, return the non-greater estimate.
    // 
    // We round the first estimate up to avoid it becoming zero.
    int a = x, b = (x + 1) / 2;
    while (a > b)
    {
        a = b;
        b = (b + x / b) / 2;
    }
    return a;
}

With a good initial guess the method works even faster.

Meanwhile, people writing ll c = a * b; for $$$a, b \le 10^9$$$.

Several more points about make int, not float

Cross product

Cross product calculates $$$(-1)^n \cdot 2S$$$. The sign depends on rotation of points in triangle. It can be used in tasks related to convex hull. Don't calculate angles.

int c_p(int x1, int y1, int x2, int y2, int x3, int y3) {
    return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
}

Task

Square

If the points of triangle are integers, then the square of it is $$$\frac{int}{2}$$$. We can operate on double square, which are ints. We can get it using vector product, which returns $$$(-1)^n \cdot 2S$$$.

For example, we can safely check if point $$$(x4, y4)$$$ is inside of triangle (including boundaries).

if (abs(c_p(x1, y1, x2, y2, x3, y3) == abs(c_p(x4, y4, x1, y1, x2, y2) + abs(c_p(x4, y4, x1, y1, x3, y3) + abs(c_p(x4, y4, x2, y2, x3, y3)) ...

Task

Dot product

Dot product is needed more rarely. It can be used to check, if the angle is acute, right or obtuse. For example, it can be used to find distance from point to segment on plane. The are two cases: when perpendicular from point to segment's line lies on segment, or not. It can be checked with dot product.

int d_p(int x1, int y1, int x2, int y2, int x3, int y3) {
    return (x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1);
}

Task

Sort by polar angle

Assume, you need to sort point by polar angle relative to vector $$$(1, 0)$$$. You can do $$$a[i] = atan2(y[i], x[i]);$$$ (if you don't know, what is atan2(y, x), discover it, it helpful in reducing ifs). Instead we can (unfortunately, with ifs) sort points in one quadrant by their tan (which is monotone there). But compare not $$$\frac{y[i]}{x[i]} - \frac{y[j]}{x[j]}$$$, but $$$y[i] * x[j] - y[j] * x[i]$$$.

Task Task

Check, if overflow happened

Assume, in problem you have to multiply numbers $$$\le 10^{18}$$$, but you know for sure, that if at some moment the number is $$$\ge 10^{18}$$$, the answer is "NO". How can we check, if multiplication won't give overflow?

Assume, you have to check, if $$$x \cdot y \le C$$$. Instead, check if $$$x \le \frac{C}{y}$$$

Floating-point numbers can accurately represents $$$2^n$$$, so maybe long double is still useful for some problems that require $$$2^n$$$ of your output. It can represent $$$2^n$$$ for any integer $$$n<15000$$$ (in the circumstances where long double have 15 bits for Exponent).

Some people are suggesting sqrtl. Can someone write or refer to a convincing analysis to show that sqrtl is always correct?

C++20 also has https://en.cppreference.com/w/cpp/numeric/countr_zero and https://en.cppreference.com/w/cpp/numeric/countl_zero to replace __builtin_ctz and __builtin_clz. They return the correct answer (the number of bits of the corresponding datatype) when passed 0 as input, so there's no undefined behavior.

Don't use floor((double) a / (double) b) or similar.

For some years now, floating-point division has been faster on x86 than integer division. (On top of that, it is also vectorizable, but it’s faster even when unvectorized.)

And for int32, dividing through double is exact.

So for int32: do use (int) ((double) a / b) or similar; just make sure you pick the rounding you need from (int)/(int)(_+0.5)/floor/ceil. At least as long as you’re on x86, that is, but I strongly suspect Codeforces is.

For int16, divide through float for even more speed.

[1] [2] [3]

Can someone explain to me how pow(a, b) uses floating-point numbers?

Could you give an example of functions like ceil and floor calculating so far off that the cast rounds to the wrong mathematical integer?

So how can I hack the programs which use the functions above? thx

Can anyone tell me why the sqrt given above does not work in this case but inbuild cpp sqrt works?

Ac 208095241 TLE 208095176