I have benchmarked the iterative shift-and-add sqrt>> functioncompared with the polynomial approximation>> used in the proposed Boost.Fixed_point. The benchmark>> used bare-metal embedded microcontrollers. I was able to reproduce your results on win64 using vs2015. I was able to trick the compiler and double the speed of the iterative method but was unable to approach the poly approx in performance.
results at the top of this link (requires google benchmark)> http://codepad.org/CF84VtYS
Thanks for running the tests. Nice work! Thanks for the refinements. I think we havea couple of good options for sqrt now. The shift-and-addmight be effective in certain digit ranges such as betweenlong double and 128-bit. I think it is always a good idea to have a few options foralgorithms.
Best regards, Chris
On Friday, October 21, 2016 6:06 AM, Michael Marcin
I would like to further investigate your sqrt implementation.
It seems the link to the whitepaper for sqrt has broken over the years.
I found it again here:>> http://www.realitypixels.com/turk/computergraphics/FixedSqrt.pdf OK. Thank you. I will try to bench the iterative sqrt algorithm for,> let's say, 32-bit signed fixed-point on a 32-bit microcontroller.> If I get any sensible results compared with our polynomial> approximation, I will forward them to the thread. I have benchmarked the iterative shift-and-add sqrt functioncompared with the polynomial approximation used inthe proposed Boost.Fixed_point. The benchmark usedbare-metal embedded microcontrollers.
I used a 32-bit microcontroller at 24MHz and also an 8-bitmicrocontroller at 16MHz. I used an argument of 6/10 forthe sqrt function. The fixed_point type used was:boost::fixed_point::negatable<7, -24>. Timing measurementshave been done with a digital ascilloscope. GCC 5.2 and 5.3have been used.
On 32-bit microcontroller: * polynomial approx : 6 micro-sec, sqrt(6/10) = 0.7745966 * Shift-and-add :15 micro-sec, sqrt(6/10) = 0.7745967 On 8-bit microcontroller: * polynomial approx. : 180us* Shift-and-add : 450us Here, the unit [us] means microseconds.
The benchmark code is available at develop branch here: https://github.com/BoostGSoC15/fixed_point/blob/develop/example/fixed_point_... Best regards, Chris.
I was able to reproduce your results on win64 using vs2015. I was able to trick the compiler and double the speed of the iterative method but was unable to approach the poly approx in performance. results at the top of this link (requires google benchmark) http://codepad.org/CF84VtYS Thanks for running the tests. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost