Skip to content

Make cycle_length code, docs and tests consistent #25923

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 2 commits into from
Nov 25, 2023
Merged

Make cycle_length code, docs and tests consistent #25923

merged 2 commits into from
Nov 25, 2023

Conversation

coreycerovsek
Copy link
Contributor

@coreycerovsek coreycerovsek commented Nov 23, 2023 •
edited
Loading

Fixes #25922.

Docs, code and examples were inconsistent, and cycle_length worked on the sequence $(f(x_0), f(f(x_0)), \dots)$ rather than $(x_0, f(x_0), \dots)$ as per the description of Brent's method in the cited Wikipedia article. This commit aligns everything with the latter convention and also updates the docstring for pollard_rho, which references cycle_length.

  • ntheory
    • Made cycle_length docs and behaviour consistent with each other and with cited
      Wikipedia description of Brent's method

@coreycerovsek
Make cycle_length code, docs and tests consistent
c809531 
Docs, code and examples were inconsistent, and `cycle_length` worked on
the sequence (f(x0), f(f(x0)), ...) rather than (x0, f(x0), ...) as per
the description of Brent's method in the cited Wikipedia article. This
commit aligns everything with the latter convention and also updates the
docstring for `pollard_rho`, which references `cycle_length`.

Fixes #25922.
@coreycerovsek
Update .mailmap
c1c23fc
@sympy-bot
Copy link

sympy-bot commented Nov 23, 2023 •
edited
Loading

✅

Hi, I am the SymPy bot. I'm here to help you write a release notes entry. Please read the guide on how to write release notes.

Your release notes are in good order.

Here is what the release notes will look like:

  • ntheory
    • Made cycle_length docs and behaviour consistent with each other and with cited
      Wikipedia description of Brent's method (#25923 by @coreycerovsek)

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.13.

Click here to see the pull request description that was parsed. 
Fixes #25922.

Docs, code and examples were inconsistent, and `cycle_length` worked on the sequence $(f(x_0), f(f(x_0)), \dots)$ rather than $(x_0, f(x_0), \dots)$ as per the description of Brent's method in the cited Wikipedia article. This commit aligns everything with the latter convention and also updates the docstring for `pollard_rho`, which references `cycle_length`.

<!-- BEGIN RELEASE NOTES -->
* ntheory
  * Made cycle_length docs and behaviour consistent with each other and with cited
  Wikipedia description of Brent's method
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

@coreycerovsek coreycerovsek mentioned this pull request Nov 23, 2023
Closed
@github-actions GitHub Actions
Copy link

Benchmark results from GitHub Actions

Lower numbers are good, higher numbers are bad. A ratio less than 1
means a speed up and greater than 1 means a slowdown. Green lines
beginning with + are slowdowns (the PR is slower then master or
master is slower than the previous release). Red lines beginning
with - are speedups.

Significantly changed benchmark results (PR vs master)



Significantly changed benchmark results (master vs previous release)


