From: David Laight <David.Laight@ACULAB.COM>
To: "'Crt Mori'" <cmo@melexis.com>
Cc: Peter Zijlstra <peterz@infradead.org>,
Jonathan Cameron <jic23@kernel.org>,
Ingo Molnar <mingo@kernel.org>,
Andrew Morton <akpm@linux-foundation.org>,
Kees Cook <keescook@chromium.org>,
Rusty Russell <rusty@rustcorp.com.au>,
Ian Abbott <abbotti@mev.co.uk>,
Larry Finger <Larry.Finger@lwfinger.net>,
Niklas Soderlund <niklas.soderlund+renesas@ragnatech.se>,
Thomas Gleixner <tglx@linutronix.de>,
Krzysztof Kozlowski <krzk@kernel.org>,
Masahiro Yamada <yamada.masahiro@socionext.com>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
"linux-iio@vger.kernel.org" <linux-iio@vger.kernel.org>,
Joe Perches <joe@perches.com>
Subject: RE: [PATCH v10 1/3] lib: Add strongly typed 64bit int_sqrt
Date: Thu, 21 Dec 2017 10:59:19 +0000 [thread overview]
Message-ID: <d595eac5b5744a3a96cda44d96b08b53@AcuMS.aculab.com> (raw)
In-Reply-To: <CAKv63utKNW2--ZnkoJ0z++68764cX_S9xS9Gst_vj7eDsFAZrg@mail.gmail.com>
From: Crt Mori
> Sent: 20 December 2017 17:30
> >> OK, is there any more easy optimizations you see?
> >
> > I think this version works.
> > It doesn't have the optimisation for small values.
> >
> > unsigned int sqrt64(unsigned long long x)
> > {
> > unsigned int x_hi = x >> 32;
> >
> > unsigned int b = 0;
> > unsigned int y = 0;
> > unsigned int i;
> >
> > for (i = 0; i < 32; i++) {
> > b <<= 2;
> > b |= x_hi >> 30;
> > x_hi <<= 2;
> > if (i == 15)
> > x_hi = x;
> > y <<= 1;
> > if (b > y)
> > b -= ++y;
> > }
> > return y;
> > }
..
>
> I did a quick run through unit tests for the sensor and the results
> are way off. On the sensor I had to convert double calculations to
> integer calculations and target was to get end result within 0.02 degC
> (with previous approximate sqrt implementation) in sensor working
> range. This now gets into 3 degC delta at least and some are way off.
> It might be off because of some scaling on the other hand during the
> equation (not exactly comparing sqrt implementations here).
I didn't get it quite right...
The last few lines need to be:
if (b > y) {
b -= ++y;
y++;
}
}
return y >> 1;
}
Although that then fails for inputs larger than 2^62.
David
next prev parent reply other threads:[~2017-12-21 10:59 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-12-20 14:20 [PATCH v10 1/3] lib: Add strongly typed 64bit int_sqrt Crt Mori
2017-12-20 14:39 ` David Laight
2017-12-20 15:41 ` Crt Mori
2017-12-20 16:00 ` Peter Zijlstra
2017-12-20 16:17 ` Crt Mori
2017-12-20 16:46 ` David Laight
2017-12-20 17:19 ` Joe Perches
2017-12-21 10:02 ` David Laight
2017-12-20 17:30 ` Crt Mori
2017-12-21 10:08 ` David Laight
2017-12-21 10:59 ` David Laight [this message]
2017-12-21 11:43 ` David Laight
2017-12-21 13:17 ` Crt Mori
2017-12-21 13:56 ` David Laight
2017-12-21 14:11 ` Peter Zijlstra
2017-12-21 14:48 ` David Laight
2017-12-22 13:44 ` Crt Mori
2018-01-09 15:18 ` Crt Mori
2018-01-12 9:41 ` David Laight
2018-01-15 8:17 ` Crt Mori
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=d595eac5b5744a3a96cda44d96b08b53@AcuMS.aculab.com \
--to=david.laight@aculab.com \
--cc=Larry.Finger@lwfinger.net \
--cc=abbotti@mev.co.uk \
--cc=akpm@linux-foundation.org \
--cc=cmo@melexis.com \
--cc=jic23@kernel.org \
--cc=joe@perches.com \
--cc=keescook@chromium.org \
--cc=krzk@kernel.org \
--cc=linux-iio@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=niklas.soderlund+renesas@ragnatech.se \
--cc=peterz@infradead.org \
--cc=rusty@rustcorp.com.au \
--cc=tglx@linutronix.de \
--cc=yamada.masahiro@socionext.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).