All geek questions in one place

Time complexity of modular arithmetic

Say I wanted to compute (mod n). What is the time complexity of this? I use Matlab, and don't know how this calculates Matlab. Does it divide by n, subtract the integer part, and then multiply by n?

Does it make sense to ask: "What is the time complexity of this?"

+4
source share
2 answers

It makes sense to ask about time complexity for long numbers a and / or n . A related field is called computational number theory. For example, see this book .

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

+2
source

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

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

where the gender function is rounded to minus infinity (i.e. it splits the decimal part).

Runtime will be constant until you calculate mod (X, y), where X is a vector, in which case it will scale linearly with the number of elements in the vector

0
source

Source: https://habr.com/ru/post/1390248/

More articles:


All Articles