| Change   | Before [a00718ba]    | After [69d3af72]    |   Ratio | Benchmark (Parameter)                                                |
|----------|----------------------|---------------------|---------|----------------------------------------------------------------------|
| -        | 69.3±2ms             | 43.7±0.4ms          |    0.63 | integrate.TimeIntegrationRisch02.time_doit(10)                       |
| -        | 67.9±0.6ms           | 43.6±0.2ms          |    0.64 | integrate.TimeIntegrationRisch02.time_doit_risch(10)                 |
| +        | 18.2±0.2μs           | 30.1±0.3μs          |    1.66 | integrate.TimeIntegrationRisch03.time_doit(1)                        |
| -        | 5.53±0.02ms          | 2.83±0.03ms         |    0.51 | logic.LogicSuite.time_load_file                                      |
| -        | 72.3±0.2ms           | 28.8±0.09ms         |    0.4  | polys.TimeGCD_GaussInt.time_op(1, 'dense')                           |
| -        | 25.8±0.2ms           | 16.9±0.07ms         |    0.65 | polys.TimeGCD_GaussInt.time_op(1, 'expr')                            |
| -        | 72.4±1ms             | 28.8±0.1ms          |    0.4  | polys.TimeGCD_GaussInt.time_op(1, 'sparse')                          |
| -        | 254±2ms              | 124±0.4ms           |    0.49 | polys.TimeGCD_GaussInt.time_op(2, 'dense')                           |
| -        | 250±2ms              | 125±0.6ms           |    0.5  | polys.TimeGCD_GaussInt.time_op(2, 'sparse')                          |
| -        | 646±4ms              | 375±2ms             |    0.58 | polys.TimeGCD_GaussInt.time_op(3, 'dense')                           |
| -        | 659±7ms              | 374±1ms             |    0.57 | polys.TimeGCD_GaussInt.time_op(3, 'sparse')                          |
| -        | 491±2μs              | 287±1μs             |    0.59 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(1, 'dense')            |
| -        | 1.80±0.01ms          | 1.05±0.01ms         |    0.58 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(2, 'dense')            |
| -        | 5.72±0.03ms          | 3.08±0.01ms         |    0.54 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(3, 'dense')            |
| -        | 451±2μs              | 229±1μs             |    0.51 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(1, 'dense')               |
| -        | 1.48±0ms             | 663±3μs             |    0.45 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(2, 'dense')               |
| -        | 4.83±0.02ms          | 1.65±0.01ms         |    0.34 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(3, 'dense')               |
| -        | 374±2μs              | 202±0.8μs           |    0.54 | polys.TimeGCD_SparseGCDHighDegree.time_op(1, 'dense')                |
| -        | 2.42±0.01ms          | 1.22±0ms            |    0.5  | polys.TimeGCD_SparseGCDHighDegree.time_op(3, 'dense')                |
| -        | 10.2±0.04ms          | 4.27±0.03ms         |    0.42 | polys.TimeGCD_SparseGCDHighDegree.time_op(5, 'dense')                |
| -        | 356±2μs              | 167±2μs             |    0.47 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(1, 'dense')            |
| -        | 2.49±0.01ms          | 881±5μs             |    0.35 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(3, 'dense')            |
| -        | 9.51±0.05ms          | 2.62±0.01ms         |    0.28 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(5, 'dense')            |
| -        | 998±10μs             | 428±5μs             |    0.43 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'dense')           |
| -        | 1.69±0ms             | 508±2μs             |    0.3  | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'sparse')          |
| -        | 5.62±0.02ms          | 1.78±0.01ms         |    0.32 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'dense')           |
| -        | 8.28±0.05ms          | 1.50±0ms            |    0.18 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'sparse')          |
| -        | 285±0.9μs            | 63.3±0.7μs          |    0.22 | polys.TimePREM_QuadraticNonMonicGCD.time_op(1, 'sparse')             |
| -        | 3.37±0.04ms          | 396±3μs             |    0.12 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'dense')              |
| -        | 3.87±0.02ms          | 277±0.8μs           |    0.07 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'sparse')             |
| -        | 6.70±0.1ms           | 1.24±0.01ms         |    0.19 | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'dense')              |
| -        | 8.56±0.02ms          | 837±2μs             |    0.1  | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'sparse')             |
| -        | 5.06±0.08ms          | 2.99±0ms            |    0.59 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(2, 'sparse') |
| -        | 11.8±0.1ms           | 6.42±0.03ms         |    0.54 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'dense')  |
| -        | 22.6±0.08ms          | 9.16±0.05ms         |    0.41 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'sparse') |
| -        | 5.36±0.01ms          | 868±5μs             |    0.16 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(1, 'sparse')    |
| -        | 12.7±0.07ms          | 7.03±0.01ms         |    0.55 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(2, 'sparse')    |
| -        | 100±0.6ms            | 25.7±0.2ms          |    0.26 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'dense')     |
| -        | 165±0.3ms            | 54.8±0.3ms          |    0.33 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'sparse')    |
| -        | 176±1μs              | 112±0.4μs           |    0.64 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(1, 'dense')      |
| -        | 369±7μs              | 213±0.7μs           |    0.58 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(1, 'sparse')     |
| -        | 4.20±0.02ms          | 841±4μs             |    0.2  | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'dense')      |
| -        | 5.19±0.03ms          | 378±2μs             |    0.07 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'sparse')     |
| -        | 19.2±0.05ms          | 2.76±0.01ms         |    0.14 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'dense')      |
| -        | 21.9±0.2ms           | 628±7μs             |    0.03 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'sparse')     |
| -        | 489±1μs              | 133±0.6μs           |    0.27 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(1, 'sparse') |
| -        | 4.57±0.01ms          | 608±3μs             |    0.13 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'dense')  |
| -        | 5.34±0.02ms          | 137±0.9μs           |    0.03 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'sparse') |
| -        | 12.9±0.1ms           | 1.28±0.01ms         |    0.1  | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'dense')  |
| -        | 13.4±0.03ms          | 138±0.9μs           |    0.01 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'sparse') |
| -        | 135±1μs              | 74.9±0.2μs          |    0.55 | solve.TimeMatrixOperations.time_rref(3, 0)                           |
| -        | 260±0.4μs            | 88.1±0.4μs          |    0.34 | solve.TimeMatrixOperations.time_rref(4, 0)                           |
| -        | 24.1±0.2ms           | 10.2±0.1ms          |    0.42 | solve.TimeSolveLinSys189x49.time_solve_lin_sys                       |



