From: "hsbt (Hiroshi SHIBATA) via ruby-core" <ruby-core@ml.ruby-lang.org>
To: ruby-core@ml.ruby-lang.org
Cc: "hsbt (Hiroshi SHIBATA)" <noreply@ruby-lang.org>
Subject: [ruby-core:117412] [Ruby master Feature#12676] Significant performance increase, and code conciseness, for prime_division method in prime.rb
Date: Wed, 03 Apr 2024 03:31:52 +0000 (UTC) [thread overview]
Message-ID: <redmine.journal-107591.20240403033152.11075@ruby-lang.org> (raw)
In-Reply-To: redmine.issue-12676.20160815014812.11075@ruby-lang.org
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/
parent reply other threads:[~2024-04-03 3:32 UTC|newest]
Thread overview: expand[flat|nested] mbox.gz Atom feed
[parent not found: <redmine.issue-12676.20160815014812.11075@ruby-lang.org>]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.ruby-lang.org/en/community/mailing-lists/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=redmine.journal-107591.20240403033152.11075@ruby-lang.org \
--to=ruby-core@ruby-lang.org \
--cc=noreply@ruby-lang.org \
--cc=ruby-core@ml.ruby-lang.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).