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=-3.9 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,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 9C8B01F463 for ; Sat, 4 Jan 2020 23:10:08 +0000 (UTC) Received: from neon.ruby-lang.org (localhost [IPv6:::1]) by neon.ruby-lang.org (Postfix) with ESMTP id 7FB0C1209FA; Sun, 5 Jan 2020 08:09:50 +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 814071209ED for ; Sun, 5 Jan 2020 08:09:47 +0900 (JST) Received: by filterdrecv-p3mdw1-56c97568b5-thcqq with SMTP id filterdrecv-p3mdw1-56c97568b5-thcqq-18-5E111B3B-22 2020-01-04 23:09:47.608142186 +0000 UTC m=+1636000.996801900 Received: from herokuapp.com (unknown [3.84.47.179]) by ismtpd0024p1iad2.sendgrid.net (SG) with ESMTP id Bo0VEMhGQJqgiFfSe9cERQ for ; Sat, 04 Jan 2020 23:09:47.472 +0000 (UTC) Date: Sat, 04 Jan 2020 23:09:47 +0000 (UTC) From: ruby-core@marc-andre.ca Message-ID: References: Mime-Version: 1.0 X-Redmine-MailingListIntegration-Message-Ids: 72327 X-Redmine-Project: ruby-master X-Redmine-Issue-Id: 16468 X-Redmine-Issue-Author: steveb3210 X-Redmine-Sender: marcandre 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?jp+swDN4yjawvlS938eDTV7AcuBgTjW2xvQn0nZL4RCO9nCrpsPUKNw04vKagV?= =?us-ascii?Q?rPoP3Zmu4Jn76C5V6Go8o=2FTQvviH7Kjocya1TH5?= =?us-ascii?Q?nQYpOIUtPEAnWkPadLfRU=2FJ8tHEn4UKntRDrPgC?= =?us-ascii?Q?jAMU3ghw7VlhpSD8ARfV6KpjreQ5T7YA7vGfopf?= =?us-ascii?Q?Ohb3VjsMXmj8f69Q1mJhmQFLC6uVjsS7nNRCxYi?= =?us-ascii?Q?Gz4bWe6pJAvil+OHQ=3D?= To: ruby-core@ruby-lang.org X-ML-Name: ruby-core X-Mail-Count: 96665 Subject: [ruby-core:96665] [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 marcandre (Marc-Andre Lafortune). Interesting. We might as well always return the correct result, i.e. apply the fast algorithm for integers < 318,665,857,834,031,151,167,461 and the slow algorithm for larger ones. Would you care to modify your patch? ---------------------------------------- Feature #16468: Switch to Miller-Rabin for Prime.prime? https://bugs.ruby-lang.org/issues/16468#change-83647 * 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/