[Suggestion] Faster trailing method

[oppressionslayer]

I discovered a much faster method to get the shifted value of trailing by using powers of two math to get the same result. The speeds are 1.5x to 3x faster for larger numbers and only 3x slower in 1 in 15 cases, so an overall performance increase:

import random
import math
from sympy.ntheory.factor_ import trailing

def sympysalg(n):
    t = 0
    p = 8
    while not n & 1:
        while not n & ((1 << p) - 1):
            n >>= p
            t += p
            p *= 2
        p //= 2
    return t

def last_powers_of_two_trailing(N):
  orign = N
  if orign < 17: N = N%16
  else: N = N&15
  if N == 1: 
     if ((orign -1) & (orign -2)) == 0: return orign.bit_length()-1
     return sympysalg(orign-1)
  if N in [3, 7, 11, 15]: return 1
  if N in [5, 13]: return 2
  if N == 9: return 3
  return 0

def strailing(N):
   return N>>last_powers_of_two_trailing(N)

or you may use for further speed increases in cases of 1:

def lars_last_powers_of_two_trailing(N):
  p,y=1,2
  orign = N
  if orign < 17: N = N%16
  N = N&15
  if N == 1: 
     if ((orign -1) & (orign -2)) == 0: return orign.bit_length()-1
     while orign&y == 0:
       p+=1
       y<<=1
     return p
  if N in [3, 7, 11, 15]: return 1
  if N in [5, 13]: return 2
  if N == 9: return 3
  return 0

Code for quick testing:

l=2**4999999+1 
h=2**5000000+1 
s = random.randrange(l,h,2) 

import time   
start = time.time()  
a = s >> trailing(s-1) 
end = time.time() 
print(end-start)   
print(f"Operation took {(end-start)/60} minutes")   

import time   
start = time.time()  
b = strailing(s) 
end = time.time() 
print(end-start)   
print(f"Operation took {(end-start)/60} minutes")   
a==b       

Results:

0.0006721019744873047
Operation took 1.1201699574788412e-05 minutes
0.0004048347473144531
Operation took 6.747245788574219e-06 minutes
Out[7321]: True

This is just a suggestion, as the math is faster and code is more concise and the code is more accurate in terms of the math used to determine the result. Feel free to ignore if you don't need these speed increase. This is just a suggestion. There is slight difference in usage as mine does the shift operation with a division in the trailing algorithm. This is a different approach to the problem, as it uses shortcuts of a base 10 to 16 relationship of repeating numbers in that base 10 to 16 relationship. Instead of the Stein Algorithm, i used sympy's algorithm for cases of 1 Again, just a suggestion and some support for it's use if you would like the speed increase, feel free to use. It is slower 1 in 15 tries ,but i think the performance gain 1.5x to 3x of the other 15 numbers outweighs the 3x slower of the 1 in 15.

In the case someone wants to build the powers of two path down a number that's over a million digits long, the performance enhancements may be helpful. I used the algorithm above to build that for A Million Random Digits from the RAND corporation and it finished rather quickly.

[asmeurer]

Please use ``` to format your code (see https://guides.github.com/features/mastering-markdown/). Otherwise it removes the indentation and isn't readable.

[oppressionslayer]

ok, i added those

[oppressionslayer]

At second look this isn't faster, but the code is more concise. I'll post again if i find a faster method

[oppressionslayer]

I updated the orignal post with a faster algorithm and updated the description. This is just to show that a refactor can lead to faster results using a shortcut in a base 10 to 16 relationship of repeating trailing numbers. Something you may or may not be interested in, but maybe the performance gains are so i wanted to share

[oscarbenjamin]

I see that trailing is used in a number of other functions like perfect_power and some prime testing routines. Does this lead to a measurable speed up in any of those?

[smichr]

@haru-44 , you already made changes. Should this issue be closed?

[haru-44]

I think it is good to close. Essentially, I think small_trailing implements this suggestion.

[oppressionslayer]

Most definitely!

On Tue, Sep 19, 2023, 7:41 AM haru-44 @.***> wrote:

I think it is good to close. Essentially, I think small_trailing implements this suggestion.

— Reply to this email directly, view it on GitHub https://github.com/sympy/sympy/issues/20014#issuecomment-1725469484, or unsubscribe https://github.com/notifications/unsubscribe-auth/AI35AJHMKQPDEQN7MFJULMTX3GOG3ANCNFSM4QOSTXMA . You are receiving this because you modified the open/close state.Message ID: @.***>