direct calculation of the modulus ?

Hi,

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

Thanks in advance.

Mete

Reply to
mete
Loading thread data ...

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.

Reply to
Tuukka Toivonen

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

Reply to
glen herrmannsfeldt

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

Regards, Allan

Reply to
Allan Herriman

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

Reply to
Shankar B

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)

Reply to
John

[snip]

You might be interested in this thread:

formatting link
which discusses a combinatorial circuit for evaluating a ten bit number mod 3 in a single CLB.

Regards, Allan

Reply to
Allan Herriman

formatting link

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,

Reply to
Marlboro

I wrote:

formatting link

Thanks Allan, I shoulda googled first

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 0, let N
Reply to
John

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

Mete

Reply to
mete

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.