Talk:Integer square root

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Low‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. Low This article has been rated as Low-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Mathematics Low‑priority Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. Low This article has been rated as Low-priority on the project's priority scale.

Request for a picture

If someone with Maple, Mathematica, etc. and would graph a function of isqrt, that would be very appreciated. I have use of Maple over Putty, but it displays graphs with ASCII characters, and it's hideous to look at. Iamunknown 09:26, Sep 13, 2004 (UTC)-

On second thought, is a graph necessary? Opinions, please. Iamunknown 18:53, 28 July 2006 (UTC)[reply]

It might be nice to have a plot for every specific function with its own article. To give a quick visual insight to what's going on. If the scale isn't terrible. WikiSlothBlobThing (talk) 02:13, 24 July 2021 (UTC)[reply]

Remarks about the writing

Hi Olegalexandrov. I was planning on editing the page again, but wanted to consult you beforehand. I think that the apostrophe in the bottom link needs to be escaped; otherwise Wikipedia fails to recognize the enclosed text as a link. On the flip-side, thanks for cleaning up after me! I messed up on standardization of 'x' and 'n', 'x_n', and 'valid' is much better than 'correct'. I am wondering, however, about your excess of links. For the words (take 'number theory' for example) that are throughout the document, I personally think that only one reference should be linked, presumably at the top. Since that was a bulk of your edit, though, I decided to ask you beforehand; I didn't want to completely reverse your edit! ('Recursive function' is also linked more than once.) Also, I completely realize my ambiguity in the statement, "The beauty of Newton's Iteration for finding the integer square root of a number n is that it can use solely integers," and was wondering what you thought about this statement: "The beauty of Newton's Iteration as used to find the integer square root of a number n is its inherent ability to stay within the set of integers, requiring no use of floating-point arithmetic." That was definitely what I trying to get at. Thanks! --Iamunknown 08:45, 11 Dec 2004 (UTC)

Thanks for the info about the excess links; I will be reverting that soon. I do mean that every operation can be performed in integers. About the statement,

The beauty of Newton's Iteration as used to find the integer square root of a number n is its inherent ability to stay within the set of integers, requiring no use of floating-point arithmetic,

I mean the function itself is wholly algebraic. It uses fractions, yes, but fractions are merely two integers placed atop and beneath one another. Keeping that into perspective, you could retain their integer identites and continue on with your calculation (still remaining in the set of integers) and when you have reached the desired accuracy, then do your final division.

--Iamunknown 21:50, 11 Dec 2004 (UTC)

Got it now! You meant to say that you use rational numbers, not integers. Then it all makes sense! So maybe you should write on the integer square root page that finding the square root directly gives you irrational numbers, while doing Newton's method gives you rational numbers. What do you think? --Olegalexandrov 22:15, 11 Dec 2004 (UTC)

Excellent! That is much easier to understand than what I previously had written. I'll definitely add that right now. Thanks, Olegalexandrov! --Iamunknown 22:29, 11 Dec 2004 (UTC)

Division-free square root

Is anyone interested in the divison-free algorithm for the square root? Obviously it only converges linearly rather than quadratically, but, especially in binary, it might be faster anyway. —The preceding unsigned comment was added by 80.175.250.218 (talk • contribs) 10:46, 31 October 2005 (UTC).[reply]

Actually, now that I think about it, it's only purely division-free in binary, not in other bases. —The preceding unsigned comment was added by 80.175.250.218 (talk • contribs) 10:48, 31 October 2005 (UTC).[reply]

Sure... I had to code up a division- (and multiplication)-free version for an 8 bit micro that had no divide or multiply instruction - you're welcome to use this if you want it. The code has been verified against all 65535 inputs:

u_int8_t IterSqrt(u_int16_t b) {
  u_int8_t i, j;
  u_int16_t step, prev, tot, isquared, jsquared;
  if (b <= 1) return b;
  i = j = 0; isquared = prev = tot = 0; step = 1;
  for (;;) { // maximum 255 iterations, but cheap compared to the 5 divides in software needed by Newton-Raphson.
    tot += step; step += 1; jsquared = tot+prev; prev = tot;     // calculate squares using 'table of differences' method.
    if (jsquared == 0) return 255U; // overflow and loop-end test in one!
    if (b >= isquared && b < jsquared) return i;     // test plausible square root: sqrt(b) = i IF i^2 <= b < (i+1)^2
    i += 1; isquared = jsquared;
  } // loop contains two full adds, two increments, and 3 comparisons.
}

