Why sigma(n) seems not so performant for small n?
 
  
 
  
 
 
 
 
 
 
    
        
        asked 8 years ago  
 
 logomath gravatar image  
 
 
 
 
    
        
        updated 8 years ago  
 
 
 
 
 
When I try to timeit sigma(n):
 
sage:  %timeit
 
sage:  for n in xsrange(1,10000):  c=sigma(n)
 
5 loops, best of 3: 181 ms per loop
 
but it seems much quicker when you directly sum the divisors
 
sage:  %timeit
 
sage:  def s(n): return sum(divisors(n))
 
sage:  for n in xsrange(1,10000): c=s(n)
 
5 loops, best of 3: 44.8 ms per loop
 
The same with sigma(n,k). Why that happens (for relatively small n)?
 
Preview: (hide)
 
 
 
 
          
 
Comments
Finding divisors uses pari, and maybe pari has gotten faster recently, making your version faster. Or more specifically, maybe pari has gotten faster at listing divisors than at factoring -- sigma uses the factor function. That's just a guess, though.
John Palmieri gravatar imageJohn Palmieri (
    
        8 years ago
    )
By the way, as far as I can tell, the code for sigma was last changed in 2007 or so. So it may be time to revisit it.
John Palmieri gravatar imageJohn Palmieri (
    
        8 years ago
    )
Thank you for your hint
logomath gravatar imagelogomath (
    
        8 years ago
    )
add a comment