SpectralSequences / sseq

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

Introduce non-prime finite fields in `fp` #159

Closed JoeyBF closed 3 months ago

JoeyBF commented 4 months ago

This is in the spirit of #147 and extends it somewhat, but I believe it's a better implementation. We have better ergonomics, as the tests for F_4, F_8, F_16 and F_9 show.

I didn't go for the idea of replacing u32 by other types outside the crate (in this case by FieldElement<Fp<P>>) because this causes issues for typing. One of the goals of FpVector is to hide away the prime, so we would have to do the same for the field elements, but that already seems like too much of an overhead.

JoeyBF commented 3 months ago

Thanks @JoeyBF. Looks to me like performance will be pretty poor, but at least we have it. I wonder whether it might be better not to bitpack at all for these Fq's. Or select the limb size as a power of two bytes (8, 16, or 32). That way, having to pack and unpack all the time should be less wasteful, and more of the steps will work with vector processing...

That's a good point. I think first I'll write some proptests that check vectors over these new fields and then try some benches. Probably good for a followup PR if need be. Good to squash and merge?

hoodmane commented 3 months ago

Yeah, you can merge when ready. Thanks @JoeyBF!

JoeyBF commented 3 months ago

My pleasure! :tada: