Root and Smith
Weekly challenge 133 — 4 October 2021
Week 133: 4 Oct 2021
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.
Input: $N = 10 Output: 3 Input: $N = 27 Output: 5 Input: $N = 85 Output: 9 Input: $N = 101 Output: 10
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
.
#!/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); }
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
Any content of this website which has been created by Peter Campbell Smith is in the public domain