# Trait malachite_base::num::arithmetic::traits::FloorSqrt

source · ```
pub trait FloorSqrt {
type Output;
// Required method
fn floor_sqrt(self) -> Self::Output;
}
```

## Expand description

Finds the floor of the square root of a number.

## Required Associated Types§

## Required Methods§

#### fn floor_sqrt(self) -> Self::Output

## Implementations on Foreign Types§

source§### impl FloorSqrt for i8

### impl FloorSqrt for i8

source§#### fn floor_sqrt(self) -> Self

#### fn floor_sqrt(self) -> Self

Returns the floor of the square root of an integer.

$f(x) = \lfloor\sqrt{x}\rfloor$.

##### Worst-case complexity

Constant time and additional memory.

##### Panics

Panics if `self`

is negative.

##### Examples

See here.

#### type Output = i8

source§### impl FloorSqrt for i16

### impl FloorSqrt for i16

source§#### fn floor_sqrt(self) -> Self

#### fn floor_sqrt(self) -> Self

Returns the floor of the square root of an integer.

$f(x) = \lfloor\sqrt{x}\rfloor$.

##### Worst-case complexity

Constant time and additional memory.

##### Panics

Panics if `self`

is negative.

##### Examples

See here.

#### type Output = i16

source§### impl FloorSqrt for i32

### impl FloorSqrt for i32

source§#### fn floor_sqrt(self) -> Self

#### fn floor_sqrt(self) -> Self

Returns the floor of the square root of an integer.

$f(x) = \lfloor\sqrt{x}\rfloor$.

##### Worst-case complexity

Constant time and additional memory.

##### Panics

Panics if `self`

is negative.

##### Examples

See here.

#### type Output = i32

source§### impl FloorSqrt for i64

### impl FloorSqrt for i64

source§#### fn floor_sqrt(self) -> Self

#### fn floor_sqrt(self) -> Self

Returns the floor of the square root of an integer.

$f(x) = \lfloor\sqrt{x}\rfloor$.

##### Worst-case complexity

Constant time and additional memory.

##### Panics

Panics if `self`

is negative.

##### Examples

See here.

#### type Output = i64

source§### impl FloorSqrt for i128

### impl FloorSqrt for i128

source§#### fn floor_sqrt(self) -> Self

#### fn floor_sqrt(self) -> Self

Returns the floor of the square root of an integer.

$f(x) = \lfloor\sqrt{x}\rfloor$.

##### Worst-case complexity

Constant time and additional memory.

##### Panics

Panics if `self`

is negative.

##### Examples

See here.

#### type Output = i128

source§### impl FloorSqrt for isize

### impl FloorSqrt for isize

source§#### fn floor_sqrt(self) -> Self

#### fn floor_sqrt(self) -> Self

Returns the floor of the square root of an integer.

$f(x) = \lfloor\sqrt{x}\rfloor$.

##### Worst-case complexity

Constant time and additional memory.

##### Panics

Panics if `self`

is negative.

##### Examples

See here.

#### type Output = isize

source§### impl FloorSqrt for u128

### impl FloorSqrt for u128

source§#### fn floor_sqrt(self) -> u128

#### fn floor_sqrt(self) -> u128

Returns the floor of the square root of a `u128`

.

$f(x) = \lfloor\sqrt{x}\rfloor$.

##### Worst-case complexity

$T(n) = O(n)$

$M(n) = O(1)$

where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`

.

##### Examples

See here.

##### Notes

For `u128`

, using a floating-point approximation and refining the result works, but the
number of necessary adjustments becomes large for large `u128`

s. To overcome this, large
`u128`

s switch to a binary search algorithm. To get decent starting bounds, the following
fact is used:

If $x$ is nonzero and has $b$ significant bits, then

$2^{b-1} \leq x \leq 2^b-1$,

$2^{b-1} \leq x \leq 2^b$,

$2^{2\lfloor (b-1)/2 \rfloor} \leq x \leq 2^{2\lceil b/2 \rceil}$,

$2^{2(\lceil b/2 \rceil-1)} \leq x \leq 2^{2\lceil b/2 \rceil}$,

$\lfloor\sqrt{2^{2(\lceil b/2 \rceil-1)}}\rfloor \leq \lfloor\sqrt{x}\rfloor \leq \lfloor\sqrt{2^{2\lceil b/2 \rceil}}\rfloor$, since $x \mapsto \lfloor\sqrt{x}\rfloor$ is weakly increasing,

$2^{\lceil b/2 \rceil-1} \leq \lfloor\sqrt{x}\rfloor \leq 2^{\lceil b/2 \rceil}$.

For example, since $10^9$ has 30 significant bits, we know that $2^{14} \leq \lfloor\sqrt{10^9}\rfloor \leq 2^{15}$.