maths.integer_square_root

Integer Square Root Algorithm – An efficient method to calculate the square root of a non-negative integer ‘num’ rounded down to the nearest integer. It uses a binary search approach to find the integer square root without using any built-in exponent functions or operators. * https://en.wikipedia.org/wiki/Integer_square_root * https://docs.python.org/3/library/math.html#math.isqrt Note:

  • This algorithm is designed for non-negative integers only.

  • The result is rounded down to the nearest integer.

  • The algorithm has a time complexity of O(log(x)).

  • Original algorithm idea based on binary search.

Functions

integer_square_root(→ int)

Returns the integer square root of a non-negative integer num.

Module Contents

maths.integer_square_root.integer_square_root(num: int) → int

Returns the integer square root of a non-negative integer num. Args:

num: A non-negative integer.

Returns:

The integer square root of num.

Raises:

ValueError: If num is not an integer or is negative.

>>> [integer_square_root(i) for i in range(18)]
[0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4]
>>> integer_square_root(625)
25
>>> integer_square_root(2_147_483_647)
46340
>>> from math import isqrt
>>> all(integer_square_root(i) == isqrt(i) for i in range(20))
True
>>> integer_square_root(-1)
Traceback (most recent call last):
    ...
ValueError: num must be non-negative integer
>>> integer_square_root(1.5)
Traceback (most recent call last):
    ...
ValueError: num must be non-negative integer
>>> integer_square_root("0")
Traceback (most recent call last):
    ...
ValueError: num must be non-negative integer