Note that you might need to change the 2.22044604925031e-16 constant to 2 ULPs (4.44089209850063e-16) in order to get around some pathological rounding cases.
It probably will not be noticeable faster since you are only saving a few machine cycles per iteration. It might be noticeable unless you are running the calculation thousands or millions of times. -- The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume. >-----Original Message----- >From: sqlite-users <sqlite-users-boun...@mailinglists.sqlite.org> On >Behalf Of Bart Smissaert >Sent: Friday, 18 October, 2019 16:48 >To: SQLite mailing list <sqlite-users@mailinglists.sqlite.org> >Subject: Re: [sqlite] Standard deviation last x entries > >> However, to optimize the calculation the following is more efficient > >I tested it, but didn't find it any faster. >Naming makes it a lot clearer though. > >RBS > >On Fri, Oct 18, 2019 at 10:56 PM Keith Medcalf <kmedc...@dessus.com> >wrote: > >> >> We are calculating the square root using Newtons Method of successive >> approximation >> >> https://pages.mtu.edu/~shene/COURSES/cs201/NOTES/chap04/sqrt.html >> >> (x>0)*(y+x/y)/2 yi >> >> is computing the new guess of the square root of x based on the last >guess >> y and calling that calculation yi (the AS keyword is omitted). The >(x>0) >> part is to make sure that x is always a positive number otherwise the >new >> guess will be 0. This means that the attempt to find the square root >of a >> negative number (or 0) will always return 0 for each of two iterations >thus >> meeting the stop condition because abs(0 - 0) is less than any positive >> number. >> >> To use a CTE with better named variables one would use: >> >> with guesses(findRootOf, guessRoot, iteration) >> as ( >> select ?, 1.0, 1 >> union all >> select findRootOf, (findRootOf > 0) * (guessRoot + findRootOf >/ >> guessRoot) / 2.0 as newGuess, iteration + 1 >> from guesses >> where abs(newGuess - guessRoot) > 1e-12 >> limit 32 >> ) >> select guessRoot >> from guesses >> order by iteration desc >> limit 1; >> >> However, to optimize the calculation the following is more efficient >> (since it only calculates the new guess once each iteration, and >computes >> to the limit of precision). We are substituting calculating the guess >> twice and its difference from a constant (9 operations) with computing >the >> actual precision (6 operations): >> >> with guesses(findRootOf, guessRoot, iteration) >> as ( >> select ?, 1.0, 1 >> union all >> select findRootOf, (findRootOf > 0) * (guessRoot + findRootOf >/ >> guessRoot) / 2.0, iteration + 1 >> from guesses >> where abs(guessRoot*guessRoot - findRootOf) > >> (2.22044604925031e-16 * FindRootOf) >> limit 32 >> ) >> select guessRoot >> from guesses >> order by iteration desc >> limit 1; >> >> where 2.22044604925031e-16 is the epsilon of IEEE754 double precision >> floating point numbers (the limit of computational precision in the >last >> binary place) >> >> -- >> The fact that there's a Highway to Hell but only a Stairway to Heaven >says >> a lot about anticipated traffic volume. >> >> >-----Original Message----- >> >From: sqlite-users <sqlite-users-boun...@mailinglists.sqlite.org> On >> >Behalf Of Bart Smissaert >> >Sent: Friday, 18 October, 2019 14:55 >> >To: SQLite mailing list <sqlite-users@mailinglists.sqlite.org> >> >Subject: Re: [sqlite] Standard deviation last x entries >> > >> >Hi Olaf, >> > >> >Could you tell me what this is doing: >> > >> >,(x>0)*(y+x/y)/2 yi >> > >> >Especially the yi after the 2 >> >How does the yi relate to the preceding bit? >> > >> >RBS >> > >> > >> > >> >On Fri, Oct 18, 2019 at 8:26 PM Olaf Schmidt <n...@vbrichclient.com> >wrote: >> > >> >> Am 18.10.2019 um 19:45 schrieb Bart Smissaert: >> >> >> >> > Regarding: >> >> > >> >> > With r(s2, s, i) As (Select 2, 1, 1 Union All >> >> > Select s2, (s2>0)*(s+s2/s)*.5, i+1 From r Where Abs(s2- >s*s)>1e-12 >> >> > Limit 32 >> >> > ) Select s From r Order By i Desc Limit 1 >> >> > >> >> > How would this work if I wanted to update all the values in a >table >> >> column >> >> > to have the square root? >> >> >> >> Well, as with any other (single-value-returning) Sub-Select >> >> (which was enclosed in parentheses)... >> >> >> >> E.g. >> >> "Update MyTable Set MyCol = (Select 1)" >> >> would update MyCol with the value 1 across the whole table... >> >> >> >> Same thing basically (only "a bit larger") with a CTE-based >> >> "Single-Value-SubSelect"... >> >> >> >> BTW, I've updated and tuned the thing a bit (which should now >> >> offer more precision, and ~20% more performance as well): >> >> >> >> With r (x, y, i) As ( >> >> Select ?, 1, 1 Union All >> >> Select x,(x>0)*(y+x/y)/2 yi,i+1 From r Where Abs(yi-y)>1e-12 >Limit >> >32 >> >> ) Select y From r Order By i Desc Limit 1 >> >> >> >> Note the question-marked "Parameter" for the "squared Input-Value" >> >> (in the first Select Statement of the CTEs triple). >> >> >> >> Integrated into an Update-Query it could look this way: >> >> >> >> Update MyTable Set MySquareRoot = ( -- SubSelect-Opening-Paren... >> >> With r (x, y, i) As ( >> >> Select MySquaredValue, 1, 1 Union All >> >> Select x,(x>0)*(y+x/y)/2 yi,i+1 From r Where Abs(yi-y)>1e-12 >Limit >> >32 >> >> ) Select y From r Order By i Desc Limit 1 >> >> ) -- SubSelect-Closing-Paren... >> >> >> >> HTH >> >> >> >> Olaf >> >> >> >> _______________________________________________ >> >> sqlite-users mailing list >> >> sqlite-users@mailinglists.sqlite.org >> >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users >> >> >> >_______________________________________________ >> >sqlite-users mailing list >> >sqlite-users@mailinglists.sqlite.org >> >http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users >> >> >> >> _______________________________________________ >> sqlite-users mailing list >> sqlite-users@mailinglists.sqlite.org >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users >> >_______________________________________________ >sqlite-users mailing list >sqlite-users@mailinglists.sqlite.org >http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
