OVERHEAD

Integer square root in POSIX shell

Scripting

POSIX shell script which uses the binary search method to compute the integer square root of the first argument.

#!/bin/sh

input="$1"
root="0"
iterate="$(( "$input" + 1 ))"
while [ "$root" -ne "$(( "$iterate" - 1 ))" ]; do
        step="$(( ("$root" + "$iterate") / 2 ))"
        if [ "$(( "$step" * "$step" ))" -le "$input" ]; then
			root="$step"
                else
			iterate="$step"
        fi
done

printf "Integer square root: %s\n" "$root"

See the Integer square root Wikipedia page for more information.

Some notes on this script:

  1. I have no idea why this method works, all I know is that it’s fast.
  2. Because it’s POSIX shell, you can’t use floating point numbers, meaning both the input and output of this script are integers.

I’m disappointed that I wasn’t able to find an “arithmetic-only non-iterative integer square root” formula which only needs to be executed once. I feel like it’s possible, but, this is good enough given its speed.