Hi,
Is there method that is more efficient than regular division for calculating modulus ?
Thanks in advance.
Mete
Hi,
Is there method that is more efficient than regular division for calculating modulus ?
Thanks in advance.
Mete
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.
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
In particular, if the divisor is 2^N +/- 1, there are significant simplifications.
Regards, Allan
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 :
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)
[snip]
You might be interested in this thread:
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,
I wrote:
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 NThank you all. This thread was very helpful...
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.