Algorithm in terms of integers

The algorithm given in the article

${\displaystyle x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right),\ k\geq 0.}$

with ${\displaystyle x_{0}=n}$ works if you do integer calculations, too (truncate when dividing). Then the algorithm terminates when ${\displaystyle x_{k+1}=x_{k}}$. And as far as I can see, it actually converges a little faster. Wouldn't it make more sense for the article to do everything in terms of integers, instead of rationals? dbenbenn | talk 09:45, 18 March 2006 (UTC)[reply]

If you use truncation when dividing, the algorithm doesn't work when n=3, or any square less one. In that case it'll oscillate between sqrt(n+1) and sqrt(n+1)-1. CHL (aka yse) (talk) 14:04, 30 November 2008 (UTC)[reply]

The description of the algorithm in the article should explicitly state what kind of variables are used in the algorithm. It is very easy for someone to think that the variables are integers, for example.

My opinion is that the algorithm used should be in terms of integer variables. It seems that the context in which someone is most likely to look at the algorithm is when they are operating in integer domains, and algorithms based on non-integer computations will be of little interest in such situations. —Preceding unsigned comment added by 71.112.25.123 (talk) 00:18, 7 August 2009 (UTC)[reply]

Integer square root code in C

Would it be appropriate to post the following C code in the article? It is fast and tested:

#include <stdio.h>

/*
 * Return the truncated integer square root of "y" using longs.
 * Return -1 on error.
 */
long
lsqrt(long y)
{
        long    x_old, x_new;
        long    testy;
        int     nbits;
        int     i;

        if (y <= 0) {
                if (y != 0) {
                        fprintf(stderr, "Domain error in lsqrt().\n");
                        return -1L;
                }
                return 0L;
        }
/* select a good starting value using binary logarithms: */
        nbits = (sizeof(y) * 8) - 1;    /* subtract 1 for sign bit */
        for (i = 4, testy = 16L;; i += 2, testy <<= 2L) {
                if (i >= nbits || y <= testy) {
                        x_old = (1L << (i / 2L));       /* x_old = sqrt(testy) */
                        break;
                }
        }
/* x_old >= sqrt(y) */
/* use the Babylonian method to arrive at the integer square root: */
        for (;;) {
                x_new = (y / x_old + x_old) / 2L;
                if (x_old <= x_new)
                        break;
                x_old = x_new;
        }
        return x_old;
}

I have thoroughly tested this code and guarantee it is correct. --Gesslein 16:20, 2 July 2006 (UTC)[reply]

I do not know. I started a Integer square root codebase on Wikisource which was eventually deleted, because (although the programs in each language worked) the programs were original contributions. I think that applies to this article and would thus forbid you to place that code in the article, but I will forward the query to Charles Matthews, a prominent mathematics administrator. This article itself, however, may be an original contribution. He will be more likely to know than I. Iamunknown 20:03, 18 July 2006 (UTC)[reply]

I thought the terms of Wikipedia edits were "No original research". Contributions should always be welcome :-) --Gesslein 18:53, 28 July 2006 (UTC)[reply]

I agree that contributions should always be welcome. The proposed mathematics convention for algorithms, however, suggests that "Algorithms, like all other content in Wikipedia, should be traceable to reliable, published sources. Every presentation of an algorithm (both pseudocode and sample code) should include a citation." I agree with this, even though abiding by it currently prevents your code from inclusion. Iamunknown 19:34, 28 July 2006 (UTC)[reply]

Thanks for your thoughts on this. The algorithm used is Newton's method (also called the Babylonian method) described in the article. It gets a speed increase from using binary logarithms to select the starting value. --Gesslein 19:40, 28 July 2006 (UTC)[reply]

The thing about Newton-Raphson is that it iterates so quickly that a loop is seldom required - if the maximum integer size is known, then a fixed number of iterations can be used inline instead. For example:

