```Issue #12676 has been updated by Marc-Andre Lafortune.

I thought I was quite clear, but I will try to be clearer.

`n.prime_divison` returns a factorization of `n` such that when you take their product of the powers you get back `n`. Trying to express this mathematically:

n =   f_i ^ p_i

Where` f_i` is either -1 , 1 or a prime, `p_i` is positive integer. We could allow `f_i` to be 0 and `p_i` to be 1 in case `n == 0` instead of raising (i.e. returning `[[0, 1]]`, but certainly not `[]`, which would give a product of 1 (https://en.wikipedia.org/wiki/Product_(mathematics)#Empty_product). This is why the current library provides a factorization that I consider correct for negative integers:

-8.prime_division # => [[-1, 1], [2, 3]]
(-1 ** 1) * (2 ** 3) # => -8, which is the desired result

So I don't see a compelling reason for results for negative numbers to change, so it would be nice if you adapted your code to conform to this, otherwise I'll do it.

Also, as stated, `require 'openssl'` is not acceptable in `lib/prime.rb`, but it would be fine to take advantage of it if it is loaded, and documentation should mention that.

Finally, I just listed all the conditions that must be met, I didn't mean that your proposal didn't meet any of them, just some of them. In particular I never meant to imply that your solution wouldn't be faster.

----------------------------------------
Feature #12676: Significant performance increase, and code conciseness, for prime_division method in prime.rb
https://bugs.ruby-lang.org/issues/12676#change-60798

* Author: Jabari Zakiya
* Status: Assigned
* Priority: Normal
* Assignee: Marc-Andre Lafortune
----------------------------------------
I earlier posted code to simplify the prime_division method in prime.rb.
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/

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
```