Task — Integer square root

You are given a positive integer $N. Write a script to calculate the integer square root of the given number. Please avoid using built-in functions. Find out more about it here.

Examples

Input: $N = 10
Output: 3

Input: $N = 27
Output: 5

Input: $N = 85
Output: 9

Input: $N = 101
Output: 10

Analysis

The obvious answer would be int(sqrt($N)) were we not banned from using built-in functions.

So my solution does a binary chop. I start with the range 1 .. $N and find the midpoint, rounded to an integer, $try.

If $try ** 2 is greater than $N then I modify my range to be 1 .. $try, or else modify it to be $try .. $N, and repeat that process until the lower limit is just 1 less than the upper, at which point the lower limit is the answer.

This completes in milliseconds even for 10-digit $N.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2021-10-05
# PWC 133 task 1

use v5.20;
use strict;
use warnings;

my ($n, $low, $high, $odd, $try, @tests);

@tests = (123, 3000, 44444, 556677, 87654321, 909090909);

for $n (@tests) {

    $low = 1;    # answer can't be less than this
    $high = $n;  # or more than this

    while (1) {
        
        # get a trial answer which is the average of $low and $high (rounded up)
        $odd = ($low + $high) & 1 ? 1 : 0;   # because we aren't allowed to use int()
        $try = ($low + $high + $odd) / 2;
        
        # if the trial's square is larger than n, set the new $high to the trial value
        if ($try ** 2 > $n) {
            $high = $try;
            
        # or if it is less than or equal, set the new $low to the trial value
        } else {
            $low = $try;
        }
        
        # and finish when $low is just 1 less than $high
        last if $high == $low + 1;
    }

    say qq[\nInput:  \$N = $n];
    say qq[Output: $low];
    printf(qq[   %s ** 2 = %d, %s ** 2 = %d\n], $low, $low ** 2, $low + 1, ($low + 1) ** 2);
}

Output

Input:  $N = 123
Output: 11
   11 ** 2 = 121, 12 ** 2 = 144

Input:  $N = 3000
Output: 54
   54 ** 2 = 2916, 55 ** 2 = 3025

Input:  $N = 44444
Output: 210
   210 ** 2 = 44100, 211 ** 2 = 44521

Input:  $N = 556677
Output: 746
   746 ** 2 = 556516, 747 ** 2 = 558009

Input:  $N = 87654321
Output: 9362
   9362 ** 2 = 87647044, 9363 ** 2 = 87665769

Input:  $N = 909090909
Output: 30151
   30151 ** 2 = 909082801, 30152 ** 2 = 909143104