Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Sort of trivial code challenge - may be interesting to you anyway
Date: Wed, 11 Mar 2026 07:57:52 -0700
Organization: A noiseless patient Spider
Lines: 86
Message-ID: <86zf4e8lcf.fsf@linuxsc.com>
References: <10n80sc$3soe4$1@dont-email.me> <86v7feei2e.fsf@linuxsc.com> <10o53k6$1i0ef$2@dont-email.me> <86ms0peby6.fsf@linuxsc.com> <10ockdh$3qpk6$1@dont-email.me> <10ocrjn$3qpk6$2@dont-email.me> <10od30j$79v9$1@dont-email.me> <20260307220446.000077d9@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 11 Mar 2026 14:57:59 +0000 (UTC)
Injection-Info: dont-email.me; posting-host="5f44bcdbc02769ce6998caa4a4cb2206"; logging-data="1172321"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18Q5P7+nsyJj6mS9nogOjs/4gxeREdr6qQ="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:VHTQscShBYQaQEUflcvbSSWZ9Ow= sha1:L80dl6mwnQM8sTGzjYUtEfOrNeA=
Xref: csiph.com comp.lang.c:396904

Michael S <already5chosen@yahoo.com> writes:

[concerning implementing integer square root]

> Here is O(log(N)) variant [...]
>
> unsigned usqrt(unsigned x)
> {
>   if (x < 2)
>     return x;
>   unsigned y = x/2, r;
>   while ((r = x / y) < y)
>     y = (r + y) / 2;
>   return y;
> }

Right, O(log(N)).  The initial guess is kind of out in left field so
it takes a while to get into a good zone of convergence.

> And here is variation that is a little less simple, but not
> complicated and faster than one before, because it does fewer
> divisions.  The number of divisions that can't be implemented as
> shift is at most ceil(sqrt(ceil(log2(ceil(sqrt(val)))
>
> unsigned usqrt(unsigned x)
> {
>   if (x < 2)
>     return x;
>   unsigned y = 8, xx = x;
>   while (xx > 63) {
>     xx /= 64;
>     y *= 8;
>   }
>   unsigned r;
>   while ((r = x / y) < y)
>     y = (r + y) / 2;
>   return y;
> }

Here I think your analysis is a little off.  Newton's Method has
quadratic convergence, given an appropriate initial guess.  That
means the second while loop is O(log(# bits)), or O(log(log(N))).

The initial loop, to find a good initial guess, can also be made to
be O(log(log(N)));  exercise for the reader.

The foregoing assumes the usual C operators are O(1), which of
course isn't right as the width of the type involved gets larger,
but that assumption is typically made in this kind of analysis.

(Note: since the width of unsigned int is fixed, technically the
performance of these algorithms is all O(1).  But usually that
condition of constant width is ignored in this sort of discussion.)

> And here is less simple but still obvious implementation that does
> no divisions at all.  No multiplications as well.
>
> unsigned usqrt(unsigned x)
> {
>   if (x < 2)
>     return x;
>   unsigned xx = x;
>   int e = 0;
>   while (xx > 63) {
>     xx /= 64;
>     e += 3;
>   }
>   while (xx > 3) {
>     xx /= 4;
>     e += 1;
>   }
>   unsigned y = 1u << e;
>   x -= y << e;
>   for (e = e - 1; e >= 0; --e) {
>     unsigned d = y*2 + (1u << e);
>     if (d <= (x >> e)) {
>       x -= d << e;
>       y += 1u << e;
>     }
>   }
>   return y;
> }

Here the behavior is linear in the number of bits, or O(log(N)).  At
some point (but not for 32-bit integers) the division method wins
out.