[ANN] "primes-utils" rubygem

“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 conists 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-Primality-Testing-and-Factorization-in-Ruby-revised
[2]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

Jabari Z. wrote in post #1171443:

“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'

Version 2.1.0 now available.

Added new methods primesf, primesmr, primescnt, primescntf, primescntmr.
All methods significantly faster, more memory efficient, and can work
with larger numbers.

https://rubygems.org/gems/primes-utils

https://github.com/jzakiya/primes-utils

Friday, June 19, 2015
Now available, primes-utils 2.2.0, the Juneteenth release:
(https://en.wikipedia.org/wiki/Juneteenth).

New in 2.2.0
Refactored methods primes, primescnt, primenth|nthprime.

Changed default PGs on some methods to significantly increase speed.

Implemented mem error handling for primes, primescnt, primenth to
gracefully fail with informative error messages.

Upon failure methods return nil value.

Increased to 1.6 billion, indexed nth primes used in primenth to
create ranges to find nth prime within, extending max possible nth
prime.

Removed max nth prime ceiling. Only limitations now are available memory
and time.

Upon loading with Ruby 1.8 require 'rubygems' is invoked to enable
installing gems.

Friday, October 23, 2015

Now available, primes-utils 2.4.0

New in 2.4.0
Fixed edge case algorithm error affecting primes, primescnt, and
primenth|nthprime with better, faster algorithm and code.

More code DRYing and cleanups.

Additional out-of-memory error message added to primes.

Further progress on PRIMES-UTILS HANDBOOK, almost done.

Wednesday, July 1, 2015

Now available, primes-utils 2.3.0

New in 2.3.0
primescnt can now find count of primes upto some N much faster and for
larger numbers.

Increased to over 2 billionth, indexed nth primes used in primenth,
and now primescnt, to create ranges to find nth prime within,
extending
max possible nth prime.

Under the hood, more code DRYing, cleanups, refactoring, and added
capability to one private method.

Further progress on Prime-Utils Handbook.

Wednesday, December 2, 2015

Now available, primes-utils 2.5.0

New in 2.5.0
Better adaptive Prime Generator selection algorithm creates speed
increases for large ranges for methods primes, primescnt,
andprimenth|nthprime.

More code DRYing and cleanups.

Finally, now available for reading and FREE download:

PRIMES-UTILS HANDBOOK: The Math and Code behind making the Rubygem

https://www.scribd.com/doc/266461408/Primes-Utils-Handbook

Monday, December 14, 2015

Now available, primes-utils 2.6.0

New in 2.6.0
Much, much better adaptive Prime Generator selection algorithm now used.
Significant speed increases across most start values and range sizes for
methods primes, primescnt, andprimenth|nthprime.

Code, and changes, documented in current HANDBOOK ver 2015/12/14.
Available for reading and FREE download:

PRIMES-UTILS HANDBOOK: The Math and Code behind making the Rubygem

https://www.scribd.com/doc/266461408/Primes-Utils-Handbook

Hi, for large unique integer, you should use (propose) the deterministic
AKS primality test instead of the undeterministic Miller-Rabin test (AKS
is just a smarter version of Miller-Rabin, not much more code)

Hi,

I’ve been aware of AKS since it was published, but everything I’ve read
said it’s coded implementation is slow compared to other algorithms.
See from Wikipedia below:

“While the algorithm is of immense theoretical importance, it is not
used in practice. For 64-bit inputs, the Baillie–PSW is deterministic
and runs many orders of magnitude faster. For larger inputs, the
performance of the (also unconditionally correct) ECPP and APR tests is
far superior to AKS. Additionally, ECPP can output a primality
certificate that allows independent and rapid verification of the
results, which is not possible with the AKS algorithm.”

I’ve seen some C/C++ implementations, but haven’t bothered to run or
translate them into Ruby.

Have you attempted to run any coded implementation of AKS? and if so
what has been its relative performance?

Do you know of a Ruby implementation of AKS?

Jabari

Heads up for your document.

People like me who are math noobs really appreciate easy to read
documentation (Disclaimer: I have not yet read it so I can not
accurately judge as of now).

My only complaint has to do with scribd.com itself - I seem to need to
have to either register specifically or have a facebook account.

Do you think you could perhaps either consider adding the .pdf itself,
size-optimized, to your gem such as in a doc/ subdirectory OR add a
second gem that will be synced automatically called “prime-utils-doc” or
something like that ?

It’s no big deal I assume, feel free to disregard it, just was an idea I
had right now.

Cheers!

Monday, December 28, 2015

Now available, primes-utils 2.7.0

New in 2.7.0
Better adaptive selection algorithm to select PGs within a range.

Code, and changes, documented in current HANDBOOK ver 2015/12/19.
Available for reading and FREE download:

PRIMES-UTILS HANDBOOK: The Math and Code behind making the Rubygem

https://www.scribd.com/doc/266461408/Primes-Utils-Handbook

Hi Robert,

You should be able to click the scribd link and go right to the document
on scribd and read it there and/or download, for FREE.

I haven’t heard of anyone else not being able to access it, unless
scribd has changed its access policy. Try clicking the link again and
let me know exactly what it say, or does. Also, try the link on the
github.com page.

https://github.com/jzakiya/primes-utils

Here is another link for the paper on my 4shared site. There shouldn’t
be any problems with it. You can also see all my other papers I’ve
written too, that are referenced in the HANDBOOK. Again, let me know if
you have any problems.

https://www.4shared.com/web/preview/pdf/U08GamRMce?

Jabari

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs