search

mhostetter / galois

A performant NumPy extension for Galois fields and their applications
https://mhostetter.github.io/galois/
MIT License
338 stars 31 forks source link

Implementation of wheel factorization #527

Closed avadov closed 12 months ago

avadov commented 12 months ago

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 commented 12 months ago

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 commented 12 months ago

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.

codecov[bot] commented 12 months ago

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 :warning:
Additional details and impacted files ```diff @@ 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 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.