3
$\begingroup$

As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary.

I'm sure this is not original; can anyone provide a reference?

// All arithmetic is truncating unsigned integer arithmetic
// Actual implementation uses bit shifts
// Indention level defines statement scope

def sqrt(r)                         // r is an unsigned integer
    residue = r                     // residue will be the 'remainder'
    root = 0                        // root will be the integer square root (floor(r**0.5))
    onebit = 2**(bitlength(r)-2)    // onebit is a moving 'bitpicker'
    while onebit > r                
        onebit = onebit / 4         // find highest bitpicker less than r
    while onebit > 0 
        x = root + onebit           // Current root plus onebit
        if residue >= x             // Room to subtract?
            residue = residue - x   // Yes - deduct from residue
            root = x + onebit       // and step root
        root = root / 2             // Slide evolving root 1 bit down the residue
        onebit = onebit / 4         // Slide the bitpick 1 bit down the root
    assert(root**2 + residue == r)
    assert((root+1)**2 > r)
    return root, residue
$\endgroup$
  • 1
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Feb 4 '16 at 11:23
  • $\begingroup$ @Raphael I have no ideas; no arguments of correctness (beyond that it works, which is no argument at all), and I have no idea how to convert it to pseudocode that would, speculatively, be acceptable here. So, I've deleted it. $\endgroup$ – Brent.Longborough Feb 4 '16 at 12:22
  • 3
    $\begingroup$ Too bad, I found the reference question to be ontopic and potentially interesting. (That comment is a canned one, and only applies so much in any given situation. Here, the argument would mostly have been that a Go implementation may not be readable for many, so they could not see which algorithm this is even if they knew it.) $\endgroup$ – Raphael Feb 4 '16 at 12:38
  • $\begingroup$ @Raphael After your kind words, I've undeleted it. I'll hope to edit it later to try and turn it into some kind of pseudocode; just right now, I have some other priorities nagging at me. $\endgroup$ – Brent.Longborough Feb 4 '16 at 12:50
  • 2
    $\begingroup$ @Raphael, question on code per se are offtopic, but a (not too weird language) program that isn't too long is better than some mushily defined pseudocode. $\endgroup$ – vonbrand Feb 4 '16 at 14:38
7
$\begingroup$

The wikipedia article on Methods of computing square roots: base 2 presents a strikingly similar snippet of C-code [a], but the link to the source is dead. Let's try to do better.

The snippets from both wikipedia and the question are very similar to Martin Guy's widely circulated C implementation [b]. which contains a comment: From a book on programming abaci by Mr C. Woo. Search engine use suggests this is [1] - one edition seems to be from 1930; it has been reprinted, e.g. [2].

The age of the method is bound to be on the order of two millenniums - the original reference might be difficult to obtain.

A purportedly[z] very similar Algorithm has been presented by TIJ Rolfe, who in turn refers to [3].


  1. Woo, C.C. The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus, China Lace Co., Ltd., Hong Kong
  2. Kwa Tak Ming, C. C. Woo, The Fundamental Operations in Bead Arithmetic. How to Use the Chinese Abacus, Literary Licensing, LLC, United States, 2012, 9781258466855
  3. Hart, W.L. "College Algebra" 4th ed., Boston, 1955, p.424
$\endgroup$
  • $\begingroup$ how to protect spaces using markdown - the correct answer is that you should not protect spaces. Like Raphael said, content is served in different ways, e.g., to users on tablets, mobile devices, and web browsers with windows of different sizes. Therefore, doing things like that is generally discouraged. $\endgroup$ – D.W. Feb 5 '16 at 1:17
  • 1
    $\begingroup$ This is how I'd do it. Clear formatting in code and rendered form, and the reference data moved to the bottom so the grammatical sentences are easy to parse. (cc @D.W.) I'd add robust links (ideally with DOIs) for these references, if any exist. $\endgroup$ – Raphael Feb 5 '16 at 9:45
  • $\begingroup$ No, and I'm telling you that you are wrong. :) (About the principle; I don't claim my execution is the only admissible one.) $\endgroup$ – Raphael Feb 5 '16 at 10:00
  • $\begingroup$ A substantive comment (not about formatting): I can't tell how the answer relates to the question. Can anyone edit the answer to clarify? Is the answer implying that the code in the question is the same as Martin Guy's widely circulated C implementation? If so, it would help to state that explicitly. $\endgroup$ – D.W. Feb 5 '16 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.