"primes-utils" is a Rubygem which provides a suite of extremely fast
(relative to Ruby's standard library) utility methods for testing and
generating primes.
Install it the usual way:
$ gem install primes-utils
Then require inside ruby as:
> require 'primes/utils'
The suite consists of the following methods:
1)prime?
Determine if the absolute value of an integer is prime. Return 'true' or
'false'.
This replaces the `prime?` method in the `prime.rb` standard library.
2)primemr?(k=20)
Determine if the absolute value of an integer is prime using Miller-Rabin test.
Return 'true' or 'false'.
Miller-Rabin here is super fast, but probabilistic (not deterministic),
primality test.https://en.wikipedia.org/wiki/Miller-Rabin_primality_test
The method's reliability can be increased by increasing the default input
parameter of k=20.
3)factors(p=13) or prime_division(p=13)
Determine the prime factorization of the absolute value of an integer.
This replaces the `prime division` method in the `prime.rb` standard library.
Returns an array of arrays of factors and exponents: [[2,4],[3,2],[5,1]] =>
(2^4)(3^2)(5^1) = (16)(9)(5) = 720
Default Strictly Prime (SP) Prime Generator (PG) used here is P13.
Can change SP PG used on input. Acceptable primes range (3 - 19).
4)primes(start_num=0)
Create an array of primes from the absolute value range (|start_num| -
|end_num|).
The order of the range doesn't matter if both given: start.primes end <=>
end.prime start
If only one parameter used, then all the primes upto that number will be
returned.
5)primenth(p=11) or nthprime(p=11)
Return the value of the nth (absolute value) prime.
Default Strictly Prime (SP) Prime Generator (PG) used here is P11.
Can change SP PG used on input. Acceptable primes range (3 - 19).
Coding Implementations
The methods `primemr`, `nthprime/primenth`, and `primes` are coded in
pure ruby. The methods `prime?` and `prime_division/factors` have two
implementations. Each has a pure ruby implementation, and also a hybrid
implementation which uses the Unix cli command `factor` if its available
on the host OS. `factor` [5] is an extremely fast C coded factoring
algorithm, part of the GNU Core Utilities package [4].
Upon loading, the gem tests if the desired `factor` command exists on
the host OS. If so, it wraps a system call to it and uses it for
`prime?` and `prime_division/factors`. If not, it uses a fast pure ruby
implementation for each method based on the Sieve of Zakiya (SoZ)[1][2][3].
References
[1]https://www.scribd.com/doc/150217723/Improved-Prim...
<https://www.scribd.com/doc/150217723/Improved-Primality-Testing-and-Factorization-in-Ruby-revised>
[2]https://www.scribd.com/doc/228155369/The-Segmented...
<https://www.scribd.com/doc/228155369/The-Segmented-Sieve-of-Zakiya-SSoZ>
[3]https://www.scribd.com/doc/73385696/The-Sieve-of-Zakiya
[4]https://en.wikipedia.org/wiki/GNU_Core_Utilities
[5]https://en.wikipedia.org/wiki/Factor_(Unix)
Author
Jabari Zakiya
--
You received this message because you are subscribed to the Google Groups "Ruby
on Rails: Talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to rubyonrails-talk+unsubscr...@googlegroups.com.
To post to this group, send email to rubyonrails-talk@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/rubyonrails-talk/bdd01744-c04d-4cd3-b813-a3a2b1fc46b6%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
