aboutsummaryrefslogtreecommitdiffstats
path: root/test/test_prime.rb
Commit message (Collapse)AuthorAgeFilesLines
* [ruby/prime] Optimize `Integer#prime?`Marc-Andre Lafortune2020-12-091-0/+11
| | | | | | | | | | | | | | | | 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>
* [ruby/prime] Fix Prime.include?Jeremy Evans2020-03-061-0/+8
| | | | | | | | | | | | | | | 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
* Suppress method redefinition warningsNobuyoshi Nakada2019-06-301-0/+1
|
* Removed unused variablesNobuyoshi Nakada2019-06-301-1/+1
|
* test/test_prime.rb: add testcases of prime librarymame2018-06-241-0/+81
| | | | | | | This change improves line coverage of prime.rb from 86% to 99%. A patch from @shio-phys. https://github.com/ruby/prime/pull/3 git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@63735 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* prime.rb: remove alias after timeout teststomar2017-05-201-0/+1
| | | | | | | | * 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
* lib/prime: Fix primality of some large integers [#13492].marcandre2017-05-201-7/+8
| | | | | | | | | * 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
* test/test_prime.rb: update method name in commentstomar2017-04-221-1/+1
| | | | git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58449 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * lib/prime.rb: Optimize prime?marcandre2016-08-101-10/+7
| | | | | | | | 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
* Add frozen_string_literal: false for all filesnaruse2015-12-161-0/+1
| | | | | | 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
* * lib/prime.rb: Add basic argument checking to Prime.prime?marcandre2015-10-201-0/+5
| | | | | | [Bug #11606] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@52201 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* test: refine assertionsnobu2015-06-251-3/+1
| | | | | | | | | | | | | * test/test_prime.rb (test_eratosthenes_works_fine_after_timeout): use assert_raise to check timeout. * test/test_securerandom.rb: check if results are hexadecimal strings, and refine failure messages. * test/test_tracer.rb (test_tracer_with_option_r_without_gems): use assert_equal to compare. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51023 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* test_prime.rb: cosmetic changesnobu2015-06-251-2/+2
| | | | | | | * test/test_prime.rb (test_eratosthenes_works_fine_after_timeout): use spaces instead of TABs in ruby codes. [Fix GH-944] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@51022 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* test_prime.rb: descriptive assertionsnobu2015-06-141-32/+32
| | | | | | | * test/test_prime.rb: use more descriptive assertions for better failure meessages, instead of simple assert. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50893 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * lib/prime.rb: Return sized enumerators.marcandre2015-06-121-0/+7
| | | | | | Patch by Kenichi Kamiya [GH-931] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50857 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * lib/prime.rb: Fix with_object with no block givenmarcandre2015-06-121-0/+9
| | | | git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50856 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * lib/prime.rb: Have with_index accept an offset parameter.marcandre2015-06-121-0/+11
| | | | | | Based on patch by T Yamada. [#11007] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50854 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* use assert_raisenobu2015-06-021-1/+1
| | | | git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50727 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * lib/prime.rb: Remove obsolete Prime.newmarcandre2015-05-221-14/+8
| | | | | | patch by Ajay Kumar. [Fixes GH-891] git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50604 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * lib/prime.rb (Prime#prime?): negative numbers can't be primesayumin2014-05-081-2/+2
| | | | | | | 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
* * lib/prime.rb (Prime::EratosthenesGenerator,yugui2013-07-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* * test/syck/test_string.rb (Syck::TestString#test_non_binary_string):nobu2011-02-131-1/+1
| | | | | | | | use assert_not instead of refute, unless required minitest directly. * test/test_prime.rb (TestPrime::sieve.Integer): ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@30859 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * test/test_prime.rb (TestPrime#test_new): the warning expected haveyugui2010-09-221-5/+7
| | | | | | | | not been displayed when $VERBOSE == nil. Patch by Shota Fukumori a.k.a. sora_h. [ruby-dev:42272] Recovers $stderr even if StringIO.new fails. Reported by unak. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@29316 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* supress warnings.akr2010-01-251-5/+5
| | | | git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@26418 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * test/test_prime.rbyugui2009-10-181-0/+26
| | | | | | | | | | | | (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
* * lib/prime.rb (Prime#prime_division): now decomposesyugui2009-07-131-0/+5
| | | | | | | | 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
* * {ext,lib,test}/**/*.rb: removed trailing spaces.nobu2009-03-061-10/+10
| | | | git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@22784 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
* * lib/prime.rb (Prime::prime?): used to return a wrong answer.yugui2009-03-031-0/+15
| | | | | | | | [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
* * lib/mathn.rb (Integer): moved into prime.rb.yugui2008-09-031-0/+126
(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.39.1) at 2024-05-29 23:59:51 +0000