Re: [boost] [fixed_point] First presentation from GSoC 2015 and more

Subject: Re: [boost] [fixed_point] First presentation from GSoC 2015 and more
From: Christopher Kormanyos (e_float_at_[hidden])
Date: 2016-10-20 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, 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_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, 32-bit signed fixed-point on a 32-bit 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