search

SpectralSequences / sseq

The root repository for the SpectralSequences project.
Apache License 2.0
25 stars 10 forks source link

Upgrade `fp` to work with primes up to 2^31 #145

Closed JoeyBF closed 8 months ago

JoeyBF commented 10 months ago

I moved from having FpVectorP be generic over u32's to generic over types that implement the new Prime trait. I also moved all the prime logic in a new module. This has the advantage of letting us treat ValidPrime as a legitimate prime number, so the FpVector enum can have it as one of its branches.

~We currently only support primes up to 2^16, because otherwise p * (p-1) would overflow a u32.~ It seems that there is a 10% performance loss for primes 2-7, at least up to matrices of size 500x500 or so. I believe that the performance difference is negligible past that size, but it's hard to benchmark in that range.

Looking ahead, I think this will make moving to arbitrary finite fields easier. I imagine that we will further replace the P: Prime generic by an FQ: Field generic, and put a field abstraction layer in between primes and vectors.

Would fix #124

Edit: I just pushed a relatively small change that allows us to support primes up to 2^31.

JoeyBF commented 8 months ago

No problem! I agree that it's a big diff, but I didn't find a natural way to break it into multiple PRs. This will pay off though, since the prime-power field implementation is just around the corner!