Trait malachite_base::num::arithmetic::traits::CheckedSqrt

pub trait CheckedSqrt {
    type Output;

    // Required method
    fn checked_sqrt(self) -> Option<Self::Output>;
}

Finds the square root of a number, returning None if it is not a perfect square.

Required Associated Types

type Output

Required Methods

fn checked_sqrt(self) -> Option<Self::Output>

Implementations on Foreign Types

impl CheckedSqrt for i8

fn checked_sqrt(self) -> Option<i8>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is negative.

Examples

See here.

type Output = i8

impl CheckedSqrt for i16

fn checked_sqrt(self) -> Option<i16>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is negative.

Examples

See here.

type Output = i16

impl CheckedSqrt for i32

fn checked_sqrt(self) -> Option<i32>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is negative.

Examples

See here.

type Output = i32

impl CheckedSqrt for i64

fn checked_sqrt(self) -> Option<i64>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is negative.

Examples

See here.

type Output = i64

impl CheckedSqrt for i128

fn checked_sqrt(self) -> Option<i128>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is negative.

Examples

See here.

type Output = i128

impl CheckedSqrt for isize

fn checked_sqrt(self) -> Option<isize>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is negative.

Examples

See here.

type Output = isize

impl CheckedSqrt for u8

fn checked_sqrt(self) -> Option<u8>

Returns the the square root of a u8, or None if the u8 is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

The u8 implementation uses a lookup table.

type Output = u8

impl CheckedSqrt for u16

fn checked_sqrt(self) -> Option<u16>

Returns the the square root of a u16, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

The u16 implementation calls the implementation for u32s.

type Output = u16

impl CheckedSqrt for u32

fn checked_sqrt(self) -> Option<u32>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

For u32 and u64, the square root is computed using Newton’s method.

type Output = u32

impl CheckedSqrt for u64

fn checked_sqrt(self) -> Option<u64>

Returns the the square root of an integer, or None if the integer is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

For u32 and u64, the square root is computed using Newton’s method.

type Output = u64

impl CheckedSqrt for u128

fn checked_sqrt(self) -> Option<u128>

Returns the the square root of a u128, or None if the u128 is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

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 u128s. To overcome this, large u128s 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}$.

type Output = u128

impl CheckedSqrt for usize

fn checked_sqrt(self) -> Option<usize>

Returns the the square root of a usize, or None if the usize is not a perfect square.

$$ f(x) = \begin{cases} \operatorname{Some}(sqrt{x}) & \text{if} \quad \sqrt{x} \in \Z, \\ \operatorname{None} & \textrm{otherwise}. \end{cases} $$

Worst-case complexity

Constant time and additional memory.

Examples

See here.

Notes

The usize implementation calls the u32 or u64 implementations.

type Output = usize

Implementors