Given an integer n, suppose you want to compute ⌊√n⌋, the greatest integer less than or equal to the square root of n. One reason you may want to compute ⌊√n⌋ is to know when you can stop trial division when factoring n. Similarly, ⌊√n⌋ gives you a starting point for Fermat’s factorization algorithm.

With floating point arithmetic

The obvious approach to computing ⌊√n⌋ would be to compute the square root of n as a real number and then round the result down.

Suppose we go down that route. How would we compute √n as real number? The usual way is to use Newton’s square root method. First you make an initial guess at the square root of n, say a. Then repeatedly update your guess to be the average of your previous guess a and n/a:

a ← (a + n/a) /2.

This is an ancient algorithm, going back to at least 1000 BC in Babylon. We call it Newton’s method because it is a special case of Newton’s root-finding method, applied to f(x) = x² − a.

Newton’s square root algorithm is implemented in computer hardware to this day. In some sense, we still compute square roots the same way the ancient Babylonians did.

Without floating point arithmetic

Our original problem was to find an integer, the largest integer no greater than the integer n. Can we take advantage of the fact that we’re working with integers?

A general approach to solving problems over the integers is to solve the same problem over the real numbers, then convert the result to an integer. That’s what we did above, but what if we incorporate the “integerification” into Newton’s algorithm itself so that we never work with real numbers?

This is a reasonable idea, but we don’t know a priori that it will work. Sometimes integer problems can be solved by integer analogs of real algorithms, but sometimes not. Integer optimization problems are harder than real number optimization problems because the optimal integer solution cannot in general be found by first finding the optimal real solution and rounding. And even when this approach works, it may not be the most efficient approach.

It turns out that the integer analog of Newton’s method does work. Bressoud [1] gives pseudocode for an algorithm which I write in Python below.

def sqrt_floor(n):
    a = n
    b = (n + 1) // 2
    while b < a:
        a = b
        b = (a*a + n) // (2*a)
    return a

Note that in Python the // operator carries out integer division, i.e. a // b computes ⌊a/b⌋.

The somewhat opaque line updating b inside the loop is just Newton’s method, averaging a and n/a, rounded down.

This algorithm could run on hardware with no floating point capability, only integer arithmetic. It will also work on extended precision integers where floating point would fail. For example, the following Python code

from math import factorial, sqrt
sqrt(factorial(1000))

produces an error “OverflowError: int too large to convert to float.” But

sqrt_floor(factorial(1000))

works just fine.

Update: FIPS 184-5

After writing this post, I was looking through the NIST FIPS 184-5 Digital Signature Standard (DSS). In Appendix B.4 the standard gives an algorithm for determining whether a large integer is a square. The algorithm in the appendix is essentially the algorithm above. The line that carries out the Newton method update is not explained, but this post explains where this otherwise mysterious line comes from.

[1] David M. Bressoud. Factorization and Primality Testing. Springer, 1989.

The diff utility compares files by lines, which is often what you’d like it to do. But sometimes you’d like more granularity.

For example, supposed we want to compare two versions of Psalm 23. Here are the first three verses in the King James version:

The Lord is my shepherd; I shall not want.
He maketh me to lie down in green pastures:
he leadeth me beside the still waters.
He restoreth my soul:
he leadeth me in the paths of righteousness
for his name’s sake.

And here are the corresponding lines from a more contemporary translation, the English Standard Version:

The Lord is my shepherd; I shall not want.
He makes me lie down in green pastures.
He leads me beside still waters.
He restores my soul.
He leads me in paths of righteousness
for his name’s sake.

Save these in two files, ps23.kjv and ps23.esv. If we run

diff ps23.kjv ps23.esv

we get

This says that the two files differ in lines 2 through 5; the first and last lines are identical. The output shows lines 2 through 5 from each file but doesn’t show how they differ.

To see more fine-grained differences, such as changing maketh to makes, we can run the version of diff that comes with git.

If we run

git diff --word-diff ps23.kjv ps23.esv

we can compare the files by words rather than by lines. This produces

The colors help make the test more readable, assuming you can see the difference between red and green. I assume the color scheme is configurable. But the text is readable without the color highlighting. For example, in the first line we have

[-maketh-]{+makes+}

which means we remove the word maketh and add the word makes.

We can compare the files on an even finer level, comparing by characters rather than words. For example, rather than saying we need to change maketh to makes the software can say we need to change the th ending to s. We can do this by running

git diff  --word-diff-regex=. ps23.kjv ps23.esv

The option --word-diff-regex=. says to use the regular expression . to indicate word boundaries. Since the dot matches any character, this says to chop the lines into individual characters.

As before we have square brackets to indicate what to remove and curly braces to indicate what to add, but now we’re removing and adding letters rather than words.

We can get a more compact display of the differences if we rely on color alone, by adding the --word-diff=color option.

git diff  --word-diff=color --word-diff-regex=. ps23.kjv ps23.esv

produces the following.

Equivalently, we can combine the two options

--word-diff=color --word-diff-regex=.

into the one option

--color-words=.

that specifies the word separation regular expression as an option to --color-words.

This may be the most convenient way to see the differences, provided you can distinguish the colors, and don’t need to use the plain text programmatically. Without the colors, makeths, for example, becomes simply makeths and we can no longer be sure what changed.

I stumbled on the book Ed Mastery by Michael W. Lucas and couldn’t tell immediately whether it was serious. In a sort of technical version of Poe’s law, Lucas lays on the technical machismo pretty thick, but not thicker than some people do unironically.

Bravado

Here’s a paragraph from early in the book.

Many younger sysadmins naively hoist their pennants to defend overblown, overwrought, overdesigned text editors like ex, vi, or even the impossibly bloated nvi. A few are so lost as to devote themselves to turgid editors meant for mere users, such as vim and Emacs. This way lies not only appalling sysadmin skills, but an absence of moral fiber. As a sysadmin, you must have enough brain power to remember what you typed, to hold your own context in your head, and to truly commune with the machine on a deep and personal level.

By the time I read the reference to moral fiber I was pretty sure the author was being facetious.

Utility

The afterword to the book begins

Okay, come on Lucas, you’re not really serious here… are you?

I am. And I’m not.

This is what I find most interesting: ed is so minimal that it seems masochistic to use it, and yet it is also practical.

I’ve used Emacs for many years, but I’ve been learning the basics of vi because it is lightweight and installed everywhere [1]. But ed is even more lightweight and also installed everywhere.

My attraction to vi was that it’s complementary to Emacs. But ed is even more complementary. ed is so small that you don’t have to prioritize what to learn: just learn every feature. That is emphatically not true of vim or Emacs. Apparently you can learn ed in a day. Peter Krumins said

From my experience, once I had completed this cheat sheet and had it in front of me, I picked ed up in 30 minutes. And then spent a few more hours experimenting and trying various constructs.

History

I also find ed linguistically interesting. A lot of ed syntax is familiar because other tools inherited part of their syntax from ed. For example, sed and grep are direct descendants of ed, and the output of diff is basically ed syntax; with the -e flag the output of diffis exactly ed code. vim is “vi improved,” and vi was a visual interface to ex, which was an extension to ed.

[1] Here “everywhere” means “every Unix-like system.” When I worked in the Windows ecosystem I found this way of speaking arrogant and absurd. The large majority of the world’s desktops run Windows, and something that isn’t installed on Windows is hardly installed “everywhere.” Now I catch myself talking that way.