1+2+...+n的约数(7) - 设想：我们还可以再快吗？

是的，我们还可以再快吗？我们还可以再快吗？
答案依旧是肯定的！
我们还有可以提高100甚至更多倍的质数求解算法！我们还有”避免重复运算“的重量级武器！

没有coding是完美的，没有做不到的，只有想不到的！

废话少说，让我们分析一下吧：
1. 质数的求解速度我们可以提高！特别是在更大的约数个数需求的时候。
我们可以预先用优化后的求解算法标记出某个范围以内的质数(用mark变量)，然后再需要的时候适当夸大这个运算范围（例如先10000以内，然后[10000, 20000]以内，等等）。当然我们仅仅把需要的质数放在primes的Array里。

代码:

def add_prime(n)    
   @primes << n if @mark[n]
end

不过，这需要很好的控制。

2. 我们并不需要特别地求解质数
注意一下，你就会发现，求解约数的过程和求解质数的过程很相似。
其实，它根本就包含着求解质数的过程。
我们可以省去那一部分的计算！

代码:

count *= 2 if (m != 1)新代码:if (m != 1)
      # @mark[m] = true # 注意这里，m是个质数！！！
      count *= 2
end

3. 重复计算？
是的！还有重复计算！
在num_of_divs_ex函数里，我们可以用循环求解并保存中间的值！

4. 我们可以换种思路吗？
当一种算法山穷水尽的时候，我们可以换种思路吗？
既然求约数个数的过程和求解质数的过程很像，那我们是不是可以用求解质数的优化算法来计算约数个数呢？

我们还可以再快吗？

 

（更多的coding我就不再贴出了）

1+2+...+n的约数(6) - 重体验: 我还可以再快吗？

问题解决的时候，一切都是那么舒爽...
一直以来，写的程序都是为了在限定时间以内运行而努力。
而这次，第一次想把自己的程序速度再进一步。

嗯，回到开始的想法：去除重复运算，用memory换时间
f(n)=n(n+1)/2=n1*n2 (n1=n/2，n2=n+1或者n1=n，n2=(n+1)/2)
因为n，n+1相邻，所以n1与n2之间没有共同的质数约数
n1与n2之间没有共同的质数约数！
也就是说 f(n)的约数个数 = n1的约数个数 × n2的约数个数

而f(n)和f(n+1)都会有个共同的部分 n+1 (或(n+1)/2)
这就是说：我们可以节省这部分重复运算！
这可以节省1/2甚至更多的运算量！

coding如下

代码:

class Divisor
  # primes: [2, 3, 5, 7, ...]
  #attr_accessor :primes, :offset, :memory
  
  def initialize
    @primes = Array.new(1, 2)
    @offset = 3
    @memory = Array.new
  end
  
  def n(num)
    return 1 if (num == 1)
    
    n = 2
    n += 1 while (num_of_divs(n) < num)
    
    return n
  end
  
  # add n if it is a prime
  def add_prime(n)
    sqrt = Math.sqrt(n).to_i    
    @primes.each do |prime|
      break if (prime > sqrt)
      return if (n % prime == 0)
    end
    
    @primes << n
  end
  
  # number of divisors of f(n) = 1 + 2 + ... + n = n(n+1)/2
  def num_of_divs(n)
    n1 = n
    n2 = n +1
    sqrt = Math.sqrt(n2).to_i
    
    # if not added (into primes' list), try to add it,
    if (sqrt >= @offset)
      add_prime(sqrt) 
      @offset += 1  #increase prime offset
    end
    
    # f(n) = n(n+1)/2 could be as multiplication of two numbers, either (n/2) * (n+1) or n * [(n+1)/2]
    if (n1 % 2 == 0)
      n1 /= 2
    else
      n2 /= 2
    end
    
    return num_of_divs_ex(n1) * num_of_divs_ex(n2) 
  end
  
  # number of divisors of n
  def num_of_divs_ex(n)
    return @memory[n] if @memory[n] #return if it is already stored in memory
    
    count = 1
    m = n
    @primes.each do |prime|
      break if (m == 1)
      
      if @memory[m]
        count *= @memory[m]
        @memory[n] = count
        return count
      end
      
      # check whther <prime> is one of divisor of <m>
      tmp = 0
      while (m % prime == 0)
        tmp += 1
        m /= prime
      end
      
      # update <count> if <prime> is one of divisor of <m>
      count *= (tmp + 1) if (tmp > 0)    
    end
    
    count *= 2 if (m != 1)
    @memory[n] = count
    return count
  end
end

start = Time.now
div = Divisor.new
print '->' + div.n(500).to_s + '<-'
final = Time.now
cost =final - start
print 'Cost: ' + cost.to_s

500个约数仅需要0.313s，速度提高了将近3倍...

