direct calculation of the modulus ?

Hi,

Is there method that is more efficient than regular division for
calculating modulus ?

Thanks in advance.

Mete

In article <acc68109.0410120613.6e669b1b@posting.google.com>, mete wrote:
> Is there method that is more efficient than regular division for
> calculating modulus ?

Depends on the modulus. For example, if you want to calculate
	x mod 2^4
you can just take take the four lowest bits and set the rest
to zero. For more complex or non-fixed moduli it's more difficult.

mete wrote:

> Is there method that is more efficient than regular division for
> calculating modulus ?

For specific input base and modulus there is usually an
efficient way.  For decimal input and modulus of 3 or 9,
you can add the digits together, and take the modulus of
the sum.  For binary input there are even more rules, but
the modulus must be known in advance.  If the modulus
is variable, I don't know of a general formula.

-- glen

On Tue, 12 Oct 2004 11:39:10 -0700, glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>
>
>mete wrote:
>
>> Is there method that is more efficient than regular division for
>> calculating modulus ?
>
>For specific input base and modulus there is usually an
>efficient way.  For decimal input and modulus of 3 or 9,
>you can add the digits together, and take the modulus of
>the sum.  For binary input there are even more rules, but
>the modulus must be known in advance.

In particular, if the divisor is 2^N +/- 1, there are significant
simplifications.

Regards,
Allan

> >mete wrote:
> >
> >> Is there method that is more efficient than regular division for
> >> calculating modulus ?

Well, it depends on what your divisor for the modulus operation is. If
you are looking at some small values of divisor, then you can do
something of this sort :

1. Start with modulus m = 0.
2. Take one bit at a time starting from the most significant bit.
3. Have one state for every modulus value (0..n-1, if you are doing
modulo n).
4. Have a state diagram with the following transitions. If input is
`1', then go to m = (2*m+1) mod n. If current input is `0' go to m =
(2*m) mod n state.
5. You will have n states with 2n transitions. Run your dividend
through this machine.
6. This is generic and well suited for small values of n.

Of course, if you need a combinational implementation, or if you have
special values of n, or if the operation needs to be signed, then the
whole ballgame is different.

Hope this helps.
--shankar

shankar.sb@gmail.com (Shankar B) wrote in message news:<b1296d94.0410132245.200a7019@posting.google.com>...
> > >mete wrote:
> > >
> > >> Is there method that is more efficient than regular division for
> > >> calculating modulus ?
> 
> Well, it depends on what your divisor for the modulus operation is. If
> you are looking at some small values of divisor, then you can do
> something of this sort :
> 
> 1. Start with modulus m = 0.
> 2. Take one bit at a time starting from the most significant bit.
> 3. Have one state for every modulus value (0..n-1, if you are doing
> modulo n).
> 4. Have a state diagram with the following transitions. If input is
> `1', then go to m = (2*m+1) mod n. If current input is `0' go to m =
> (2*m) mod n state.
> 5. You will have n states with 2n transitions. Run your dividend
> through this machine.
> 6. This is generic and well suited for small values of n.
> 
> Of course, if you need a combinational implementation, or if you have
> special values of n, or if the operation needs to be signed, then the
> whole ballgame is different.
> 
> Hope this helps.
> --shankar

This one sounds neat, here's a first cut at a combinatorial
implementation.
Modulus distributes over addition, i.e., MODn(A+B) = MODn( MODn(A) +
MODn(B) )
So the input value, I, can be partitioned into 4-bit groups, each of
which
feeds an array of 4-LUTs. Array A produces modulus for bits (4*i ..
4*i+3).
For large values of n, the low order bits that sum to less than n
don't need
to pass through LUTs. Sum the results from each array. If n and I are
large, this first stage will put you a lot closer to the final result.
Repeat as
necessary till result is guaranteed less than 2*n, then subtract n if
result is >= n.

How long is necessary? Take an example. Assume I is 48 bits, and n is
13 bits.
In the first stage, the lower 12 bits of I can be passed through to
the
addition, and the remaining 36 bits produce 9 more addends. The result
is at
most 10*(n-1), having at most 13+4 = 17 bits. Repeat the process, pass
lower
12 bits, and two LUT arrays convert the remaining 5 bits, giving 3
addends
with a result that is at most 3*(n-1). Last stage gives result F that
is at
most 2*(n-1), which can be compared to n to determine if a final
subtraction
is required (carry logic does comparision, LUT logic selects F or
(F-n) based
on carry result). Still requires 13 additions (= 9 + 2 + 1 + 1), but
is
somewhat shorter than doing long division.

What sizes input and modulus is OP interested in? Is variable modulus
needed?

John (always interested in these type circuits)

On 14 Oct 2004 18:38:32 -0700, john.l.smith@titan.com (John) wrote:

