From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on starla X-Spam-Level: X-Spam-Status: No, score=0.1 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_BL_SPAMCOP_NET,SPF_HELO_PASS, SPF_PASS autolearn=no autolearn_force=no version=3.4.6 Received: from nue.mailmanlists.eu (nue.mailmanlists.eu [94.130.110.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 2242A1F44D for ; Wed, 3 Apr 2024 03:32:05 +0000 (UTC) Authentication-Results: dcvr.yhbt.net; dkim=pass (1024-bit key; secure) header.d=ml.ruby-lang.org header.i=@ml.ruby-lang.org header.a=rsa-sha256 header.s=mail header.b=h1plFpoi; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=ruby-lang.org header.i=@ruby-lang.org header.a=rsa-sha256 header.s=s1 header.b=dOxhGBw2; dkim-atps=neutral Received: from nue.mailmanlists.eu (localhost [127.0.0.1]) by nue.mailmanlists.eu (Postfix) with ESMTP id D319A83B72; Wed, 3 Apr 2024 03:31:56 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ml.ruby-lang.org; s=mail; t=1712115116; bh=4+VIl3Mc+j1xjWW20P769WF+fuxd+vhdfGgbWqdDmIU=; h=Date:References:To:Reply-To:Subject:List-Id:List-Archive: List-Help:List-Owner:List-Post:List-Subscribe:List-Unsubscribe: From:Cc:From; b=h1plFpoiQCb5Zh7gblGxXv++q7iS2CW9u1yVo+x/Y2ZbeEQ7cNF2f5OQ+K4pMczjc AorTz4p+Bf6f+yawC91QNAon2uuPjb7PiM/wBvCECKFeXd0KoYF+HzfJaueWZQjB0p 4/C9tAuomQh7z2WHNnbGJ16DusFIJLVP5KlKGVHM= Received: from s.wrqvtbkv.outbound-mail.sendgrid.net (s.wrqvtbkv.outbound-mail.sendgrid.net [149.72.123.24]) by nue.mailmanlists.eu (Postfix) with ESMTPS id DE67683AE9 for ; Wed, 3 Apr 2024 03:31:53 +0000 (UTC) Authentication-Results: nue.mailmanlists.eu; dkim=pass (2048-bit key; unprotected) header.d=ruby-lang.org header.i=@ruby-lang.org header.a=rsa-sha256 header.s=s1 header.b=dOxhGBw2; dkim-atps=neutral DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ruby-lang.org; h=from:references:subject:mime-version:content-type: content-transfer-encoding:list-id:to:cc:content-type:from:subject:to; s=s1; bh=P07Nb2RQ7HQbqpkVqciviLUzmAkaOtpGhwhrhQAWu4Q=; b=dOxhGBw2/jvPKXh2XQEuvMzSZ08ynHBoIXRb8BGTDURT308Br64xywhezGjZaOtRV7pk i8rH9D3xYRnvR0DxtJDXH7DGkFdpAZb2dzuABGT4A9TQr55FNK/rRIUYQu8FLEPG/8cDe2 HnI+Q8enXYyy5rgdoGKe8xwMLRwINK430D/q9wFqjL1lkfpR62I9JSqLKD1k/liHJUGXef dI57aVzYHh9aQ1g4EpeVKHlSfBXGsQaa3vxTQ2/4S3jqHIaZfrWudcu9JklIcnxKLWvKaV q+GCEQ0KUxOj5pYfL5NwREQwSNIT15Fo0ZrwPjrgQR0Rbznbt9a4CgT/7gwaSCWA== Received: by filterdrecv-5fd9fcbc44-t8qtt with SMTP id filterdrecv-5fd9fcbc44-t8qtt-1-660CCDA8-10 2024-04-03 03:31:52.717308995 +0000 UTC m=+1321560.094513770 Received: from herokuapp.com (unknown) by geopod-ismtpd-11 (SG) with ESMTP id AyM8C95bS56gdoPWVpOTbQ for ; Wed, 03 Apr 2024 03:31:52.672 +0000 (UTC) Date: Wed, 03 Apr 2024 03:31:52 +0000 (UTC) Message-ID: References: Mime-Version: 1.0 X-Redmine-Project: ruby-master X-Redmine-Issue-Tracker: Feature X-Redmine-Issue-Id: 12676 X-Redmine-Issue-Author: jzakiya X-Redmine-Issue-Assignee: marcandre X-Redmine-Issue-Priority: Normal X-Redmine-Sender: hsbt 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-Redmine-MailingListIntegration-Message-Ids: 94007 X-SG-EID: =?us-ascii?Q?u001=2ESNtsfy=2FRYrUmxOeGSN+Ah1new64UppKFg8YOAgra6KK6sIhqEP6LswYh4?= =?us-ascii?Q?tCf2AhAD20FCmXanLCSpdJ9Heq83FKB1eeA=2FIRz?= =?us-ascii?Q?=2FUFVHcMb3GOw+7mx9RsVnYR0RNsv=2FISNUMCuN1M?= =?us-ascii?Q?HVYgkAgiGHKKVQfnhwiDXlfHlWBrdF+YPGqf6HG?= =?us-ascii?Q?yuNy5w3SHuulfwb7HAicCZSPnkvNSNyYIRmNyHk?= =?us-ascii?Q?S2xiqOQlyAzQ7Ua6E5zFDfkc8ZrOog+CgYWfWDI?= =?us-ascii?Q?8lRyMxAeEYRXAwqlV3lkNei0MA=3D=3D?= To: ruby-core@ml.ruby-lang.org X-Entity-ID: u001.I8uzylDtAfgbeCOeLBYDww== Message-ID-Hash: 3S4JCFGIXYHTYXGPKYJ5LBUOHKTIRWY2 X-Message-ID-Hash: 3S4JCFGIXYHTYXGPKYJ5LBUOHKTIRWY2 X-MailFrom: bounces+313651-b711-ruby-core=ml.ruby-lang.org@em5188.ruby-lang.org X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header X-Mailman-Version: 3.3.3 Precedence: list Reply-To: Ruby developers Subject: [ruby-core:117412] [Ruby master Feature#12676] Significant performance increase, and code conciseness, for prime_division method in prime.rb List-Id: Ruby developers Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: From: "hsbt (Hiroshi SHIBATA) via ruby-core" Cc: "hsbt (Hiroshi SHIBATA)" Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Issue #12676 has been updated by hsbt (Hiroshi SHIBATA). Status changed from Assigned to Closed prime is maintained at https://github.com/ruby/prime today. If you still interest this, can you submit this to upstream repo? ---------------------------------------- Feature #12676: Significant performance increase, and code conciseness, for prime_division method in prime.rb https://bugs.ruby-lang.org/issues/12676#change-107591 * Author: jzakiya (Jabari Zakiya) * Status: Closed * Assignee: marcandre (Marc-Andre Lafortune) ---------------------------------------- I earlier posted code to simplify the prime_division method in prime.rb. This made the code much more concise and readable/understandable, while also providing a small speed increase. The code presented here for prime_division2 maintains the conciseness and readability, but uses a different/simpler algorithm to provide a significant speed increase over the current implementation of prime_division in prime.rb. Timings for selected large primes are provided, run on CRuby 2.3.1. System: System76 3.5GHz I7 cpu laptop, Linux 64-bit OS in Virtual Box. ``` n1 = 100_000_000_000_000_003 n2 = 200_000_000_000_000_003 n3 = 1_000_000_000_000_000_003 n1 n2 n3 prime_division 23.7 33.5 74.6 prime_division1 22.9 32.2 72.8 prime_division2 14.8 20.5 45.8 ``` ```ruby def tm; s = Time.now; yield; Time.now - s end irb(main):015:0> n = 100_000_000_000_000_003; tm{ n.prime_division } => 23.730239721 irb(main):016:0> n = 100_000_000_000_000_003; tm{ n.prime_division1 } => 22.877657172 irb(main):017:0> n = 100_000_000_000_000_003; tm{ n.prime_division2 } => 14.758561827 irb(main):018:0> n = 200_000_000_000_000_003; tm{ n.prime_division } => 33.502851342 irb(main):019:0> n = 200_000_000_000_000_003; tm{ n.prime_division1 } => 32.23911595 irb(main):020:0> n = 200_000_000_000_000_003; tm{ n.prime_division2 } => 20.476660683 irb(main):021:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division } => 74.630244055 irb(main):022:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division1 } => 72.778948947 irb(main):023:0> n = 1_000_000_000_000_000_003; tm{ n.prime_division2 } => 45.802756121 ``` 1. Current code for prime_division in prime.rb. ```ruby def prime_division(value, generator = Prime::Generator23.new) raise ZeroDivisionError if value == 0 if value < 0 value = -value pv = [[-1, 1]] else pv = [] end generator.each do |prime| count = 0 while (value1, mod = value.divmod(prime) mod) == 0 value = value1 count += 1 end if count != 0 pv.push [prime, count] end break if value1 <= prime end if value > 1 pv.push [value, 1] end pv end ``` 2. Code simplification for current algorithm, increases conciseness/readability, with slight speedup. ```ruby def prime_division1(value, generator = Prime::Generator23.new) raise ZeroDivisionError if value == 0 pv = value < 0 ? [[-1, 1]] : [] value = value.abs generator.each do |prime| count = 0 while (value1, mod = value.divmod(prime); mod) == 0 value = value1 count += 1 end pv.push [prime, count] unless count == 0 break if prime > value1 end pv.push [value, 1] if value > 1 pv end ``` 3. Change of algorithm, maintains conciseness/readability with significant speed increase. ```ruby def prime_division2(value, generator = Prime::Generator23.new) raise ZeroDivisionError if value == 0 pv = value < 0 ? [-1] : [] value = value.abs sqrt_value = Math.sqrt(value).to_i generator.each do |prime| break if prime > sqrt_value while value % prime == 0 pv << prime value /= prime sqrt_value = Math.sqrt(value).to_i end end pv << value if value > 1 pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] } end ``` -- https://bugs.ruby-lang.org/ ______________________________________________ ruby-core mailing list -- ruby-core@ml.ruby-lang.org To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org ruby-core info -- https://ml.ruby-lang.org/mailman3/postorius/lists/ruby-core.ml.ruby-lang.org/