u_int16_t isqrt32_nr(u_int32_t number) {
  u_int32_t guess2, guess1 = number, guess = number;

  if (number <= 1) return number;

  while (guess1) {  guess >>= 1; guess1 >>= 2;  } // ballpark - half the number of bits

  guess1 = (guess + number / guess) >> 1; // enough Newton-Raphson iterations for 32 bit input
  guess2 = (guess1 + number / guess1) >> 1;
  guess  = (guess2 + number / guess2) >> 1;           if (guess == guess1) return guess2;
  guess1 = (guess  + number / guess) >> 1;            if (guess1 == guess2) return guess;
  guess2 = (guess1 + number / guess1) >> 1;           if (guess2 == guess) return guess1;
  return (u_int16_t)guess2;
}

(Also verified against all 2^32 unsigned inputs. Takes about 10 minutes to test on my old i686 32-bit PC) — Preceding unsigned comment added by 70.124.38.160 (talk) 01:18, 22 May 2023 (UTC)[reply]

Extend definition to include zero

I would like to suggest that the definition is extended from 'a positive integer n' to 'a non-negative integer n', which would be in line with the definition of the (real-number domain) square root.

If that is accepted, it should be stated that the algorithm is only suitable for finding isqrt(n), n > 0.

Lklundin 09:53, 8 March 2007 (UTC).[reply]

Stopping criterion

Currently, there is a statement in the Algorithm section with an unsourced statement that ${\displaystyle |x_{k+1}-x_{k}|<1}$ implies ${\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor }$, which is not actually difficult to prove (contrary to what the text suggests). Of course, I can't cite myself, since that's original research. I'm going to remove the claim that the proof is not trivial; if anybody objects, reply here. (Oh, and no offence to the person who wrote that it isn't trivial.) CHL (aka yse) (talk) 07:28, 20 October 2009 (UTC)[reply]

Funny that you should nitpick over the claim that the proof is trivial, while you ignore that the claim is not true. The stopping criterion should be ${\displaystyle |x_{k+1}-x_{k}|<0.5}$, else if the root is in between 2 integers, the error could carry you over to the next number. 5.102.253.21 (talk) —Preceding undated comment added 15:43, 12 February 2014 (UTC)[reply]

Having looked back at my old "proof", it turned out to be rather shoddy and nonrigorous, but I have since retried proving it and the original stopping criterion of ${\displaystyle |x_{k+1}-x_{k}|<1}$ really is sufficient. Some algebraic manipulation on ${\displaystyle x_{k+1}=(x_{k}+n/x_{k})/2}$ gives ${\displaystyle (x_{k+1}-x_{k})^{2}=x_{k+1}^{2}-n}$. Assuming that ${\displaystyle |x_{k+1}-x_{k}|<1}$, we have ${\displaystyle {\sqrt {n}}\leq x_{k+1}<{\sqrt {n+1}}}$. Splitting this into the cases where ${\displaystyle n+1}$ is a perfect square and where ${\displaystyle n+1}$ is not leads straightforwardly in either case to ${\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor }$. CHL (aka yse) (talk) 10:43, 12 December 2014 (UTC)[reply]

irrational for "almost all"?

I doubt that √n is irrational for almost all n. I can easily give infinitely many n, such that √n is rational (even an integer). Maybe something like "for most n" was meant, though strictly this is not correct either, as there are exactly as many square numbers as non-square numbers ... --134.102.204.124 (talk) 16:17, 21 February 2012 (UTC)[reply]

It is irrational for almost all n, insofar as it is rational for a set of measure 0. CRGreathouse (t | c) 18:50, 21 February 2012 (UTC)[reply]

There are much more irrational numbers than rational numbers. — Preceding unsigned comment added by 129.97.171.175 (talk) 21:41, 3 March 2014 (UTC)[reply]

Notes ad Revision 08-12-2021 (01:11)

Ad 'Algorithm using linear search'

• In the previous revision(s) the C-code was changed. The type of the functions was changed from unsigned long long int to int.

Comment: In a fragment further down ^[1] the type used was unsigned long.^[2] An article should be consistent in style, so a mix of data types should be based on a reason, which here I do not see. I admit that by introducing unsigned long long int myself I did not stick to this design principle. I fixed this in the current release by changing the type throughout to unsigned long. Whatever the outcome shall be, I am in favour of keeping unsigned, to visualize that negative numbers are disallowed.

• The code

x = 1;
while( x * x <= y )
	x = x + 1;

was changed to

for( x = 1; x * x <= y; ++x )
	;

This is a change of syntax only. As a professional C-veteran myself I have no problems at all with this for-statement. My decision to use an equivalent while is based on the consideration that the present article is not an article about C. The readers can be expected to know some Pascal or Algol or BASIC or ... . Pseudocode too. But they are not necessarily experts in C. A for statement like this will pull many off. On the other hand the C-programmers also understand the while-construct. So why not stay on common ground?

Ad 'Algorithm using binary search'

• The assignments L = 0; R = y; are illegal without previous declaration of these variables. The code does not compile. I fixed this.

• In the previous revision the test while( L != R - 1 ) was changed to while( L < R - 1 ). The author hailed this as an increase of robustness. I disagree. For a while (condition){...} loop to be valid, the condition must at some point turn False. If the != condition is never met then the loop will run forever. An unexpected eternal loop is made more unlikely by strengthening the termination condition to <. As the procedure is designed to reach an = situation, the defensive reflex to allow illegitimate variable values to become even more illegitimate cannot be called 'more robust'. On the theoretical side see the following informal example.

• An inline variable declaration int const was introduced. This is not possible in many other languages. The attention is deflected to considerations about const and scope. Avoid! Keep it simple.

• I further simplified the code, keeping the proposed name change M instead of x.

• It was incorrectly mentioned that the linear search on input 2000000 would need 2000000 steps. 1414 steps are needed.

Reply

In 'Algorithm using linear search', you convinced me to keep the while loop, which indeed makes to code more understandible to non-C-programmers. However, for a similar reason, I'd still suggest to keep the involved types (throughout the whole article) as easy as possible. That is, long should be avoided, as it is very specific to C. My personal taste would also omit unsigned, but you have a point in explicitly disallowing negative numbers.

In 'Algorithm using binary search', you convinced me that != in the loop condition is more robust than < . On the other hand, the latter indicates the loop invariant L <= R in a better way. If you insist on !=, I won't object any further. As for the declaration of M, as far as I know, many languages allow new local declarations at the beginning of a block, i.e. immediately after a {. I found programs easier to understand if variable scopes are as small as possible, and if immutible variables are used whenever possible (using const in C); however, for a demonstration program of this small size, it doesn't make much difference, so I don't want to argue any further about this, either. In the while condition, I'm still in favor of omitting the parantheses; the involved operator priorities are the same in all programming languages I know, and in mathematics, so the expression is understandible for anybody without parantheses. Finally, you are right with 1414 vs. 2000000. - Jochen Burghardt (talk) 10:23, 8 December 2021 (UTC)[reply]

References

1. sub 'Example implementation in C'
2. Another fragment (further down) is not in C.

Notes ad Revision 27-02-2022‎ (16:51)

From the section Introductory remark I removed the sentence (which I had introduced myself):

"One can define ${\displaystyle {\sqrt {y}}}$ to be the number for which there is an algorithm — more precisely: "Turing machine" — which, given a second input parameter ${\displaystyle k}$, terminates with the decimal representation of ${\displaystyle {\sqrt {y}}}$ truncated to ${\displaystyle k}$ decimal digits."

My reasons for removal were:

• It looks like the definition of ${\displaystyle {\sqrt {y}}}$ is self-referential, as ${\displaystyle {\sqrt {y}}}$ appears in the definiens as well as in the definiendum. It is not, but a second thougth is required.

• The notion of "algorithm" is too broad, as it carries on its back the Church–Turing thesis. "Turing machine" is a more restrained concept. On the other hand I did not want to talk about Turing machines in this article.

• The removed sentence is not neccessary for the remark I make. The sentence might even obnubilate my point to some extent.

My revision has been reverted with the comment: "unexplained content removal".

As the content removal is explained here, I will "undo".

Marc Schroeder (talk) 20:31, 27 February 2022 (UTC)[reply]

Suggest correction or removal of "... using subtraction section"

As written, the program does not produce correct results for all input (e.g. for input 8 the program produces 3 and not the desired 2). This may have been an attempt to modify the algorithm to avoid needing to repeatedly insert zeros into digits as described in the referenced paper (see step R2 on page 1), which would involve more complicated arithmetic. 2604:3D08:6881:4A00:D9A0:6FE3:4F1F:17DE (talk) 17:50, 12 September 2022 (UTC)[reply]