>shankar.sb@gmail.com (Shankar B) wrote in message news:<b1296d94.0410132245.200a7019@posting.google.com>...
>> > >mete wrote:
>> > >
>> > >> Is there method that is more efficient than regular division for
>> > >> calculating modulus ?

[snip]

>John (always interested in these type circuits)

You might be interested in this thread:
http://groups.google.com/groups?threadm=18c289aa.0304230854.6897fb3b%40posting.google.com
which discusses a combinatorial circuit for evaluating a ten bit
number mod 3 in a single CLB.

Regards,
Allan

Allan Herriman <allan.herriman.hates.spam@ctam.com.au.invalid> wrote in message news:<55kum0lpfu23e8darsn23f8ugk8gookr5k@4ax.com>...
> On 14 Oct 2004 18:38:32 -0700, john.l.smith@titan.com (John) wrote:
> 
> >shankar.sb@gmail.com (Shankar B) wrote in message news:<b1296d94.0410132245.200a7019@posting.google.com>...
> >> > >mete wrote:
> >> > >
> >> > >> Is there method that is more efficient than regular division for
> >> > >> calculating modulus ?
> 
> [snip]
> 
> >John (always interested in these type circuits)
> 
> You might be interested in this thread:
> http://groups.google.com/groups?threadm=18c289aa.0304230854.6897fb3b%40posting.google.com
> which discusses a combinatorial circuit for evaluating a ten bit
> number mod 3 in a single CLB.
> 
> Regards,
> Allan

It's even simpler for mod 0, isn't it?  IHMO, ingeneral cases you
can't avoid the DIV operation or some agorithm similar to that,
cheers,

ccon67@netscape.net (Marlboro) wrote in message news:<e3fd5378.0410151004.4015287c@posting.google.com>...
> Allan Herriman <allan.herriman.hates.spam@ctam.com.au.invalid> wrote in > > >shankar.sb@gmail.com (Shankar B) wrote in message 
> > >> > >mete wrote:
> > >> > >> Is there method that is more efficient than regular division for
> > >> > >> calculating modulus ?
> > [snip]
I wrote:
> > >John (always interested in these type circuits)
> > 
> > You might be interested in this thread:
> > http://groups.google.com/groups?threadm=18c289aa.0304230854.6897fb3b%40posting.google.com
> > which discusses a combinatorial circuit for evaluating a ten bit
> > number mod 3 in a single CLB.

Thanks Allan, I shoulda googled first

> It's even simpler for mod 0, isn't it?  IHMO, ingeneral cases you
> can't avoid the DIV operation or some agorithm similar to that,
> cheers,
Reducto ab absurdum?
Here's the similar algorithm/circuit, as best I can work out this
morning... Shankar wrote me about my previous post, pointed out I was
a little incomplete in my explanation (sorry, it was late, it was
after a long day at work, and that post was the last thing I did
before heading home). The MAIN point is that mod distributes over
addition, and can be solved using distributed arithmetic.

Gory details (I waved my hands too much last post):

Some definitions:
B: Base for modulus
b: number of bits to represent B in binary
N: Number to take mod of
n: number of bits in N

Exclude special cases such as B = 2^k, 2^k - 1, 2^k + 1, which have
neat tricks that can be used, as Allan pointed out in previous mod
thread. When n is very large and b is somewhat large, mod(N,B) can be
generated (for fixed B) as follows:

1) Group the bits of N into a lower group, G0, consisting of b LSBs of
N, and a set of 4-bit upper groups to feed LUTs:
 L0, L1, ..., Lr, ..., LR
where R = ceil((n-b)/4) - 1. The top group, LR, may have <4 bits. 

2) Each of the upper groups, Lr, feeds an array of b LUTs to lookup
the values MOD(i*2^(4*r+b),B) for i = 0..15. Call the LUT outputs M0,
M1, ..., MR.

3) Sum: S = G0 + M0 + M1 + ... + MR.

The result S will be at most (R+2)*B, and will thus have at most
 b + ceil(log2(R+2)) bits.

4) If R > 0, let N <= S and repeat 1..3.
5) R = 0, subtract: F = S - B
6) If F is negative, MOD(N,B) = S, else MOD(N,B) = F

As usual, pipeline to taste.
Not quite as easy as 1,2,3, but a little easier than division. Hmmm.
Starting this exploration, I was thinking of arbitrary divisor; fixed
division can be approximated similarly to steps 2 and 3 (inverse
multiplication distributes over addition). So slightly worse than
division. But mod generally uses smaller adders at step 3). But
division ends at step 3). So it depends on definition of complexity,
more circuitry, or more levels...(Sorry to be talking to myself here,
just working it out). Hope no one was bored, I was annoyed at my
previous post for being fuzzy in the details!

Allan, I recall for 2^k - 1, break into k-bit groups, add, repeat as
req'd. How about 2^k + 1? I'm lazy after the above exposition.

Anyone care to speak to interesting H/W applications for mod?

Regards All,
John

Thank you all. This thread was very helpful...

Mete