[#97086] [Ruby master Bug#16612] Enumerator::ArithmeticSequence#last with float range produces incorrect value — muraken@...
Issue #16612 has been updated by mrkn (Kenta Murata).
4 messages
2020/02/07
[#97095] [PATCH] Modify shebang of libexec/y2racc and libexec/racc2y. — Wang Mingyu <wangmy@...>
change /usr/local/bin/ruby to /usr/bin/env ruby.
3 messages
2020/02/08
[#97307] [Ruby master Feature#16663] Add block or filtered forms of Kernel#caller to allow early bail-out — headius@...
Issue #16663 has been reported by headius (Charles Nutter).
29 messages
2020/02/28
[ruby-core:97209] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime?
From:
sblackstone@...
Date:
2020-02-20 04:11:16 UTC
List:
ruby-core #97209
Issue #16468 has been updated by steveb3210 (Stephen Blackstone).
Created PR - https://github.com/ruby/ruby/pull/2917
----------------------------------------
Feature #16468: Switch to Miller-Rabin for Prime.prime?
https://bugs.ruby-lang.org/issues/16468#change-84317
* Author: steveb3210 (Stephen Blackstone)
* Status: Open
* Priority: Normal
----------------------------------------
The miller-rabin algorithm is a non-deterministic primality test, however it is known that below 2**64, you can always get a deterministic answer by only checking a=[2,3,5,7,11,13,17,19,23, 29, 31, 37]
Given that Prime.prime? would never respond in a reasonable amount of time for larger numbers, we can gain much more utility and performance by switching..
```
user system total real
miller_rabin: random set 0.150000 0.000000 0.150000 ( 0.152212)
Prime.prime?: random set 0.270000 0.000000 0.270000 ( 0.281257)
user system total real
miller_rabin: 16 digits 0.010000 0.000000 0.010000 ( 0.000300)
Prime.prime? 16 digits 2.200000 0.020000 2.220000 ( 2.368247)
user system total real
miller_rabin: 2-10000 0.030000 0.000000 0.030000 ( 0.035752)
Prime.prime? 2-10000 0.020000 0.000000 0.020000 ( 0.022948)
---Files--------------------------------
patch_with_argument_error.diff (1.94 KB)
--
https://bugs.ruby-lang.org/
Unsubscribe: <mailto:[email protected]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>