Skip to content
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.

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

Implementation of wheel factorization #527

Merged
merged 3 commits into from
Dec 1, 2023

Conversation

avadov
Copy link
Contributor

@avadov avadov commented Nov 30, 2023

Also, it fixes the bug of skipping the first two numbers after n. For example, in the previous version:

galois.next_prime(100000034)
100000037
galois.next_prime(100000035)
100000039
galois.next_prime(100000036)
100000039
galois.next_prime(100000037)
100000049

Also, it fixes the bug of skipping the first two numbers after n. For example, in the previous version:

>>> galois.next_prime(100000034)
100000037

>>> galois.next_prime(100000035)
100000039

>>> galois.next_prime(100000036)
100000039

>>> galois.next_prime(100000037)
100000049
@avadov
Copy link
Contributor Author

avadov commented Nov 30, 2023

By the way, I was trying to implement progressive expansion of the primes list. The primes(n) function exhausts all RAM with n=10^10. This limitation can be bypassed by alternative techniques. But would such a long primes list be useful? Say, finding all primes <= 10^11?

@mhostetter mhostetter linked an issue Dec 1, 2023 that may be closed by this pull request
@mhostetter
Copy link
Owner

I pushed up small changes to appease the formatter. I also added a unit test for the bug you identified and fixed. Thanks!

By the way, I was trying to implement progressive expansion of the primes list. The primes(n) function exhausts all RAM with n=10^10. This limitation can be bypassed by alternative techniques. But would such a long primes list be useful? Say, finding all primes <= 10^11?

I also thought about dynamically expanding the primes table. Do you think that would have utility? I don't want to blow up the memory (without the user knowing). Do you have a working prototype to share? Feel free to open a separate pull request and we can discuss / test it.

@mhostetter mhostetter added the bug Something isn't working label Dec 1, 2023
Copy link

codecov bot commented Dec 1, 2023

Codecov Report

Attention: 13 lines in your changes are missing coverage. Please review.

Comparison is base (9b41a86) 96.23% compared to head (ae6f858) 96.23%.

Files Patch % Lines
src/galois/_prime.py 50.00% 13 Missing ⚠️
Additional details and impacted files
@@                Coverage Diff                @@
##           release/0.3.x     #527      +/-   ##
=================================================
- Coverage          96.23%   96.23%   -0.01%     
=================================================
  Files                 46       46              
  Lines               5903     5917      +14     
=================================================
+ Hits                5681     5694      +13     
- Misses               222      223       +1     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@mhostetter mhostetter merged commit 50c394c into mhostetter:release/0.3.x Dec 1, 2023
44 checks passed
@mhostetter mhostetter added bug-fix Fixes a reported bug and removed bug Something isn't working labels Dec 1, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug-fix Fixes a reported bug
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Incorrect values in next_prime()
2 participants