Integer Square Roots

Today's post is short; it shows how to do integer square roots.

This is an old algorithm, once popular in assembly language programs on small processors. The fact that it uses only integers, addition, subtraction, and less-than branching, mean that its hardware and software requirements are at rock bottom. With enough patience and wire, you could probably get it running on a breadboard full of discrete ICs.

With modern floating-point hardware, this algorithm is rarely used, but it can still be handy from time-to-time. (For example, when trying solve the Project Euler problems without calling on external libraries, lol.)

It makes use of the fact that any perfect square can be expressed as the sum of consecutive odd integers.* Below is the F# code and a test; computing the big-O time is left as an exercise to the reader.

(As always, this code is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

// Minimalist square root finder.

let sqrt =

  let rec f i c n =

    match n<i with

    | false -> f (i+2) (c+1) (n-i) 

    | true -> c

  f 1 0

// Test.

let x = 

  {0..100} 

  |> Seq.map (fun i->i,sqrt(i)) 

  |> Seq.toList 

printfn "Your breakpoint here."

-Neil

*On the outside chance that the reason for this is not immediately obvious, the diagram below should provide a hint: