[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Fri, 17 Feb 2023 17:53:25 -0500
From: Rich Felker <dalias@...c.org>
To: Bobby Bingham <koorogi@...rogi.info>
Cc: musl@...ts.openwall.com
Subject: Re: [RFC] new qsort implementation
On Fri, Feb 17, 2023 at 10:51:14AM -0500, Rich Felker wrote:
> Regarding the sqrt, nowadays musl's sqrt is basically all integer code
> except on targets with a native sqrt instruction, so it's probably not
> catastrophic to performance on softfloat archs. However, it is a
> little bit sketchy with respect to determinism since it's affected by
> (and in turn alters) the floating point environment (rounding mode,
> exception flags). I assume only an approximation within some
> reasonable bounds (to ensure the desired big-O) is needed, so it
> probably makes sense to do a fast integer approximation. Maybe even
> something that's essentially just "wordsize minus clz, >>1, 1<<that,
> multiply by 1.4 if shifted-out bit was 1" would suffice.
Indeed, an approach like this (which is just taking the first-order
approximation of sqrt centered at the next-lower power of two) seems
to have a max error of around 6.7%, and the cost is essentially just
one clz and one divide. If you're happy with up to 25% error, using
the next-lower *even* power of two has a cost that's essentially just
one clz. I think either could be made significantly better by using
the nearest (resp. nearest-even) power of two rather than always going
down, without any significant addition of costly operations.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
