Challenge: optimizing isqrt

[Steven D'Aprano]

Stephen Tucker wrote:

> Another _possible_ performance improvement that is staring us in the face
> is that 2*b could be replaced with b<<1. Given that b+b (an earlier
> suggestion of mine) involves two table look-ups for b, whereas b<<1 only
> involves one, it seems that the scope here for improvement is significant.


As the Original Poster of this thread, I want to thank everyone who has
contributed and assure them that despite my silence so far, I do appreciate
your responses and I'm collecting the suggestions for later.


> By the way, I hope this post is not "top-posted" as my previous one was.
> Apologies for that - I am new to this kind of thing.

Alas, you have top posted. Has anyone explained what top posting is?

Reading from the top down, as is standard in English, an email conversation
will often take the following form. I'll use "=" to indicate quoted text
instead of the more common ">".

    = quoted comment
    = more text

    response

    = a question

    answer

    = a second question

    a second answer


Note that it reads like a conversation, "you say, I respond, you say, I
respond...". This is often called "interleaved posting" or "inline
posting", because the replies are interleaved between the questions. Also,
the quoted text is usually trimmed or "snipped" to remove parts which are
no longer relevant. The idea is to leave enough quoted content to establish
content, but without removing so much as to give a misleading impression,
or leaving so much in that the reader is overwhelmed by the volume of
quoted text.

To old-school email and Usenet users, inline posting is usually considered
far superior, *especially* for long and technical discussions like we often
find here.

Top posting usually ends up looking like this:


    response completely lacking any context

    = quoted comment
    = more text
    = text which is no longer relevant
    = a question
    = more text which is not relevant
    = and even more of it
    = a second question
    = and more text which is not being
    = commented on, so why is it left in?


Notice that it is all too easy to fail to answer the questions when top
posting. (To be fair, that's more a product of the person responding being
lazy or careless, but top posting does encourage lazy and careless
replies.)


Bottom posting often looks like this:

    = quoted comment
    = more text
    = text which is no longer relevant
    = a question
    = more text which is not relevant
    = and even more of it
    = a second question
    = and more text which is not being
    = commented on, so why is it left in?

    response lacking context


Note that the reader may end up having to scroll past many paragraphs (or
even pages!) of quoted text to discover the response. Which, all too often,
is a single sentence.


Thanks for contributing to the discussion.



-- 
Steven