Full benchmark results can be found as artifacts in GitHub Actions

(click on checks at the top of the PR).

      		
    

  





        


            

            
            

              
            

        

      


      

            
  
  

    
  
    
    

  

  

  


    












      

  
      



  

  @haru-44





  



    

      

  

    

        
    
    

  


      
          
  
      
            Copy link

  

      
    

  


  

      

  
  Member


      

  


  

    

      

      
            haru-44
  

      

      

      commented


        Nov 24, 2023


      
    


  





      


        



  
    

      
          
looks good

      		
    

  





        


            

            
            

              
            

        

      


      

            
  
  

    
  
    
    

  

  

  


    












      

  
      



  

  @oscarbenjamin





  



    

      

  

    

        
    
    

  


      
          
  
      
            Copy link

  

      
    

  


  

      

  
    Collaborator


      

  


  

    

  





      


        



  
    

      
          
@haru-44 I have added you to the SymPy GitHub organisation. If you accept the invite then you can merge this.


I would send you an email to discuss this but we don't seem to have any email address for you:



  

    

      sympy/.mailmap
    

    

         Line 1539
      in
      69d3af7
    

  

  

    


        

          
           haru-44 <36563693+haru-44@users.noreply.github.com> 
        

    

  






Can you send me an email? My address is in the .mailmap file.

      		
    

  





        


            

            
            

              
            

        

      


      

            
  
  

    
  
    
    

  

  

  


    












      

  
            







      

  
      



  

  @haru-44





  



    

      

  

    

        
    
    

  


      
          
  
      
            Copy link

  

      
    

  


  

      

  
  Member


      

  


  

    

      

      
            haru-44
  

      

      

      commented


        Nov 25, 2023


      
    


  





      


        



  
    

      
          
@oscarbenjamin

I just sent you an email.

      		
    

  





        


            

            
            

              
            

        

      


      

            
  
  

    
  
    
    

  

  

  


    












      

  
          
 
  

    
  

  



        @haru-44
  haru-44



        merged commit 39594aa
      into

      
  
    sympy:master
  


    Nov 25, 2023

  












      

  
      



  

  @haru-44





  



    

      

  

    

        
    
    

  


      
          
  
      
            Copy link

  

      
    

  


  

      

  
  Member


      

  


  

    

      

      
            haru-44
  

      

      

      commented


        Nov 25, 2023


      
    


  





      


        



  
    

      
          
Thank you for your contribution. Pull requests have been merged.

      		
    

  





        


            

            
            

              
            

        

      


      

            
  
  

    
  
    
    

  

  

  


    












      

  
      



  

  @coreycerovsek





  



    

      

  

    

        
    
    

  


      
          
  
      
            Copy link

  

      
    

  


  

      

  
    Contributor


      

  Author


  


  

    

  





      


        



  
    

      
          
You’re welcome, my pleasure!

      		
    

  





        


            

            
            

              
            

        

      


      

            
  
  

    
  
    
    

  

  

  


    
















  
  

    

      

  




      


    


    

      

        
      

  
    Sign up for free
    to join this conversation on GitHub.
    Already have an account?
    Sign in to comment


  



      

    

  




  
          



      

  

    
    

    

  

    Reviewers
  


    

    No reviews






    

  


      
  

    Assignees
  



        


    No one assigned







      


  


  

    Labels
  



    

      

    ntheory









      

  

    

        

    Projects
  


        




    None yet




  



      


  

    
  

    Milestone
  


      No milestone





    
      
          


  

    

      
        

          
  

    Development
  



            


Successfully merging this pull request may close these issues.



  
          
      cycle_length documentation / behaviour mismatch



  
  



      
    

  




      

    

  
      

  

    

      4 participants
    

    

        
          @coreycerovsek 
        
          @sympy-bot 
        
          @haru-44 
        
          @oscarbenjamin