summaryrefslogtreecommitdiff
path: root/lib/prime.rb
AgeCommit message (Collapse)Author
2021-05-27Promote prime to the bundled gemsHiroshi SHIBATA
Notes: Merged: https://github.com/ruby/ruby/pull/4530
2020-12-09[ruby/prime] v0.1.2Marc-Andre Lafortune
2020-12-09[ruby/prime] Optimize `Integer#prime?`Marc-Andre Lafortune
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 <sblackstone@gmail.com> Notes: Merged: https://github.com/ruby/ruby/pull/3847
2020-03-06Improve docs for Prime.{prime_division,int_from_prime_division} (#8)Marcus Stollsteimer
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.
2020-03-06[ruby/prime] Fix typoMarcus Stollsteimer
https://github.com/ruby/prime/commit/549c1b86f1
2020-03-06[ruby/prime] Improve docs for Prime.include? (#7)Marcus Stollsteimer
https://github.com/ruby/prime/commit/230a5af325
2020-03-06[ruby/prime] Fix Prime.include?Jeremy Evans
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
2019-12-22[ruby/prime] Bump versionMarc-Andre Lafortune
2019-01-10proc.c: proc without blocknobu
* 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
2018-06-24lib/prime.rb: remove unused methodsmame
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
2018-06-02Promote Prime library to default gems.hsbt
* 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
2017-05-20prime.rb: remove alias after timeout teststomar
* test/test_prime.rb: remove alias after timeout test. * lib/prime.rb: fix typo. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58813 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2017-05-20lib/prime: Fix primality of some large integers [#13492].marcandre
* lib/prime.rb: Use accurate sqrt to insure all factors are tested. Patch by Marcus Stollsteimer. * test/test_prime.rb: Adapt test for timeout git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58809 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2016-10-07* basictest/test.rb: Adjust spaces in class declarationshsbt
with inheritance. [fix GH-1227] Patch by @adrfer * lib/irb/*: ditto. * lib/prime.rb: ditto. * lib/shell/builtin-command.rb: ditto. * object.c: ditto. * sample/*.rb: ditto. * test/-ext-/method/test_arity.rb: ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@56371 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2016-08-10* lib/prime.rb: Optimize prime?marcandre
Adapted from patch by Jabari Zakiya [#12665] * test/test_prime.rb: Improve test git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@55856 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-12-16Add frozen_string_literal: false for all filesnaruse
When you change this to true, you may need to add more tests. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@53141 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-10-20* lib/prime.rb: Add basic argument checking to Prime.prime?marcandre
[Bug #11606] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@52201 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-10-20* lib/prime.rb: Optimize Integer#prime?marcandre
Patch by Nick Slocum [Bug #10354] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@52200 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-06-12* lib/prime.rb: Return sized enumerators.marcandre
Patch by Kenichi Kamiya [GH-931] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50857 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-06-12* lib/prime.rb: Fix with_object with no block givenmarcandre
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50856 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-06-12* lib/prime.rb: Have with_index accept an offset parameter.marcandre
Based on patch by T Yamada. [#11007] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50854 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-06-09* lib/prime.rb: Simplify and optimize EratosthenesSievemarcandre
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50803 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-06-09* lib/prime.rb: Simplify and optimize EratosthenesSievemarcandre
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50802 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-06-09* lib/matrix.rb: Simplify and optimize EratosthenesSievemarcandre
based on patch by Ajay Kumar. [Fixes GH-921] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50800 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-05-22* lib/matrix.rb: Stylingmarcandre
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50605 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2015-05-22* lib/prime.rb: Remove obsolete Prime.newmarcandre
patch by Ajay Kumar. [Fixes GH-891] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50604 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2014-12-10* lib/prime.rb: Remove useless loop and block capture.marcandre
See [#10354] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@48767 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2014-07-27* lib/cgi/core.rb: remove unused variables.hsbt
* lib/erb.rb: ditto. * lib/mkmf.rb: ditto. * lib/net/http/response.rb: ditto. * lib/optparse/version.rb: ditto. * lib/prime.rb: ditto. * lib/racc/parser.rb: ditto. * lib/rexml/document.rb: ditto. * lib/rexml/dtd/dtd.rb: ditto. * lib/rexml/element.rb: ditto. * lib/rexml/functions.rb: ditto. * lib/rexml/parsers/xpathparser.rb: ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46973 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2014-05-24prime.rb: fix a grammonobu
* lib/prime.rb (prime?): [DOC] fix a grammo, a missing article. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46076 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2014-05-23add information of incompatibility about Prime.prime? [Bug #7395]ayumin
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@46061 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2014-05-08* lib/prime.rb (Prime#prime?): negative numbers can't be primesayumin
by definition. reported by Ivan Kataitsev. [Bug #7395] * test/test_prime.rb: add test. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@45878 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2013-07-15* lib/prime.rb (Prime::EratosthenesGenerator,yugui
Prime::EratosthenesSieve): New implementation by robertjlooby <robertjlooby AT gmail.com>. * test/test_prime.rb: updated with new method name commit 4b6090ea852d63b26e02796c69b41caa0fa95077 Merge: ceda881 c8f7809 Author: Yuki Sonoda (Yugui) <yugui@yugui.jp> Date: Mon Jul 15 12:50:04 2013 +0900 Merge commit 'c8f780987fbdfbae428977487e1cf793c4c36d3f' Conflicts: lib/prime.rb commit c8f780987fbdfbae428977487e1cf793c4c36d3f Author: robertjlooby <robertjlooby@gmail.com> Date: Thu Jun 27 23:04:45 2013 -0500 updated test/test_prime.rb with new method name commit 996517bdbb3108cd1687d99613b69e539eb1567b Author: robertjlooby <robertjlooby@gmail.com> Date: Thu Jun 27 22:59:39 2013 -0500 new implementation of Prime::EratosthenesGenerator and Prime::EratosthenesSieve git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@41982 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2013-06-30* lib/prime.rb: Corrected a few comments. Patch by @Nullset14.charliesome
Fixes GH-346. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@41714 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2013-01-13* lib/irb.rb, lib/prime.rb: Typos in overviewzzak
Patch by Ershad K [Github Fixes #234] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@38798 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2011-06-01 * lib/prime.rb: Indent examples enough to appear as code sections.drbrain
Note that Prime is Enumerable. [#4762] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@31880 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2011-05-19* lib: revert r31635-r31638 and untabify with expand(1).nobu
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@31641 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2011-05-18 * lib: Convert tabs to spaces for ruby files perdrbrain
http://redmine.ruby-lang.org/projects/ruby/wiki/DeveloperHowto#coding-style Patch by Steve Klabnik [Ruby 1.9 - Bug #4730] Patch by Jason Dew [Ruby 1.9 - Feature #4718] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@31635 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2010-03-20* lib: fixed typo. a patch by Sho Hashimoto in [ruby-dev:40716].nobu
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@26986 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2009-10-18* test/test_prime.rbyugui
(TestPrime#test_eratosthenes_works_fine_after_timeout): test for [ruby-dev:39465]. * lib/prime.rb (Prime::EratosthenesSieve): fixed [ruby-dev:39465]. suppressed memory reallocation. constantified some magic numbers. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@25388 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2009-09-13* lib/prime.rb (EratosthenesGenerator#initialize): call super.nobu
(TrialDivisionGenerator, Generator23): ditto. [ruby-core:25539] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@24884 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2009-07-13* lib/prime.rb (Prime#prime_division): now decomposesyugui
negative integer into a decomposition with element [-1, 1]. * test/test_prime.rb: test for it. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@24091 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2009-06-11* lib/prime.rb: documentation typo fixed. a patch from okkez.matz
[ruby-dev:38586] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@23665 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2009-03-06* {ext,lib,test}/**/*.rb: removed trailing spaces.nobu
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@22784 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2009-03-03* lib/prime.rb (Prime::prime?): used to return a wrong answer.yugui
[ruby-core:22646]. * test/test_prime.rb (test_prime?): test case for [ruby-core:22646]. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@22741 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2008-12-18* lib/optparse/version.rb: remove variable shadowing to stopmatz
warning. [ruby-core:20612] * lib/irb/completion.rb, lib/net/imap.rb, lib/prime.rb, lib/rinda/ring.rb, lib/racc/parser.rb, lib/shell/command-processor.rb, lib/yaml/yamlnode.rb: ditto. * lib/racc/parser.rb: remove space before parentheses. * lib/shell/command-processor.rb, lib/shell/process-controller.rb: use parentheses around arguments. * lib/irb/ext/change-ws.rb, lib/rexml/validation/relaxng.rb, lib/yaml/baseemitter.rb: indentation fix. * lib/matrix.rb: small cosmetic change. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@20859 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2008-12-10* enumerator.c (enumerator_next): Fix a typo: s/rewinded/rewound/.knu
* lib/prime.rb (Prime::OldCompatibility#each): Ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@20604 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2008-09-04* lib/prime.rb (Prime::OldCompatibility#each): added compatibility toyugui
Ruby 1.8.7. (Prime#each): added more rdocs. (Prime#each): remembers the last value of the given block. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@19135 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
2008-09-03* lib/mathn.rb (Integer): moved into prime.rb.yugui
(Prime): ditto. * lib/prime.rb (Integer): moved from mathn.rb. (Integer.each_prime): added. (Integer#prime?): added. (Prime): moved from mathn.rb. Its implmentation was rewritten. see [ruby-dev:35863]. And patched by Keiju ISHITSUKA <keiju@ishitsuka.com>, see [ruby-dev:36128]. (Prime.new): obsolete. (Prime.instance): added. (Prime.each): added. (Prime.int_from_prime_division): added. (Prime.prime_division): added. (Prime.prime?): added. Patch by TOYOFUKU Chikanobu <nobu_toyofuku at nifty.com> in [ruby-dev:36067]. (Prime.cache): removed. (Prime.primes): removed. (Prime.primes_so_far): removed. (Prime#int_from_prime_division): added. (Prime#prime_division): added. (Prime#prime?): added. (Prime#primes): removed. (Prime#primes_so_far): removed. (Prime::PseudoPrmeGenerator): added. (Prime::EratosthenesGenerator): added. (Prime::TrialDivisionGenerator): added. (Prime::Generator23): added. (Prime::TrialDivision): added. Extracted from the previous implementation of Prime by Keiju ISHITSUKA. (Prime::EratosthenesSieve): added. * lib/.document (prime.rb): added * lib/README (prime.rb): added * test/test_prime.rb: added. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@19095 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-27 05:07:59 +0000