Subj : Re: faster approach to division
To   : comp.programming
From : Willem
Date : Tue Jul 12 2005 11:50 pm

Willem wrote:
) Mark wrote:
) ) I assume then that the divisor was known to you at compile time.  My 
) ) situation is more like: x / f(...) where f(...) will always return +/-1 
) ) or +/-2, determined at run time.
)
) *always* ?
)
) In that case, I guess you can come up with something faster,
) but you need to think beyond 'if' statements.
)
) there may be some bit twiddling trick.

For example, in C:
  result = value >> (divisor - 1);
Will work for division by 1 and 2.

And:
  result = (value >> ((divisor - 1) & 1)) * ((divisor >> 2) | 1);
Will work for division by +1, +2, -1 and -1.

I'm not sure I worked it out correctly, nor am I sure these are the fastest
methods, and I'm not even entirely sure it will beat straight division,
but it should at least give you an idea what you could try.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.