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

Groups > comp.programming > #268

Re: integer division algorithm

Show all headers | View raw

robin wrote:
) "zephyrtronium" <zephyrtronium@gmail.com> wrote in message 
) news:215653aa-defb-4f81-bba4-9e8a2845b13e@hg8g2000vbb.googlegroups.com...
)|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.
)
) Since it makes two calls on log2, how does this help?

It doesn't make those two calls.  Check the code below.

) Wouldn't it be slower than conventional long-hand division?

It's almost but not quite exactly like long-hand division.

)| 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.
)|
)| Anyone know anything about this? Existing (optimized) implementations,
)| complexity, et cetera? 


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

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