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