1+2+...+n的约数(5) - 再回首：一切竟是那么简单

嗯，优化的算法找好了，让我们替换原来的求质函数吧...
等等，我们需要计算n(n+1)/2个质数吗？
汗，一滴滴流了下来。
不需要！答案是勿庸置疑的！

写计算n个质数的算法...
等等，我们需要计算n个质数吗？
又是不需要！
求解sqrt(n)就够了...

天啊，我竟然用了这么多无用的计算...

把新的求质函数放在一旁，改进现有算法:

代码:

class Divisor
  # prime: [2, 3, 5, 7, ...]
  #attr_accessor :primes, :offset
  
  def initialize
    @primes = Array.new(1, 2)
    @offset = 3
  end
  
  def n(num)
    return 1 if (num == 1)
    
    n = 2
    n += 1 while (num_of_divs(n) < num)
    
    return n
  end
  
  # add n if it is a prime
  def add_prime(n)
    sqrt = Math.sqrt(n).to_i    
    @primes.each do |prime|
      break if (prime > sqrt)
      return if (n % prime == 0)
    end
    
    @primes << n
  end
  
  def num_of_divs(n)
    n1 = n
    n2 = n +1
    sqrt = Math.sqrt(n2).to_i
    
    # if not added (into primes' list), try to add it,
    if (sqrt >= @offset)
      add_prime(sqrt) 
      @offset += 1  #increase prime offset
    end
    
    # f(n) = n(n+1)/2 could be as multiplication of two numbers, either (n/2) * (n+1) or n * [(n+1)/2]
    if (n1 % 2 == 0)
      n1 /= 2
    else
      n2 /= 2
    end    count = 1
    @primes.each do |prime|
      # exit the loop when both n1 & n2 are 1
      break if (n1 == 1 && n2 == 1)
      
      # try to use current prime divide n1 & n2
      tmp = 0
      while (n1 % prime == 0)
        tmp += 1
        n1 /= prime
      end
      while (n2 % prime == 0)
        tmp += 1
        n2 /= prime
      end
      
      count *= (tmp + 1) if (tmp > 0)
    end
    
    #if n1 or n2 is not 1, multiple the count by 2 (as current n1 or n2 is a prime)
    count *= 2 if (not n1 == 1)
    count *= 2 if (not n2 == 1)
    
    return count
  end
endstart = Time.now
div = Divisor.new
print '->' + div.n(500).to_s + '<-'
final = Time.now
cost =final - start
print 'Cost: ' + cost.to_s

100个约数需要0.016s，500个约数需要0.828s...
原来...一切都是这么简单...

1+2+...+n的约数(4) - 他山之石：质数的求解优化

他山之石：质数的求解优化

问题到底是出在哪里了呢？
测试啊测试...
毫无疑问，太多的时间浪费在了质数的求解运算上...
那，就去找质数的优化算法吧...

原版算法代码（计算n以内的质数）：

代码:

#generate prime numbers which are not larger than n
def primes(n)
  primes = Array.new
  i = 2
  while (i <= n)
    #check whether a number is prime
    is_prime = true
    sqrt = Math.sqrt(i).to_i
    primes.each do |prime|
      break if (prime > sqrt)
      is_prime = false and break if (i % prime == 0)
    end 
       
    # prime
    primes << i if is_prime
      
    i += 1
  end
    
  return primes
end

嗯...也许我们可以换个思路...每计算得一个质数m，就更新m~n之间的数：
例如划去2m，3m，4m...这些下次都可以不用计算
等等....那些没被划去的不就是质数吗？

优化后的代码如下：

代码:

def primes(n)
  primes = Array.new(1, 2)
  mark = Array.new(n + 1, true)   
  
  max = Math.sqrt(n).to_i    
  i = 3  
  while (i <= n)    
    # not a prime number, go to next iteration
    i += 2 and next if not mark[i]
    
    # smallest marked number => prime number
    primes << i
    
    # unmark the number who is p*@i
    if (i < max)
      j = i * i
      while (j <= n)
        mark[j] = false #if @mark[@j]
        j += i * 2
      end  
    end
    
    i += 2
  end
  
  return primes  
end

结果是喜人的：在同样的环境下，计算1000000内的质数，第二个算法用了1.7s，而第一个算法用了174s

1+2+...+n的约数(3) - 再试: 100个约数1.578s， 150个约数67.7s！！

再试: 100个约数1.578s， 150个约数67.7s！！

计划失败，怎么办呢，还是先分析下问题吧...
1. Array的读写吃了太多的时间
2. 太多没必要的计算...

