Project

General

Profile

Feature #12676

Updated by nobu (Nobuyoshi Nakada) over 3 years ago

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.


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

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.


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.


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

end
pv << value if value > 1

pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] }

end

```

Back