Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #265

Re: integer division algorithm

Followups directed to: comp.programming

Show all headers | View raw

zephyrtronium wrote:

> I invented an algorithm thingy for division of integers based on the
> identity n/d = 2**(lg(n/d)) = 2**(lg(n) - lg(d)). It seems too obvious
> to me not to be a reinvention, but I can't find any implementations of
> it, so I was wondering whether anyone here might have any more info.
> 
> In C-like pseudocode:
> // n starts as the numerator and d the denominator.
> // lb(x) = 1 + [[log2(x)]], the position of the highest bit of x.
> // Assume n >= 0, d > 0.
> q = 0; // quotient
> while (n >= d)
> {
>   log_diff = lb(n) - lb(d);
>   c = d << log_diff; // temp
>   if (c > n) { c >>= 1; log_diff--; } // This occurs when the
> fractional part of log2(d) > that of log2(n).
>   n -= c;
>   q += 1 << log_diff;
> }
> // q now contains the quotient and n the remainder.
> 
> I'm not exactly sure what the complexity of this is, but some examples
> I've tried include twelve iterations for 183346819/45, five for
> 168937/251, and eight for 1662263/61. If n is a power of two multiple
> of d, it takes one iteration.

Looks like the classical algorithm for long division in binary: Per each 
iteration you extract a non-zero digit (i.e., 1) of the quotient, and you 
use the logarithm part to know where to put it (q += 1 << log_diff). On 
paper, that is taken care of by proper alignment of the numbers.

> Anyone know anything about this? Existing (optimized) implementations,
> complexity, et cetera?

I think, Knuth has a discussion of the complexity for the classical 
algorithms in volume 2.


Best,

Kai-Uwe Bux

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

integer division algorithm zephyrtronium <zephyrtronium@gmail.com> - 2011-05-02 15:04 -0700
  Re: integer division algorithm Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-05-03 02:21 +0200
  Re: integer division algorithm "robin" <robin51@dodo.mapson.com.au> - 2011-05-05 00:29 +1000
    Re: integer division algorithm Willem <willem@toad.stack.nl> - 2011-05-04 14:36 +0000
      Re: integer division algorithm "robin" <robin51@dodo.mapson.com.au> - 2011-05-05 10:52 +1000
        Re: integer division algorithm zephyrtronium <zephyrtronium@gmail.com> - 2011-05-04 18:50 -0700
          Re: integer division algorithm "robin" <robin51@dodo.mapson.com.au> - 2011-05-07 23:53 +1000
  Re: integer division algorithm pete <pfiland@mindspring.com> - 2011-05-05 02:41 -0400

csiph-web