Alternate methods

One approach described at https://leetcode.com/problems/sqrtx/editorial/ (paywalled) uses the Exponential Identity to rewrite sqrt(x) into e^((1/2)lnx. Obviously you need to then be able to calculate exponentials and logarithms

Another approach (probably only realistic in languages with fixed-width integer types) is to make lookup tables. (I.e. [0-1):0, [1-2): 1, [2-4):2, [4-9): 3, [9, 16): 4, [16-25): 5, [25-36): 6, [36-49): 7, to the desired length) which can then be binary-searched upon 2605:A601:A629:3300:9F2E:49BA:32DC:82AF (talk) 06:16, 9 November 2023 (UTC)[reply]

Yes, the log and exponential method is commonly known, so it is a bit surprising that it isn't in the article. However, logs and exponentials take a relatively long time to calculate. Also, you want the result to be exactly the correct integer, so you have to be careful with the floating-point math, to make sure you get the right result.

The table-lookup would be practical only for small ranges. For instance, if you wanted to take square roots of integers up to ${\displaystyle 2^{64}-1}$, the table would have ${\displaystyle 2^{32}-1}$ entries, each four bytes, or 16GB in total. Bubba73 ^{You talkin' to me?} 07:51, 9 November 2023 (UTC)[reply]

The denormalization in Karatsuba's algorithm is wrong.

In line 59 of the algorithm the remainder is generated by using the remainder of the normalized ${\displaystyle u}$ and simply denormalize it using the bit shift.

return (s >> denormalization_shift, r >> denormalization_shift);

This is simply incorrect and I can explain: Suppose ${\displaystyle u_{n}}$ is the normalized ${\displaystyle u}$. Then there exists a ${\displaystyle k}$ such that ${\displaystyle u_{n}=2^{2k}\cdot u}$. The algorithm already gave us the ${\displaystyle isqrt}$ and the remainder of ${\displaystyle u_{n}=s_{n}^{2}+r_{n}}$. Then we have ${\displaystyle u={\frac {u_{n}}{2^{2k}}}=\left({\frac {s_{n}}{2^{k}}}\right)^{2}+{\frac {r_{n}}{2^{2k}}}}$.

We can see the first problem at this point: The remainder needs to be shifted twice.

But there is an even bigger problem: ${\displaystyle s_{n}}$ is in general not devisable by ${\displaystyle 2^{k}}$. Suppose ${\displaystyle B}$ are the ${\displaystyle k}$ rightmost bits of ${\displaystyle s_{n}}$ and ${\displaystyle s}$ is the rest. We obtain ${\displaystyle u=\left(s+{\frac {B}{2^{k}}}\right)^{2}+{\frac {r_{n}}{2^{2k}}}=s^{2}+2^{-2k}\left(B\cdot \left(2^{k+1}s+B\right)+q\right)}$. Note that ${\displaystyle s}$ has the same definition as the first return value. Everything right of it is the remainder we were looking for as our second value. Trainpilot (talk) 17:49, 11 September 2024 (UTC)[reply]

Hello. Thank you for pointing this out. I've made some corrections. Is the code now correct? — Chai T. Rex (talk) 03:26, 5 September 2025 (UTC)[reply]

Disputed

"Algorithm using binary search" is incorrect. It can not compute the integer square root of 131072. W65C02 (talk) 05:15, 19 May 2025 (UTC)[reply]

It also isn't really binary search, it is more like the Bisection method. Bubba73 ^{You talkin' to me?} 05:58, 19 May 2025 (UTC)[reply]

Computation of ${\displaystyle \operatorname {isqrt} (131072)}$ using binary search.

The ${\displaystyle [L,R]}$ sequence is:

${\displaystyle {\begin{aligned}&[0,131073]\rightarrow [0,65536]\rightarrow [0,32768]\rightarrow [0,16384]\rightarrow [0,8192]\rightarrow [0,4096]\rightarrow [0,2048]\rightarrow [0,1024]\\&\rightarrow [0,512]\rightarrow [256,512]\rightarrow [256,384]\rightarrow [320,384]\rightarrow [352,384]\rightarrow [352,368]\rightarrow [360,368]\\&\rightarrow [360,364]\rightarrow [362,364]\rightarrow [362,363]\end{aligned}}}$

