
Boost : 
Subject: Re: [boost] [fixed_point] First presentation from GSoC 2015 and more
From: Christopher Kormanyos (e_float_at_[hidden])
Date: 20161020 16:56:48
>>> 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, 32bit signed fixedpoint on a 32bit microcontroller.> If I get any sensible results compared with our polynomial> approximation, I will forward them to the thread.
I have benchmarked the iterative shiftandadd sqrt functioncompared with the polynomial approximation used inthe proposed Boost.Fixed_point. The benchmark usedbaremetal embedded microcontrollers.
I used a 32bit microcontroller at 24MHz and also an 8bitmicrocontroller 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 32bit microcontroller:
* polynomial approx : 6 microsec, sqrt(6/10) = 0.7745966
* Shiftandadd :15 microsec, sqrt(6/10) = 0.7745967
On 8bit microcontroller:
* polynomial approx. : 180us* Shiftandadd : 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_bare_metal_benchmark_32bit_sqrt_variation.cpp
Best regards, Chris.
On Sunday, October 16, 2016 9:20 PM, Michael Marcin <mike.marcin_at_[hidden]> wrote:
On 10/16/2016 12:52 PM, Christopher Kormanyos wrote:
>>> I would like to further investigate your sqrt implementation.
>
>> It seems the link to the whitepaper for sqrt has broken over the years.
>> I swear archive.org is the only thing keeping us from another dark age.
>
>> I found it again here:
>Â OK. Thank you. I will try to bench the iterative sqrt algorithm for,let's say, 32bit signed fixedpoint on a 32bit microcontroller.If I get any sensible results compared with our polynomialapproximation, I will forward them to the thread.
> One disadvantage of polynomial approximation is digit lossdue to argument reduction. Iterative and CORDIC seem tonot suffer from this, and cam be good options.
> Thanks for the suggestions.
>
Two things of note:
I'm pretty sure that sqrt is missing a bit of code to handle an odd
number of fractional bits (I never used any types that had these but is
probably important for a fully generic lib).
I'm pretty sure there is a low hanging fruit optimization opportunity to
use CLZ to skip a bunch of iterations before starting the loop.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk