Re: [Codel] fp sqrt vis int sqrt?

[Jim Gettys <jg@freedesktop.org>]

On 05/04/2012 11:11 AM, Dave Taht wrote:
> The linux kernel has no floating point in it, so I'd substituted the
> internal int_sqrt as a substitute,
> just to get something to work.
>
> static inline ktime_t control_law(const struct codel_sched_data *q, ktime_t t)
> {
>         return ktime_add_ns(t, q->interval / int_sqrt(q->count));
> }
>
> Often ns2 models use floating point. Having not seen the model I don't
> know that for sure.
>
> The series for an integer sqrt is far more 'chunky' than a fp one.
>
> int sqrt 1,2,3,4 = 1 1 1 2
> fp sqrt 1 2 3 4 = 1 1.4.1 1.73 2
>
> and gets even more chunky as you get larger values, eg, sqrt(36
> through 48) = 6, sqrt(49) = 7
>
> So we could precalculate the interval/sqrt(count) using floating point
> in the control law calculation,
> early, during qdisc setup, thus neatly avoiding both the divide and
> sqrt in the control law path.
>
> Or we could do fixed point.
>
> Kathie: In the sim, in various simulations, what is the dynamic range
> of count? And is it floating point sqrt?
>
The Wikipedia article on fast inverse sqrt is enlightening on computing
this really fast.

See:

http://en.wikipedia.org/wiki/Fast_inverse_square_root

This has little to do with whether an integer or floating point value is
better algorithmically.
                            - Jim