The search terminates with ${\displaystyle L=362}$ and ${\displaystyle R=363}$.

${\displaystyle \operatorname {isqrt} (131072)=362}$

Verification: ${\displaystyle 362^{2}=131044\leq 131072<363^{2}=131769}$ ✅

Marc Schroeder (talk) 23:58, 27 September 2025 (UTC)[reply]

Please refrain from removing the disputed template until after you bother to execute the code yourself. W65C02 (talk) 01:15, 28 September 2025 (UTC)[reply]

I had hoped that presenting the step-by-step values of the main variables could convince you that the algorithm behaves correctly for the input ${\displaystyle 131072}$. As you still question its accuracy, allow me to be more explicit: see below. Could you please indicate where you suspect a flaw, if any?

// Integer square root (using binary search)
unsigned int isqrt(unsigned int y)
{
    unsigned int L = 0;      // lower bound of the square root
    unsigned int M;          // midpoint to test
    unsigned int R = y + 1;  // upper bound of the square root
    while (L != R - 1)
    {
        M = (L + R) / 2;
        if (M * M <= y)
            L = M;
        else
            R = M;
    }
    return L;
}

The loop continues until ${\displaystyle L}$ and ${\displaystyle R}$ are consecutive integers ${\displaystyle (L==R-1)}$.

Step-by-Step for ${\displaystyle y=131072}$

Initialization:

• ${\displaystyle L=0,R=131072+1=131073}$

Iteration 1:

• ${\displaystyle M=(0+131073)/2=65536}$
• ${\displaystyle M*M=65536^{2}=4294967296>131072\to {\text{ too big}}}$
• ${\displaystyle {\text{Update }}R=65536}$

Iteration 2:

• ${\displaystyle M=(0+65536)/2=32768}$
• ${\displaystyle 32768^{2}=1073741824>131072\to {\text{ too big}}}$
• ${\displaystyle {\text{Update }}R=32768}$

Iteration 3:

• ${\displaystyle M=(0+32768)/2=16384}$
• ${\displaystyle 16384^{2}=268435456>131072\to {\text{ too big}}}$
• ${\displaystyle {\text{Update }}R=16384}$

Iteration 4:

• ${\displaystyle M=(0+16384)/2=8192\to {\text{ too big }}\to R=8192}$

Iteration 5:

• ${\displaystyle M=4096\to {\text{ too big }}\to R=4096}$

Iteration 6:

• ${\displaystyle M=2048\to {\text{ too big }}\to R=2048}$

Iteration 7:

• ${\displaystyle M=1024\to {\text{ too big }}\to R=1024}$

Iteration 8:

• ${\displaystyle M=512\to {\text{ too big }}\to R=512}$

Iteration 9:

• ${\displaystyle M=256}$
• ${\displaystyle 256^{2}=65536\leq 131072\to {\text{ OK}}}$
• ${\displaystyle {\text{Update }}L=256}$

Iteration 10:

• ${\displaystyle M=(256+512)/2=384}$
• ${\displaystyle 384^{2}=147456>131072\to {\text{ too big }}\to R=384}$

Iteration 11:

• ${\displaystyle M=(256+384)/2=320}$
• ${\displaystyle 320^{2}=102400\leq 131072\to {\text{ OK }}\to L=320}$

Iteration 12:

• ${\displaystyle M=(320+384)/2=352}$
• ${\displaystyle 352^{2}=123904\leq 131072\to {\text{ OK }}\to L=352}$

Iteration 13:

• ${\displaystyle M=(352+384)/2=368}$
• ${\displaystyle 368^{2}=135424>131072\to {\text{ too big }}\to R=368}$

Iteration 14:

• ${\displaystyle M=(352+368)/2=360}$
• ${\displaystyle 360^{2}=129600\leq 131072\to {\text{ OK }}\to L=360}$

Iteration 15:

• ${\displaystyle M=(360+368)/2=364}$
• ${\displaystyle 364^{2}=132496>131072\to {\text{ too big }}\to R=364}$

Iteration 16:

• ${\displaystyle M=(360+364)/2=362}$
• ${\displaystyle 362^{2}=131044\leq 131072\to {\text{ OK }}\to L=362}$

Iteration 17:

• ${\displaystyle M=(362+364)/2=363}$
• ${\displaystyle 363^{2}=131769>131072\to {\text{ too big }}\to R=363}$

Exit Condition

• ${\displaystyle {\text{Now }}L=362,R=363\to L==R-1\to {\text{ exit loop}}}$
• ${\displaystyle {\text{Return }}L=362}$

✅ Integer square root of ${\displaystyle 131072}$ is ${\displaystyle 362}$

Check

${\displaystyle 362^{2}=131044\leq 131072}$

${\displaystyle 363^{2}=131769>131072}$

Correct!

Marc Schroeder (talk) 01:18, 29 September 2025 (UTC)[reply]

The disputed section is specifically the C code/implementation.

https://godbolt.org/z/1EEneWd4r isqrt(131072) evaluates to 65536, not 362. W65C02 (talk) 03:33, 29 September 2025 (UTC)[reply]

If you correctly format the print

printf("%u\n", isqrt(131072));

instead of

printf("%d\n", isqrt(131072));

then you will get the correct output 362.

Have a good day!

Marc Schroeder (talk) 05:43, 29 September 2025 (UTC)[reply]

Did you actually try this yourself, or are you guessing? W65C02 (talk) 13:53, 29 September 2025 (UTC)[reply]

This morning (in Europe) I saw in your listing that you had used the unsupported format "%d" for unsigned int. I could reproduce the incorrect display (65536) on my system. With "%u" the display became allright (362). Only then did I post the reply on the talk page. Later I noticed an incorrect occurrence of "%d" in section "Introductory remark". I fixed that without investigation.

Now I have two questions:

1. When a bug is detected in software that might be the cause of unwanted behaviour, the first step is to fix the bug and then check the outcome.^[1] I must assume that you have done that. What output did you get after correcting the print format to "%u"?
2. In my second reply I provided a line-by-line report of a run of the code on input 131072. At what iteration number does the program go astray in your opinion?

If you agree that the issue is now resolved and there is no longer a substantive disagreement about the code or its output, the "disputed" flag can probably safely be removed.

Marc Schroeder (talk) 17:13, 29 September 2025 (UTC)[reply]

This is not a matter of "opinion"--the function is verifiably incorrect.

The format specifier is irrelevant in this case.

Complete testcase and execution, showing incorrect behavior: https://godbolt.org/z/W41Yjd6hE

The disputed template should not be removed until the C implementation is corrected. The C implementation of isqrt is not able to compute the value of isqrt(131072). The expected value of isqrt(131072) is 362. The actual value returned by the current C implementation of isqrt(131072) is 65536.

Carefully review the output as shown on godbolt, and execute the function yourself before blindly assuming the code is correct. W65C02 (talk) 17:24, 29 September 2025 (UTC)[reply]

Here is a larger test case:

#include <stdint.h>
#include <stdio.h>
#include <math.h>
// Integer square root (using binary search)
unsigned int isqrt(unsigned int y)
{
    unsigned int L = 0;      // lower bound of the square root
    unsigned int M;          // midpoint to test
    unsigned int R = y + 1;  // upper bound of the square root
    while (L != R - 1)
    {
        M = (L + R) / 2;
        if (M * M <= y)
            L = M;
        else
            R = M;
    }
    return L;
}
int main()
{
  int64_t correct = 0;
  int64_t incorrect = 0;
  for (int64_t i = 0x7fffffff; i > 0; i--) {
    int64_t expected = sqrt((double)i);
    int64_t actual   = isqrt(i);
    if (expected != actual) {
      //printf("%ld : %ld != %ld\n", i, expected, actual);
      incorrect += 1;
    } else {
      correct += 1;
    }
  }
  // isqrt does not terminate for all values larger than 0x7fffffff
  incorrect += (0xffffffff - 0x7fffffff);
  printf("correct: %ld\n", correct);
  printf("incorrect: %ld\n", incorrect);
}

The output of this program is:

correct: 357238687
incorrect: 3937728608

W65C02 (talk) 17:52, 29 September 2025 (UTC)[reply]

