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

Groups > comp.programming > #263 > unrolled thread

integer division algorithm

Back to article view | Back to comp.programming

Contents

  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

#263 — integer division algorithm

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.

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

[toc] | [next] | [standalone]

#265

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

[toc] | [prev] | [next] | [standalone]

#267

"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?
Wouldn't it be slower than conventional 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? 

[toc] | [prev] | [next] | [standalone]

#268

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

[toc] | [prev] | [next] | [standalone]

#270

"Willem" <willem@toad.stack.nl> wrote in message news:slrnis2p3u.2ti9.willem@toad.stack.nl...
| 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.

lb(n) - lb(d)   makes two calls on log2, as   lb(x) = 1 + [[log2(x)]]

| ) 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? 

[toc] | [prev] | [next] | [standalone]

#271

On May 4, 8:52 pm, "robin" <robi...@dodo.mapson.com.au> wrote:
> "Willem" <wil...@toad.stack.nl> wrote in messagenews:slrnis2p3u.2ti9.willem@toad.stack.nl...
> | robin wrote:
>
> | ) "zephyrtronium" <zephyrtron...@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.
>
> lb(n) - lb(d)   makes two calls on log2, as   lb(x) = 1 + [[log2(x)]]

It's trivial to remember (or find) the position of the highest set
bit, which is the alternative definition of lb(x) here. If the exact
value of the logarithm were being calculated, there would be little
point in the rest of the algorithm.

Thanks for the responses.

[toc] | [prev] | [next] | [standalone]

#279

"zephyrtronium" <zephyrtronium@gmail.com> wrote in message 
news:e2242be4-ebf2-4ef9-be2b-70d56e57edc4@y31g2000vbp.googlegroups.com...
~On May 4, 8:52 pm, "robin" <robi...@dodo.mapson.com.au> wrote:
~> "Willem" <wil...@toad.stack.nl> wrote in messagenews:slrnis2p3u.2ti9.willem@toad.stack.nl...
~> | robin wrote:
~>
~> | ) "zephyrtronium" <zephyrtron...@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.
~>
~> lb(n) - lb(d) makes two calls on log2, as lb(x) = 1 + [[log2(x)]]

~It's trivial to remember (or find) the position of the highest set
~bit,

It is? If you are using machine code on a machine that provides
the position of the most-significant bit, it is.
But if not, it's necessary to do a linear search (maximum typically 32 iterations);
alternatively, table lookups for each byte.
The first takes time, and one wonders that the complete algorithm
is not going to be slower than traditional long division.
The second method is faster, but requires time and care to establish the lookup tables.

~ which is the alternative definition of lb(x) here. If the exact
~value of the logarithm were being calculated, there would be little
~point in the rest of the algorithm. 

[toc] | [prev] | [next] | [standalone]

#272

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.

http://en.wikipedia.org/wiki/Slide_rule

-- 
pete

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web