没必要的计算？对，没必要的计算！
1. f(n-1) ~ f(n)之间的值的约数求解浪费了太多运算量
2. f(n) = n(n+1)/2，其实，我们是可以分成n*[(n+1)/2]或者(n/2)*(n+1)算的，把f(n)分成2部分的积，然后分别求解
例如f(8) = 8*9/2 = 4*9 = (2^2) * (3^2)，即[2, 0] + [0, 2] = [2, 2]

结论?
1. 去除f(n-1) ~ f(n)之间的运算量，改回普通计算方式
2. 把f(n)分成2部分求解

代码见评论。

如前所料，速度果然大大提高，然而，与设想的却差了一大截:
50个约数需要0.437s，100个约数1.578s，150个约数67.7s！！ 500个约数....依旧不敢想象...

---------------------------------

class Divisor
  # prime_list: [2, 3, 5, 7, ...]
  attr_accessor :primes
  
  def initialize
    @primes = Array.new(1, 2)
  end
  
  def n(num)
    return 1 if (num == 1)
    
    n = 2
    n += 1 while num_of_divs(n) < num
    
    return n
  end
  
  # number of divisors of f(n) = 1 + 2 + ... + n = n(n+1)/2
  def num_of_divs(n)
    if (n > 1)
      cur = (n - 1) * n / 2 + 1      
      final = (n + 1) * n /2
      while (cur < final)
        add_prime(cur)
        cur += 1
      end
    end
    
    return num_of_divs_ex(n)
  end
  
  def add_prime(n)
    sqrt = Math.sqrt(n).to_i
    
    # already some primes
    if (not @primes.empty?)
      @primes.each do |prime|
        break if (prime > sqrt)
        return if (n % prime == 0)
      end
    end
    
    @primes << n
  end
  
  # number of divisors of f(n) = 1 + 2 + ... + n = n(n+1)/2
  def num_of_divs_ex(n)
    n1 = n
    n2 = n +1
    sqrt = Math.sqrt(n2).to_i
    
    if (n1 % 2 == 0)
      n1 /= 2
    else
      n2 /= 2
    end

    count = 1
    if (not @primes.empty?)
      @primes.each do |prime|
        break if (n1 == 1 && n2 == 1)
        if (prime > sqrt)
          count *= 2 if (not n1 == 1)
          count *= 2 if (not n2 == 1)
          break
        end
        
        tmp = 0
        while (n1 % prime == 0)
          tmp += 1
          n1 /= prime
        end
        while (n2 % prime == 0)
          tmp += 1
          n2 /= prime
        end
        
        count *= (tmp + 1) if (tmp > 0)
      end
    end
    return count
  end
end

start = Time.now
div = Divisor.new
print '->' + div.n(50).to_s + '<-'
final = Time.now
cost =final - start
print 'Cost: ' + cost.to_s

1+2+...+n的约数(2) - 初试：50个约数0.922s，100个约数14.7s！！

分析下题目吧，很明显，f(n)的约数个数不是随着n的递增而递增的，解的过程是从n=1求起，递增，直到f(n)有超过500个约数，返回n值

f(n)的约数个数怎么求呢？
一个for loop, 从1到f(n)，依次检查起是否为f(n)的约数...
又是很明显的，用这种方法的话可以拿块豆腐把自己撞死了...
也许，这种方法需要若干年才能完成计算吧...

质数，质数...
假设f(n) = (a^i) * (b^j) * (c^k) * ... (a, b, c为质数)
那么f(n)的约数共有(i+1) * (j+1) * (k+1) *...个

提高运算速度最常用的方法是避免重复计算，而最常用的手法则是用memory换时间...
要保存什么内容以提高运算速度呢？
1. 质数是不能缺的，[2, 3, 5, 7, 11, ...]
2. 一个自然数n分解成质数所形成的数组[i, j , k, ...]
例如n = 15 = 3*5可以用[0,1,1]表示，即 n = (2^0) * (3^1) * (5^1)
这样计算2n时我们发现2n=2*n, 于是2n用[1] + [0, 1, 1] = [1, 1, 1]表示

让我们来coding吧。(代码见评论)

 

然而，想象是美好的，结局是残酷的。
测试一下，发现50个约数需要0.922s，100个约数14.7s，500个约数....不敢想象了...
 那个6s的确实够强大....

1+2+...+n的约数(1) - 源起

最近学Ruby, 到处翻着看，在百度贴吧看到这么一个帖子，如下:
*****************************************************************************************************************************
2008-05-26 Ruby 测试题【转载于ruby中文论坛】
F(n) = 1 + 2 + ,..., + n = (1+n)*n/2 
求最小的n，使F(n)拥有超过500个的约数。 

这题求的是最优效率，哎，本人能力有限，我写出来的最快都要半分钟，论坛上一牛人6秒，打击我信心啊~~~~~~
*****************************************************************************************************************************
得，就拿它练练手吧...