Project

General

Profile

Actions

Feature #12676

open

Significant performance increase, and code conciseness, for prime_division method in prime.rb

Added by jzakiya (Jabari Zakiya) over 7 years ago. Updated over 7 years ago.

Status:
Assigned
Target version:
-
[ruby-core:76868]

Description

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
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.

    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.

    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.

    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
    
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0