README.md in congruence_solver-0.4.0 vs README.md in congruence_solver-0.5.0
- old
+ new
@@ -2,11 +2,11 @@
CongruenceSolver is a gem for solving polynomial congruences. Should you ever need to solve polynomial congruences, this is the gem for you!
## Polynomial Congruences
-Polynomial congruences are the central topic of most elementary number theory and abstract algebra curricula. Similar to an equation, a [congruence](https://en.wikipedia.org/wiki/Modular_equation) is an [equivalence relation](https://en.wikipedia.org/wiki/Equivalence_relation) arising from [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic) (also knowsn as "clock arithmetic"). For example, the idea "5 hours past 8 is 1" is expressed in the congruence ```8 + 5 = 1 mod 12```. A polynomial congruence is simply a congruence involving a polynomial, like ```x + 5 = 1 mod 12```. The problem of solving a congruence is to find all inputs satisfying the congruence, much like solving an equation (in this case, ```x = 8```). Generally speaking, congruences become more difficult to solve as the degree of the polynomial and the modulus grow. Elementary number theory develops tools like [Hensel Lifting](https://en.wikipedia.org/wiki/Hensel%27s_lemma#Hensel_Lifting) for solving polynomial congruences and the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) for solving systems of polynomial congruences. This gem leverages these methods as implemented in C in [congruence_solver_ext](https://github.com/laneb/congruence_solver_ext).
+Polynomial congruences are the central topic of most elementary number theory and abstract algebra curricula. Similar to an equation, a [congruence](https://en.wikipedia.org/wiki/Modular_equation) is an [equivalence relation](https://en.wikipedia.org/wiki/Equivalence_relation) arising from [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic) (also knowsn as "clock arithmetic"). For example, the idea "5 hours past 8 is 1" is expressed in the congruence ```8 + 5 = 1 mod 12```. A polynomial congruence is simply a congruence involving a polynomial, like ```x + 5 = 1 mod 12```. The problem of solving a congruence is to find all inputs satisfying the congruence, much like solving an equation (in this case, ```x = 8```). Generally speaking, congruences become more difficult to solve as the degree of the polynomial and the modulus grow. Elementary number theory develops tools like [Hensel Lifting](https://en.wikipedia.org/wiki/Hensel%27s_lemma#Hensel_Lifting) for solving polynomial congruences and the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) for solving systems of polynomial congruences. This gem leverages these methods as implemented in C in [congruence_solver](https://github.com/laneb/congruence_solver).
## Installation
With [RubyGems](https://rubygems.org/) on your machine, installation is as easy as
```shell
@@ -39,9 +39,13 @@
#solve -3x^5 - x^3 + x^2 + 2x + 1 = 0 mod 49
coeffs = [1, 2, 1, 1, 0, 3]
mod = 49
CongruenceSolver.solve_congruence(coeffs, mod).sort #=> [1, 8, 15, 22, 26, 29, 36, 43]
```
+
+## Limitations
+
+What are the limitations on the size of the numbers, you ask? CongruenceSolver can solve any congruence with a 16 bit degree that 32 bit coefficients and modulus. Of course, Ruby's Bignum can manage arbitrarily large integers without overflow, but the extension that powers has limitations to maintain speed and simplicity.
## Development
First, install bundler (`gem install bundler`). Then install this project's dependencies with `bundle install`. Use `bundle exec rake update_ext` to pull and compile the extension. Use `bundle exec rake spec` to run the tests and `bundle exec rake bench` to run the benchmark. To build and install this gem locally, run `bundle exec rake install`.