I can confirm that the code produces erroneous output on a 64bit machine (under linux / gcc 13.3.0, int: 4 bytes, long: 8 bytes). I see two possible reasons: (1) the expression "L+R" may overflow, (2) the expression "M*M" may overflow. When I deleted the declation of M, and changed the first loop body statement to "unsigned long const M = L + (R-L)/2;", I got no more errors reported during the range from 2147000000 down to 2084000000 (i.e. the first few million tests; I didn't check the rest). The computation of M is discussed in https://github.com/fraunhoferfokus/acsl-by-example/blob/master/ACSL-by-Example.pdf , sect.6.1.2. The computation of M*M is done in 8-byte arithmetic due to the type of M, and hence can't overflow if M fits into 4 bytes. - Jochen Burghardt (talk) 15:44, 30 September 2025 (UTC)[reply]

As with many other examples in this article, this C snippet is intended for illustration and does not account for integer overflow. For large values of y (in particular, UINT_MAX), the code will produce incorrect results due to wraparound. Other examples in the article have the same limitation.

One possible remedy is to promote the arithmetic to a wider integer type before performing the calculation, then convert back the return value, for example:

// Integer square root (using binary search)
unsigned int isqrt(unsigned int y)
{
    int64_t L = 0;
    int64_t M;
    int64_t R = (int64_t)y + 1;
    while (L != R - 1)
    {
        M = (L + R) / 2;
        if (M * M <= y)
            L = M;
        else
            R = M;
    }
    return (unsigned int)L;
}

That said, adding such fixes may distract from the didactic purpose of the snippet. The code is intended to illustrate language-independent algorithmic complexity rather than to serve as a production-ready implementation. Introducing details such as int64_t or explicit casts could confuse readers who are less familiar with C, diverting attention from the main idea. The snippets are best regarded as executable pseudocode.

The limitations vanish when the examples are converted to Python, which avoids integer overflow by design:

# Integer square root (using binary search)
def isqrt(y):
    L = 0
    R = y + 1
    while (L != R - 1):
        M = (L + R) // 2
        if (M * M <= y):
            L = M
        else:
            R = M
    return L

However, per MOS:RETAIN, Wikipedia’s style guideline states that the style of an article should not be changed if it is already using one acceptable style, unless there is a strong reason. It is not clear whether avoiding overflow alone is sufficient justification to switch the examples from C to Python, though it may be worth discussing further.

Marc Schroeder (talk) 02:02, 2 October 2025 (UTC)[reply]

If someone proposed to change all examples from C to some language supporting unlimited arithmetic by default, I wouldn't object. Also, I'd find it ok to add an introductory remark that pseudo-code is shown, not C (in that case, at least the C-specific data types should be replaced by e.g. "integer"). In the current form, however, I expect many readers to copy-and-paste the C code into their C programs; in this case, multiplication overflow is an issue (I've wasted dozens of hours of my life debugging my code when multiplication overflow had caused the observed error), and should be warned about, imo. - Jochen Burghardt (talk) 11:29, 2 October 2025 (UTC)[reply]

I will port the whole article to Python if user WC65C02 does not object.

One comment about the wrong output ${\displaystyle \operatorname {isqrt} (131072)\to 65536=2^{16}\neq 362=\lfloor {\sqrt {131072}}\rfloor }$.

The (rightfully) disputed C isqrt example can produce incorrect results for large inputs due to 32-bit unsigned integer overflow. Specifically, when the midpoint M exceeds 65,535, the product M * M exceeds UINT_MAX (4,294,967,295) and wraps around. Inputs y ≥ 131,071 can overflow modulo 2³², producing unexpectedly large numbers. Smaller inputs (y < 131,071) are unaffected. Why on my system the code did not break on input 131072 is not relevant, but it didn't.

Marc Schroeder (talk) 12:33, 2 October 2025 (UTC)[reply]

Sure, do it. W65C02 (talk) 13:46, 2 October 2025 (UTC)[reply]

Fine for me, too. (Maybe your int is 64-bit by default? Try 4294967295 and 4294967297 as input.) - Jochen Burghardt (talk) 16:37, 2 October 2025 (UTC)[reply]

1. In production software there may be reasons to maintain the error, when bugfixes might propagate through the system.