Efficient Algorithm for Calculating f(x)modg(x) with Large Degrees

Thread starter smslca
Start date Jan 2, 2012

In summary, calculating f(x)modg(x) involves finding the remainder when f(x) is divided by g(x). This is useful in various mathematical and scientific applications and can be done using the modulo operator. It is possible for f(x)modg(x) to be negative, depending on the signs of f(x) and g(x). However, there are limitations to this calculation, such as g(x) not being equal to 0 and potential overflow errors. This is different from f(x)/g(x) which gives the quotient instead of the remainder and can result in a decimal or fraction.

Jan 2, 2012

smslca

I like to know

what is best known efficient algorithm to calculate f(x)modg(x) , in which the degrees of f(x) and g(x) are very very very large , and degree of f(x) >> degree of g(x).

Last edited: Jan 3, 2012

Physics news on Phys.org

Jan 10, 2012

Stephen Tashi

Science Advisor

f and g are polynomials with integer coefficients? You know how to divide one polynomial into another, right?

Related to Efficient Algorithm for Calculating f(x)modg(x) with Large Degrees

1. What is the purpose of calculating f(x)modg(x)?

The purpose of calculating f(x)modg(x) is to find the remainder when f(x) is divided by g(x). This can be useful in various mathematical and scientific applications, such as finding recurring patterns or solving equations.

2. How do I calculate f(x)modg(x)?

To calculate f(x)modg(x), you can use the modulo operator (%). Simply divide f(x) by g(x) and the remainder is the result of f(x)modg(x). For example, if f(x) = 10 and g(x) = 3, then f(x)modg(x) = 1 (10 divided by 3 has a remainder of 1).

3. Can f(x)modg(x) be negative?

Yes, f(x)modg(x) can be negative. The result will depend on the signs of f(x) and g(x). If both f(x) and g(x) are negative, then f(x)modg(x) will also be negative. If either f(x) or g(x) is positive, then f(x)modg(x) will be positive.

4. Are there any limitations to calculating f(x)modg(x)?

Yes, there are some limitations to calculating f(x)modg(x). The most common limitation is that g(x) cannot be equal to 0, as division by 0 is undefined. Additionally, if g(x) is a very large number, it may result in an overflow error.

5. How is f(x)modg(x) different from f(x)/g(x)?

The main difference between f(x)modg(x) and f(x)/g(x) is that the former gives the remainder when f(x) is divided by g(x), while the latter gives the quotient. Additionally, f(x)modg(x) will always result in an integer, while f(x)/g(x) can result in a decimal or fraction.