RE: [PATCH v10 1/3] lib: Add strongly typed 64bit int_sqrt

From: David Laight
Date: Thu Dec 21 2017 - 05:59:21 EST


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