Python's math.isqrt in TypeScript

How to use

Install via yarn add locutus and import: import { isqrt } from 'locutus/python/math/isqrt'.

Or with CommonJS: const { isqrt } = require('locutus/python/math/isqrt')

Use a bundler that supports tree-shaking so you only ship the functions you actually use. Vite, webpack, Rollup, and Parcel all handle this. For server-side use this is less of a concern.

Examples

These examples are extracted from test cases that automatically verify our functions against their native counterparts.

#	code	expected result
1	isqrt(15)	3
2	isqrt(16)	4
3	isqrt(0)	0

Notes

• Returns the integer square root, rounding down to the nearest whole number.

Here's what our current TypeScript equivalent to Python's math.isqrt looks like.

TSTypeScript JSJavaScript TSStandalone TS JSStandalone JS

Copy code

const MAX_SAFE_ROOT = BigInt(Number.MAX_SAFE_INTEGER)
const FIRST_UNSAFE_ROOT_SQUARED = (MAX_SAFE_ROOT + 1n) * (MAX_SAFE_ROOT + 1n)

export function isqrt(n: number | string): number {
  //      discuss at: https://locutus.io/python/isqrt/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //          note 1: Returns the integer square root, rounding down to the nearest whole number.
  //       example 1: isqrt(15)
  //       returns 1: 3
  //       example 2: isqrt(16)
  //       returns 2: 4
  //       example 3: isqrt(0)
  //       returns 3: 0

  if (typeof n === 'string' && /^[-+]?\d+$/.test(n.trim())) {
    const parsed = BigInt(n)
    if (parsed < 0n) {
      throw new Error('isqrt() only accepts non-negative integers')
    }

    if (parsed >= FIRST_UNSAFE_ROOT_SQUARED) {
      throw new RangeError('isqrt() only supports roots within JS safe integer precision')
    }

    const root = bigintSqrt(parsed)
    if (root > MAX_SAFE_ROOT) {
      throw new RangeError('isqrt() only supports roots within JS safe integer precision')
    }

    return Number(root)
  }

  const value = Number(n)

  if (!Number.isFinite(value) || !Number.isSafeInteger(value) || value < 0) {
    throw new Error('isqrt() only accepts non-negative integers')
  }

  return Math.floor(Math.sqrt(value))
}

function bigintSqrt(value: bigint): bigint {
  if (value < 2n) {
    return value
  }

  let x0 = value
  let x1 = (x0 + 1n) >> 1n

  while (x1 < x0) {
    x0 = x1
    x1 = (x1 + value / x1) >> 1n
  }

  return x0
}

const MAX_SAFE_ROOT = BigInt(Number.MAX_SAFE_INTEGER)
const FIRST_UNSAFE_ROOT_SQUARED = (MAX_SAFE_ROOT + 1n) * (MAX_SAFE_ROOT + 1n)

export function isqrt(n) {
  //      discuss at: https://locutus.io/python/isqrt/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //          note 1: Returns the integer square root, rounding down to the nearest whole number.
  //       example 1: isqrt(15)
  //       returns 1: 3
  //       example 2: isqrt(16)
  //       returns 2: 4
  //       example 3: isqrt(0)
  //       returns 3: 0

  if (typeof n === 'string' && /^[-+]?\d+$/.test(n.trim())) {
    const parsed = BigInt(n)
    if (parsed < 0n) {
      throw new Error('isqrt() only accepts non-negative integers')
    }

    if (parsed >= FIRST_UNSAFE_ROOT_SQUARED) {
      throw new RangeError('isqrt() only supports roots within JS safe integer precision')
    }

    const root = bigintSqrt(parsed)
    if (root > MAX_SAFE_ROOT) {
      throw new RangeError('isqrt() only supports roots within JS safe integer precision')
    }

    return Number(root)
  }

  const value = Number(n)

  if (!Number.isFinite(value) || !Number.isSafeInteger(value) || value < 0) {
    throw new Error('isqrt() only accepts non-negative integers')
  }

  return Math.floor(Math.sqrt(value))
}

function bigintSqrt(value) {
  if (value < 2n) {
    return value
  }

  let x0 = value
  let x1 = (x0 + 1n) >> 1n

  while (x1 < x0) {
    x0 = x1
    x1 = (x1 + value / x1) >> 1n
  }

  return x0
}

Improve this function

Locutus is a community effort following The McDonald's Theory: we ship first iterations, hoping others will improve them. If you see something that could be better, we'd love your contribution.

View on GitHub · Edit on GitHub · View Raw

---

Help us add more

Got a rainy Sunday afternoon and a taste for a porting puzzle?

• Get inspiration from the Python 3 standard library string page.
• Click "New file" in the appropriate folder on GitHub. This will fork the project to your account, directly add the file to it, and send a Pull Request to us.

We will then review it. If it's useful to the project and in line with our contributing guidelines your work will become part of Locutus and you'll be automatically credited in the authors section accordingly.

« More Python math functions

Star