Messages in this thread |  | | From | "Alexander van Heukelum" <> | Subject | Re: [PATCH] x86: generic versions of find_first_(zero_)bit, convert i386 | Date | Mon, 07 Apr 2008 12:25:50 +0200 |
| |
On Sun, 6 Apr 2008 13:22:58 -0700 (PDT), "dean gaudet" <dean@arctic.org> said: > On Sun, 6 Apr 2008, Alexander van Heukelum wrote: > > > The current generic implementation of ffz is O(lg(n)) already > > it's O(lg(n)) time... the operations all depend on each other. > > the implementation i pointed to is O(lg(n)) code space... and the time > depends on how parallel the machine is, they're not dependent on each > other.
Indeed. The worst dependencies are in the sum of all the partial results in this implementation. And addition is associative, so partial results can be written as ((a+b)+(c+d))+(e+f). Assuming perfect parallel execution this would lead to O(ln(ln(n))). Good.
Care to implement ffs and __ffs like this?
Greetings, Alexander
> -dean -- Alexander van Heukelum heukelum@fastmail.fm
-- http://www.fastmail.fm - The professional email service
|  |