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

Should frobenius_map powers be unrolled #209

Open
ValarDragon opened this issue Feb 6, 2021 · 3 comments
Open

Should frobenius_map powers be unrolled #209

ValarDragon opened this issue Feb 6, 2021 · 3 comments
Labels
D-medium Difficulty: medium P-low Priority: low T-design Type: discuss API design and/or research T-performance Type: performance improvements

Comments

@ValarDragon
Copy link
Member

ValarDragon commented Feb 6, 2021

Currently we have a method fe.frobenius_map(power), which computes a given power of a frobenius map. This involves multiplying a field element by frobenius coefficient. In many instances, these frobenius coefficients are 1, -1, however we resort to general multiplication in these cases.

The frobenius map power is almost always known at compile time, (and as far as I can tell only ranges between 0,1,2,3 in usage within the library), so we could switch this for a potential #206 optimization if we change the API to have different functions for different frobenius powers, or have a macro of some sort for computing this when the power is known at compile time.

This is potentially a notable speedup to the pairing

@ValarDragon ValarDragon added the T-performance Type: performance improvements label Feb 6, 2021
@Pratyush
Copy link
Member

Pratyush commented Feb 6, 2021

This is a good point, but I dunno how much we can save, because we only call the frobenius map a few times. I also don't know a good way to make the test for smallness cheap (at least for -1; for 0 and 1 it's easy).

@ValarDragon
Copy link
Member Author

ValarDragon commented Feb 6, 2021

These are known at compile time, so theres no run time test needed with an API change. (The coefficient is a constant)

@ValarDragon
Copy link
Member Author

Agreed that its probably not that notable on a second pass through, its called like 4 times for bls12

@Pratyush Pratyush added D-medium Difficulty: medium P-low Priority: low T-design Type: discuss API design and/or research labels Sep 9, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
D-medium Difficulty: medium P-low Priority: low T-design Type: discuss API design and/or research T-performance Type: performance improvements
Projects
None yet
Development

No branches or pull requests

2 participants