Square Root
Find the square root of a perfect square of a positive integer without a built-in square root function.
Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.
// FILE: square_root.nomi
//# The exercise asks for the root without a built-in square root, so
//# `square_root` finds it with Newton's method on integers, not with
//# `Int.sqrt`.
/// The square root of `radicand`, a perfect square, and 0 for 0.
pub fn square_root(radicand: Int) -> Int
if radicand <= 0 then return 0
newton(radicand, radicand)
end
/// Newton's step for the root of `radicand` from `guess`, an integer at or
/// above the root. Each step lowers the guess, and the first step that
/// would not lower it leaves the root.
fn newton(radicand: Int, guess: PositiveInt) -> Int
next = (guess + radicand / guess) / 2
if next >= guess then
guess
else
// A step from above the root lands at or above it, so at least 1.
newton(radicand, PositiveInt.try_from(next)!)
end
end
// FILE: square_root_test.nomi
import square_root
test "square root"
[
("root of 1", 1, 1),
("root of 4", 4, 2),
("root of 25", 25, 5),
("root of 81", 81, 9),
("root of 196", 196, 14),
("root of 65025", 65025, 255),
]
|> subtests (description, radicand, expected), description
assert square_root.square_root(radicand) == expected
end
endok square root (6 cases)
test result: ok. 6 passed, 0 failed
How it’s written
Section titled “How it’s written”- std has
Int.sqrt, which is the answer the exercise forbids, sosquare_rootuses Newton’s method on integers instead. The file says so in its//#comment. newtonstarts from the radicand itself, which is at or above the root for any positive integer, and steps to(guess + radicand / guess) / 2. Integer division rounds each step down, so the guesses fall to the root and the first step that does not fall stops the walk. There is no tolerance to choose, as there would be with floats.- The radicand is promised to be a perfect square, so there is no error case and no
Result.square_rootanswers 0 for 0 and below, andnewtontakes its guess as aPositiveInt, the divisor/needs. A step from above the root lands at or above it, so the next guess is at least 1, whichPositiveInt.try_from(next)!states (style §29). - The six canonical cases are one
subteststable named by the description column.