ruby.git/lib/prime.rb, branch v3_0_4

[ruby/prime] v0.1.2

2020-12-09T05:45:56+00:00

[ruby/prime] Optimize `Integer#prime?`

2020-12-09T05:40:09+00:00

Miller Rabin algorithm can be used to test primality for integers smaller than a max value "MaxMR" (~3e24)

It can be much faster than previous implementation: ~100x faster for numbers with 13 digits, at least 5 orders of magnitude for even larger numbers (previous implementation is so slow that it requires more patience than I have for more precise estimate).

Miller Rabin test becomes faster than previous implementation at somewhere in the range 1e5-1e6. It seems that the range 62000..66000 is where Miller Rabin starts being always faster, so I picked 0xffff arbitrarily; before that, or above "MaxMR", the previous implementation remains.

I compared the `faster_prime` gem too. It is slower than previous implementation up to ~1e4. After that it becomes faster and faster compared to previous implementation, but is still slower than Miller Rabin starting at ~1e5 and up to MaxMR. Thus, after this commit, builtin `Integer#prime?` will be similar or faster than `faster_prime` up to "MaxMR".

Adapted from patch of Stephen Blackstone [Feature #16468]

Benchmark results and code: https://gist.github.com/marcandre/b263bdae488e76dabdda84daf73733b9

Co-authored-by: Stephen Blackstone

Improve docs for Prime.{prime_division,int_from_prime_division} (#8)

2020-03-06T11:55:22+00:00

Move explanation for the decomposition array from the Example section
to the method description. Mention the term "multiplicity".

Use examples that also demonstrate factors with multiplicity
other than 1, and avoid factors/multiplicities with the same value.
Also add the decomposition written as simple mathematical expression.

This also fixes missing syntax highlighting for the code examples
due to verbatim blocks that did not only include Ruby code.

[ruby/prime] Fix typo

2020-03-06T11:54:45+00:00

https://github.com/ruby/prime/commit/549c1b86f1

[ruby/prime] Improve docs for Prime.include? (#7)

2020-03-06T11:54:38+00:00

https://github.com/ruby/prime/commit/230a5af325

[ruby/prime] Fix Prime.include?

2020-03-06T11:54:33+00:00

Previously, it would be an infinite loop if passed a non-prime
integer.

Also, Prime.include? should also provide similar results to
Module#include? if passed a Module, so handle that.

For consistency with Enumerable#include?, return false if passed
other object types.

Fixes Ruby Bug 10167.

https://github.com/ruby/prime/commit/55dda6aa7f

[ruby/prime] Bump version

2019-12-23T02:48:54+00:00

proc.c: proc without block

2019-01-10T08:19:14+00:00

* proc.c (proc_new): promoted lambda/proc/Proc.new with no block
  in a method called with a block to a warning/error.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@66772 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

lib/prime.rb: remove unused methods

2018-06-24T09:31:07+00:00

This change removes TrialDivision#cache, TrialDivision#primes, and
TrialDivision#primes_so_far.

TrialDivision class is undocumented officially, so this class is used
only internally.  Yugui san moved prime library from mathn to prime in
2008, and then she might forget to delete these methods.

A patch from @shio-phys.  https://github.com/ruby/prime/pull/4

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@63737 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

Promote Prime library to default gems.

2018-06-02T23:05:45+00:00

  * Its upstream is https://github.com/ruby/prime.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@63560 b2dd03c8-39d4-4d8f-98ff-823fe69b080e