mod function

EDAboard.com Forum Index -> ASIC Design Methodologies & Tools (Digital) -> mod function

Author

Message

sree205

Joined: 13 Mar 2006
Posts: 421
Helped: 30

13 Feb 2007 11:45 mod function

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

Joined: 13 Feb 2007
Posts: 8
Location: Bangalore

13 Feb 2007 12:04 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 ﬂoored division, promoted by Knuth, is also a good deﬁnition. Despite its widespread use, truncated division is shown to be inferior to the other deﬁnitions.

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.

Last edited by dbshailesh on 13 Feb 2007 12:53; edited 1 time in total

ankit12345

Joined: 27 Dec 2005
Posts: 292
Helped: 6
Location: bangalore,India

13 Feb 2007 12:22 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

Joined: 13 Mar 2006
Posts: 421
Helped: 30

13 Feb 2007 12:38 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 ?

Google
AdSense
Google Adsense

13 Feb 2007 12:38 Ads

ankit12345

Joined: 27 Dec 2005
Posts: 292
Helped: 6
Location: bangalore,India

13 Feb 2007 13:18 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

Joined: 13 Mar 2006
Posts: 421
Helped: 30

13 Feb 2007 14:58 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

Joined: 13 Feb 2007
Posts: 8
Location: Bangalore

19 Feb 2007 13:14 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.