Messages in this thread | | | Date | Wed, 16 Jul 2008 14:35:56 -0700 (PDT) | From | Soumyadip Das Mahapatra <> | Subject | Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c |
| |
> From: Peter Zijlstra <peterz@infradead.org>
> To: Soumyadip Das Mahapatra <soumya.linux@yahoo.com> > Cc: linux-kernel@vger.kernel.org > Sent: Thursday, July 17, 2008 2:21:09 AM > Subject: Re: [PATCH] : A better approach to compute int_sqrt in lib/int_sqrt.c > > On Wed, 2008-07-16 at 13:19 -0700, Soumyadip Das Mahapatra wrote: > > Hello everybody !! > > The patch below is what i think is a better approach to > > compute int_sqrt(). > > > > What about it ? > > Indeed, what about it? > > How is it better; > - is it cheaper > - how so > - on what platform > > - it is more accurate > - who needs it > > Please provide a little more information about why you suggest this > change. > > > Thanks !! > > > > --- > > --- a/lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 > > +++ b/lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 > > @@ -1,4 +1,3 @@ > > - > > #include > > #include > > > > @@ -7,26 +6,21 @@ > > * @x: integer of which to calculate the sqrt > > * > > * A very rough approximation to the sqrt() function. > > + * Improved version from the previous one. > > With the previuos one being gone, this comment adds little but > confusion.. > > > */ > > unsigned long int_sqrt(unsigned long x) > > { > > - unsigned long op, res, one; > > - > > - op = x; > > - res = 0; > > - > > - one = 1UL << (BITS_PER_LONG - 2); > > - while (one > op) > > - one >>= 2; > > - > > - while (one != 0) { > > - if (op >= res + one) { > > - op = op - (res + one); > > - res = res + 2 * one; > > - } > > - res /= 2; > > - one /= 4; > > - } > > - return res; > > + unsigned long ub, lb, m; > > + lb = 1; /* lower bound */ > > + ub = (x >> 5) + 8; /* upper bound */ > > + do { > > + m = (ub + lb) >> 1; /* middle value */ > > + if((m * m) > x) > > + ub = m - 1; > > + else > > + lb = m + 1; > > + } while(ub >= lb); > > + > > + return lb - 1; > > } > > EXPORT_SYMBOL(int_sqrt); > >
Thanks Peter for noticing :-) Sorry, I should have it explained before. Really sorry for that. Here are they...
0 It is better because o it uses only one loop instead of two o contains no division operator (older version has two) which are surely comparatively slow task in computer
0 Currently find . -name '*.[ch]' | xargs grep int_sqrt gives me this .... ./fs/nfs/write.c: nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10); ./drivers/video/fbmon.c: h_period = int_sqrt(h_period); ./mm/page_alloc.c: min_free_kbytes = int_sqrt(lowmem_kbytes * 16); ./mm/oom_kill.c: s = int_sqrt(cpu_time); ./mm/oom_kill.c: s = int_sqrt(int_sqrt(run_time)); .... So this function works in critical computing sections like frame-buffer, paging. Which means betterment of this function should not be ignored. Besides, if there is a better way to do things then why should not we do that ?
Anyways thanks :-)
| |