prime
prime copied to clipboard
Published
20 hours ago •
ruby
ruby
Feature Request: Add divisors methods
I want Integer#divisors that return the divisors of self.
6.divisors # => [1, 2, 3, 6]
7.divisors # => [1, 7]
8.divisors # => [1, 2, 4, 8]
Divisors are basic and important mathematical matters. Enumeration of divisors can be useful or necessary when solving integer problems.
The main idea and divisors code was provided by tompng-san.
I improved the average speed and added document and tests.
Benchmark
This PR code runs faster than the simple O(√N) code for large numbers.
Benchmark code
Details (Click here)
class Integer
def divisors
if prime?
[1, self]
elsif self == 1
[1]
else
xs = prime_division.map{ |p, n| Array.new(n + 1){ |e| p**e } }
x = xs.pop
x.product(*xs).map{ |t| t.inject(:*) }.sort
end
end
# this divisors is slow when +self+ is a prime number
def original_divisors
xs = prime_division.map{ |p, n| Array.new(n + 1){ |e| p**e } }
[1].product(*xs).map{ |t| t.inject(:*) }.sort
end
# time complexity: O(√N)
# this is very slow when +self+ is a large number
def simple_divisors
n = self
s = Integer.sqrt(n)
res1 = []
res2 = []
i = 1
while i <= s
if self % i == 0
res1 << i
res2.unshift(n / i)
end
i += 1
end
res1.pop if s * s == n
res1.concat(res2)
end
end
require 'bundler/inline'
gemfile do
source 'https://rubygems.org'
gem 'benchmark-ips'
end
require 'prime'
srand(42)
2.upto(15) do |exp|
r = 10 ** (exp - 1) .. 10 ** exp
samples = 100.times.map { rand(r) }
puts "Testing 10**#{exp- 1 }..10**#{exp} (#{r})"
Benchmark.ips do |x|
x.config(:time => 0.05, :warmup => 0.1)
x.report('divisors '){ samples.each { |i| i.divisors } }
x.report('original '){ samples.each { |i| i.original_divisors } }
x.report('simple_division'){ samples.each { |i| i.simple_divisors } } if exp < 14
x.compare!
end
end
Result
Details (Click here)
Testing 10**1..10**2 (10..100)
Warming up --------------------------------------
divisors 282.000 i/100ms
original 226.000 i/100ms
simple_division 1.704k i/100ms
Calculating -------------------------------------
divisors 2.469k (± 0.0%) i/s - 282.000 in 0.114232s
original 2.132k (± 0.0%) i/s - 226.000 in 0.106019s
simple_division 16.023k (± 0.0%) i/s - 1.704k in 0.106345s
Comparison:
simple_division: 16023.3 i/s
divisors : 2468.7 i/s - 6.49x (± 0.00) slower
original : 2131.7 i/s - 7.52x (± 0.00) slower
Testing 10**2..10**3 (100..1000)
Warming up --------------------------------------
divisors 176.000 i/100ms
original 153.000 i/100ms
simple_division 951.000 i/100ms
Calculating -------------------------------------
divisors 1.700k (± 0.0%) i/s - 176.000 in 0.103512s
original 1.496k (± 0.0%) i/s - 153.000 in 0.102284s
simple_division 8.945k (± 0.0%) i/s - 951.000 in 0.106321s
Comparison:
simple_division: 8944.6 i/s
divisors : 1700.3 i/s - 5.26x (± 0.00) slower
original : 1495.8 i/s - 5.98x (± 0.00) slower
Testing 10**3..10**4 (1000..10000)
Warming up --------------------------------------
divisors 129.000 i/100ms
original 114.000 i/100ms
simple_division 421.000 i/100ms
Calculating -------------------------------------
divisors 1.211k (± 0.0%) i/s - 129.000 in 0.106486s
original 1.134k (± 0.0%) i/s - 114.000 in 0.100531s
simple_division 3.964k (± 0.0%) i/s - 421.000 in 0.106201s
Comparison:
simple_division: 3964.2 i/s
divisors : 1211.4 i/s - 3.27x (± 0.00) slower
original : 1134.0 i/s - 3.50x (± 0.00) slower
Testing 10**4..10**5 (10000..100000)
Warming up --------------------------------------
divisors 91.000 i/100ms
original 72.000 i/100ms
simple_division 182.000 i/100ms
Calculating -------------------------------------
divisors 836.313 (± 0.0%) i/s - 91.000 in 0.108811s
original 729.912 (± 0.0%) i/s - 72.000 in 0.098642s
simple_division 1.637k (± 0.0%) i/s - 182.000 in 0.111150s
Comparison:
simple_division: 1637.4 i/s
divisors : 836.3 i/s - 1.96x (± 0.00) slower
original : 729.9 i/s - 2.24x (± 0.00) slower
Testing 10**5..10**6 (100000..1000000)
Warming up --------------------------------------
divisors 55.000 i/100ms
original 41.000 i/100ms
simple_division 55.000 i/100ms
Calculating -------------------------------------
divisors 557.708 (± 0.0%) i/s - 55.000 in 0.098618s
original 396.028 (± 0.0%) i/s - 41.000 in 0.103528s
simple_division 577.980 (± 0.0%) i/s - 55.000 in 0.095159s
Comparison:
simple_division: 578.0 i/s
divisors : 557.7 i/s - 1.04x (± 0.00) slower
original : 396.0 i/s - 1.46x (± 0.00) slower
Testing 10**6..10**7 (1000000..10000000)
Warming up --------------------------------------
divisors 26.000 i/100ms
original 23.000 i/100ms
simple_division 20.000 i/100ms
Calculating -------------------------------------
divisors 267.355 (± 0.0%) i/s - 26.000 in 0.097249s
original 219.073 (± 0.0%) i/s - 23.000 in 0.104988s
simple_division 193.864 (± 0.0%) i/s - 20.000 in 0.103165s
Comparison:
divisors : 267.4 i/s
original : 219.1 i/s - 1.22x (± 0.00) slower
simple_division: 193.9 i/s - 1.38x (± 0.00) slower
Testing 10**7..10**8 (10000000..100000000)
Warming up --------------------------------------
divisors 10.000 i/100ms
original 7.000 i/100ms
simple_division 5.000 i/100ms
Calculating -------------------------------------
divisors 88.105 (± 0.0%) i/s - 10.000 in 0.113501s
original 66.095 (± 0.0%) i/s - 7.000 in 0.105908s
simple_division 54.814 (± 0.0%) i/s - 5.000 in 0.091218s
Comparison:
divisors : 88.1 i/s
original : 66.1 i/s - 1.33x (± 0.00) slower
simple_division: 54.8 i/s - 1.61x (± 0.00) slower
Testing 10**8..10**9 (100000000..1000000000)
Warming up --------------------------------------
divisors 5.000 i/100ms
original 2.000 i/100ms
simple_division 1.000 i/100ms
Calculating -------------------------------------
divisors 48.169 (± 0.0%) i/s - 5.000 in 0.103801s
original 29.562 (± 0.0%) i/s - 2.000 in 0.067655s
simple_division 18.661 (± 0.0%) i/s - 1.000 in 0.053589s
Comparison:
divisors : 48.2 i/s
original : 29.6 i/s - 1.63x (± 0.00) slower
simple_division: 18.7 i/s - 2.58x (± 0.00) slower
Testing 10**9..10**10 (1000000000..10000000000)
Warming up --------------------------------------
divisors 1.000 i/100ms
original 1.000 i/100ms
simple_division 1.000 i/100ms
Calculating -------------------------------------
divisors 19.975 (± 0.0%) i/s - 1.000 in 0.050062s
original 17.641 (± 0.0%) i/s - 1.000 in 0.056686s
simple_division 5.582 (± 0.0%) i/s - 1.000 in 0.179143s
Comparison:
divisors : 20.0 i/s
original : 17.6 i/s - 1.13x (± 0.00) slower
simple_division: 5.6 i/s - 3.58x (± 0.00) slower
Testing 10**10..10**11 (10000000000..100000000000)
Warming up --------------------------------------
divisors 1.000 i/100ms
original 1.000 i/100ms
simple_division 1.000 i/100ms
Calculating -------------------------------------
divisors 6.962 (± 0.0%) i/s - 1.000 in 0.143632s
original 4.042 (± 0.0%) i/s - 1.000 in 0.247414s
simple_division 1.863 (± 0.0%) i/s - 1.000 in 0.536792s
Comparison:
divisors : 7.0 i/s
original : 4.0 i/s - 1.72x (± 0.00) slower
simple_division: 1.9 i/s - 3.74x (± 0.00) slower
Testing 10**11..10**12 (100000000000..1000000000000)
Warming up --------------------------------------
divisors 1.000 i/100ms
original 1.000 i/100ms
simple_division 1.000 i/100ms
Calculating -------------------------------------
divisors 2.684 (± 0.0%) i/s - 1.000 in 0.372569s
original 1.398 (± 0.0%) i/s - 1.000 in 0.715181s
simple_division 0.594 (± 0.0%) i/s - 1.000 in 1.682943s
Comparison:
divisors : 2.7 i/s
original : 1.4 i/s - 1.92x (± 0.00) slower
simple_division: 0.6 i/s - 4.52x (± 0.00) slower
Testing 10**12..10**13 (1000000000000..10000000000000)
Warming up --------------------------------------
divisors 1.000 i/100ms
original 1.000 i/100ms
simple_division 1.000 i/100ms
Calculating -------------------------------------
divisors 0.825 (± 0.0%) i/s - 1.000 in 1.211711s
original 0.563 (± 0.0%) i/s - 1.000 in 1.776719s
simple_division 0.184 (± 0.0%) i/s - 1.000 in 5.430217s
Comparison:
divisors : 0.8 i/s
original : 0.6 i/s - 1.47x (± 0.00) slower
simple_division: 0.2 i/s - 4.48x (± 0.00) slower
Testing 10**13..10**14 (10000000000000..100000000000000)
Warming up --------------------------------------
divisors 1.000 i/100ms
original 1.000 i/100ms
Calculating -------------------------------------
divisors 0.206 (± 0.0%) i/s - 1.000 in 4.854847s
original 0.132 (± 0.0%) i/s - 1.000 in 7.557918s
Comparison:
divisors : 0.2 i/s
original : 0.1 i/s - 1.56x (± 0.00) slower
Testing 10**14..10**15 (100000000000000..1000000000000000)
Warming up --------------------------------------
divisors 1.000 i/100ms
original 1.000 i/100ms
Calculating -------------------------------------
divisors 0.186 (± 0.0%) i/s - 1.000 in 5.388732s
original 0.051 (± 0.0%) i/s - 1.000 in 19.516686s
Comparison:
divisors : 0.2 i/s
original : 0.1 i/s - 3.62x (± 0.00) slower
I'm positive to add this feature. But I'm not sure "divisors" is the best name for this.
@mame Can you review this?
The maintainer of this library is @marcandre , so I leave it to him.
The following is just my opinion. I'm not negative against the proposal, but I don't know its practical use case. The proposed implementation runs faster when the number is larger than 10**6, but it runs slower when the number is small. I think we need a good reason to adopt such an algorithm. Is this method used against a larger number than 10**6 in its typical use case? If it is not sure, I personally like the simpler (√n) algorithm.
I'm positive about the feature.
Implementation needs work though. @universato are you up for that?
Thanks to @mame for benchmarking it. A straight approach as he is proposing would also make each_divisor potentially work better.
Tests for divisors are fine, but each_divisor need to check the result at least once without to_a being called.
Naming
In some languages, libraries and web services, the feature is named or called divisors (or each_divisor). So I think divisors is a good general name for it.
| lang or lib e.t.c. | name | divisors of -1 | divisors of 0 |
|---|---|---|---|
| MATLAB | divsors | [1] | 0 |
| Maple | divisors | [1] | [] |
| Walframe | divisors | [1] | Error message(?) |
| mame/prime-faster | each_divisor | [] | [] |
| google/ac-library.cr | each_divisor | ArgumentError | ArgumentError |
| gem divisors | divisors | [1, -1] | nil |
| dCode | divisors | [1] | Error |
Performance
The implementation using prime_division may be relatively difficult to estimate the complexity, but the idea itself is simple and the code is short.
And, Indeed the fist implementation runs slow when the number is smaller than 10**6, I think the impact is not so big. However, it it possible to make it faster against small numbers, so I made it faster.