From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS4713 221.184.0.0/13 X-Spam-Status: No, score=-4.1 required=3.0 tests=AWL,BAYES_00, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from neon.ruby-lang.org (neon.ruby-lang.org [221.186.184.75]) by dcvr.yhbt.net (Postfix) with ESMTP id A90711F463 for ; Sun, 5 Jan 2020 01:41:20 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 7DA93120A77; Sun, 5 Jan 2020 10:41:04 +0900 (JST) Received: from xtrwkhkc.outbound-mail.sendgrid.net (xtrwkhkc.outbound-mail.sendgrid.net [167.89.16.28]) by neon.ruby-lang.org (Postfix) with ESMTPS id 79D83120A76 for ; Sun, 5 Jan 2020 10:41:02 +0900 (JST) Received: by filterdrecv-p3las1-5bf99c48d-j57ff with SMTP id filterdrecv-p3las1-5bf99c48d-j57ff-19-5E113EB5-11 2020-01-05 01:41:09.308730387 +0000 UTC m=+1644925.091519503 Received: from herokuapp.com (unknown [3.84.47.179]) by ismtpd0112p1mdw1.sendgrid.net (SG) with ESMTP id zg7yGgvgTsqNCT5Jak-Z2Q for ; Sun, 05 Jan 2020 01:41:09.162 +0000 (UTC) Date: Sun, 05 Jan 2020 01:41:09 +0000 (UTC) From: mame@ruby-lang.org Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 72330 X-Redmine-Project: ruby-master X-Redmine-Issue-Id: 16468 X-Redmine-Issue-Author: steveb3210 X-Redmine-Sender: mame X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-SG-EID: =?us-ascii?Q?EJh2gqwnyqXtd++xo=2FinyA1V0bXouTB4FkWnzNiKb48LtqrU0n0KXrwnziKAF+?= =?us-ascii?Q?=2F+rKbu9wEqBuLcOeTVVkyPMkWCdGnkaLq=2FVRbSU?= =?us-ascii?Q?4VCqM0AVOaODgSFx9p3wCTJNQ8t6kvrb5DH5JZI?= =?us-ascii?Q?=2Fz+8OKPt62tbo9G69byk8OMdW9dD0Gs3le+E18U?= =?us-ascii?Q?q8N7MWCAFP5hmMAYJcr38Bs6J5ldxtJJdJbB7zC?= =?us-ascii?Q?Gqbl+DFOCqe5e95mY=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 96668 Subject: [ruby-core:96668] [Ruby master Feature#16468] Switch to Miller-Rabin for Prime.prime? X-BeenThere: ruby-core@ruby-lang.org X-Mailman-Version: 2.1.15 Precedence: list Reply-To: Ruby developers List-Id: Ruby developers List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: ruby-core-bounces@ruby-lang.org Sender: "ruby-core" Issue #16468 has been updated by mame (Yusuke Endoh). It can fall back to APR-CL primality test when Miller-Rabin does not work. In my personal opinion, it would be best to keep prime.rb simple because it is a hobby library. You may be interested in my gem: https://github.com/mame/faster_prime ---------------------------------------- Feature #16468: Switch to Miller-Rabin for Prime.prime? https://bugs.ruby-lang.org/issues/16468#change-83650 * Author: steveb3210 (Stephen Blackstone) * Status: Open * Priority: Normal * Assignee: * Target version: ---------------------------------------- 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.diff (1.75 KB) -- https://bugs.ruby-lang.org/