$\left\lfloor \sqrt{x} \right\rfloor$ (tools/floor_sqrt.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-07-02 14:04:07+09:00
• Include: #include "tools/floor_sqrt.hpp"

template <typename T>
T floor_sqrt(T x);

It returns $\left\lfloor \sqrt{x} \right\rfloor$.

Constraints

• $x \geq 0$

Time Complexity

• $O(\log x)$

License

• CC0

Author

• anqooqie

Required by

• $\left\lfloor x^\frac{1}{k} \right\rfloor$ (tools/floor_kth_root.hpp)
• Mo's algorithm (tools/mo.hpp)
• Segmented sieve (tools/segmented_sieve.hpp)

Verified with

• tests/floor_kth_root.test.cpp
• tests/floor_sqrt.test.cpp
• tests/mo.test.cpp
• tests/segmented_sieve.test.cpp

Code

#ifndef TOOLS_FLOOR_SQRT_HPP
#define TOOLS_FLOOR_SQRT_HPP

#include <cassert>

namespace tools {

  template <typename T>
  T floor_sqrt(const T n) {
    assert(n >= 0);

    T ok = 0;
    T ng;
    for (ng = 1; ng <= n / ng; ng *= 2);

    while (ng - ok > 1) {
      const T mid = ok + (ng - ok) / 2;
      if (mid <= n / mid) {
        ok = mid;
      } else {
        ng = mid;
      }
    }

    return ok;
  }
}

#endif

#line 1 "tools/floor_sqrt.hpp"



#include <cassert>

namespace tools {

  template <typename T>
  T floor_sqrt(const T n) {
    assert(n >= 0);

    T ok = 0;
    T ng;
    for (ng = 1; ng <= n / ng; ng *= 2);

    while (ng - ok > 1) {
      const T mid = ok + (ng - ok) / 2;
      if (mid <= n / mid) {
        ok = mid;
      } else {
        ng = mid;
      }
    }

    return ok;
  }
}

Back to top page