How to realize mod function using combinatorial logic?

[sree205]

Hi all,
is there anyway modulus functionality ( a%b) can be realized using combinatorial logic ? i think its possible using repeated subtraction, but, for that to be realized, it takes lots of clock cycles. any other alternatives ?

 

[dbshailesh]

mod function

Hi Sree205,
I think it is possible using the some division algorithms.So to save multiple clocks you have to give up some silicon area.

There are various ways of defining a remainder, and computers and calculators have various ways of storing and representing numbers, so what exactly constitutes the result of a modulo operation depends on the programming language and/or the underlying hardware.

a modulo 0 is undefined in the majority of systems, although some do define it to be a. If the definition is consistent with the division algorithm, then n = 0 implies , which is a contradiction (i.e., the usual remainder does not exist in this case).

The remainder can be calculated by using equations, in terms of other functions. Differences may arise according to the scope of the variables, which in common implementations is broader than in the definition just given. One useful equation for calculating the remainder r is


where is the floor function of x. See e.g. [1], [2], [3].

Raymond T. Boute [1] analyses several definitions of integer division and modulo, and he introduces the “Euclidean” definition. Let q be the integer quotient of a and n, then:


Two corrolaries are that


As described by Leijen, [2]

Boute argues that Euclidean division is superior to the other ones in terms of regularity and useful mathematical properties, although floored division, promoted by Knuth, is also a good definition. Despite its widespread use, truncated division is shown to be inferior to the other definitions.

Modulo operation expression
Some calculators have a mod() function button, and many programming languages have a mod() function or similar, expressed as mod(a,n), for example. Some also support expressions that use "%", "mod", or "Mod" as a modulo operator, such as

a % n
or

a mod n
both of which are read as "a modulo n" when spoken aloud.

Performance issues
Modulo operations might be implemented such that division with remainder is calculated each time. For real-time computer software this can be slower than alternatives, for special cases. For example, the modulus of powers of 2 can alternatively be expressed as a bitwise AND operation:

x % 2^n == x & (2^n - 1)
Further examples:

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7
In devices and software that implement bitwise operations more efficiently than modulo, this can result in faster calculations.

Modulo — many uses of the word "modulo", all of which grew out of Carl F. Gauss's introduction of modular arithmetic in 1801.
Modular arithmetic

Note 1: The semantics of the modulo operator in Perl are defined to be those of the modulo operator of the C compiler that was used to compile the Perl interpreter itself.
Note 2: Mathematically, these two choices are but two of the infinite number of choices available for the inequality satisfied by a remainder.

 

[ankit12345]

mod function

How many bits u want to design??

For smaller no of bits up to 4......take a truthtable and find the equation and impliment.

For higher no of bits.......we have to use clock else u will end up with big ckt

 

[sree205]

mod function

this is what i'm looking for. if i've two numbers, a and b, both of which are huge, lets say, have 20 digits each in decimals, and i've to calculate a % b, how do i proceed ?

 

[ankit12345]

mod function

ru ready to use clock?????

else its not going to get implementer coz of its size...

u have to use a loop with clock to realise........

else u can simulate and synthesis but u cant fabricate it........

 

[sree205]

Re: mod function

if a design of such proportion is going to be implemented in a clocked process, assuming its subracting the smaller number from the bigger number, it could still take a lot of cycles to get a remainder.
i just wanted to circumvent it .

 

[dbshailesh]

mod function

In this data sync.. issue will deffinitely come into picture,because you wanted to design a Combo design.Make all the division to occur parallely.

You have to go for parallel computing algorithms.
Many algorithms are there,for example to speed up the multiplication you can use BOOThs algorithm,like this you can use other algorithms,but gate count will enormously increase.

 

[mnfsoft]

Hi all,
is there anyway modulus functionality ( a%b) can be realized using combinatorial logic ? i think its possible using repeated subtraction, but, for that to be realized, it takes lots of clock cycles. any other alternatives ?

Here are two files specifying how the whole division is expressed! with precision point to unconditional length

P.S. It may need to be much more specified but at short this would do!

- - - Updated - - -

Here is the whole division with decimal precision (the decimal point is not specified) in block diagram but it is a rough sketch

 

[mnfsoft]

Multiplcation using Combinational Logic

this is the Multiplcation operation using Combinational Logic in block diagram