CODEWITHSUNDEEP
mathmatlabtime-complexity
Matt Lab
Matt Lab

Reputation: 89

Time complexity of modular arithmetic

Say I wanted to calculate a (mod n). What is the time complexity of this? I'm using Matlab, and am not sure how Matlab calculates it. Does it divide a by n, subtract the integer part, and then multiply by n?

Does it make sense to ask 'what is the time complexity of this'?

Upvotes: 4

Views: 3587

Answers (2)

Niclas
Niclas

Reputation: 1230

According to the built in help Matlab calculates MOD(x,y) as:

MOD(x,y) = x - floor(x./y).*y

where the floor function rounds towards minus infinity (that is strips the decimal part).

Runtime will be constant as long as you don't calculate mod(X, y) where X is a vector, in that case it will scale linearly with the number of elements in the vector

Upvotes: 0

amit kumar
amit kumar

Reputation: 21032

It makes sense to ask about the time complexity for long numbers a and/or n. The related field is called Computational Number Theory. For example, see this book.

The usual integer arithmetic, which most likely is used by Matlab, is an ALU operation (or multiple operations) performed in a constant time. In this case, one has to remember that the size of the integer is restricted.

Upvotes: 2

Related Questions