FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Add truncate methods to `fmpz_mod_poly` by GiacomoPope · Pull Request #180 · flintlib/python-flint · GitHub

  1. flintlib
  2. python-flint

Repository navigation

Add truncate methods to fmpz_mod_poly - #180

Merged
oscarbenjamin merged 3 commits into
flintlib:masterfrom
GiacomoPope:fmpz_mod_trunc
Aug 12, 2024
ConversationCommits (3)ChecksFiles changed
Merged

Add truncate methods to fmpz_mod_poly#180
oscarbenjamin merged 3 commits into
flintlib:masterfrom
GiacomoPope:fmpz_mod_trunc

Conversation

GiacomoPope commented Aug 12, 2024

Copy link
Copy Markdown
Contributor

This PR adds:

  • equal_trunc
  • add_trunc
  • sub_trunc
  • mul_low
  • mul_high
  • mul_mod
  • pow_trunc

However, the output from mul_high() doesnt match my expectation... I'm not sure it's worth including, unless I'm being stupid.

The truncate pow is definitely nice, the mul mod seems to not offer much speed up.

In [3]: R = fmpz_mod_poly_ctx(2**127 - 1)

In [4]: f = R.random_element(degree=50)

In [5]: g = R.random_element(degree=50)

In [6]: h = R.random_element(degree=10)

In [7]: 

In [7]: (f * g) % h == f.mul_mod(g, h)
Out[7]: True

In [8]: %timeit (f * g) % h
67.2 μs ± 1.32 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [9]: %timeit f.mul_mod(g, h)
65 μs ± 1.01 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [10]: 

In [10]: x = R.gen()

In [11]: mod = x**20

In [12]: %timeit pow(f, 2**20, mod)
217 μs ± 2.27 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [13]: %timeit f.pow_trunc(2**20, 20)
82.2 μs ± 853 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

GiacomoPope changed the title Add truncate methods Add truncate methods to fmpz_mod_poly Aug 12, 2024
oscarbenjamin reviewed Aug 12, 2024
View reviewed changes
Comment thread src/flint/types/fmpz_mod_poly.pyx Outdated
Comment on lines +1650 to +1656
def mul_high(self, other, slong start):
r"""
Returns from coefficients from ``start`` onwards of the multiplication of ``self`` with ``other``

# TODO!!!
#
# Is this expected behaviour? Seems weird.

oscarbenjamin Aug 12, 2024

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

The doc says:

Computes the product of poly1 and poly2 and writes the coefficients from start onwards into the high coefficients of res, the remaining coefficients being arbitrary.

I think that the implementation just decided that it was faster to compute the full product rather than selectively compute the highest coefficients.

I guess we accept and document that or otherwise zero out the lower coefficients:

In [23]: f.mul_high(g, 5)
Out[23]: 13*x^8 + 37*x^7 + 17*x^6 + 138*x^5 + 101*x^4 + 45*x^3 + 19*x^2 + 7*x + 2

In [24]: f.mul_high(g, 5).right_shift(5).left_shift(5)
Out[24]: 13*x^8 + 37*x^7 + 17*x^6 + 138*x^5

GiacomoPope Aug 12, 2024

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

yeah I think my feeling is if we have to implement f.mul_high(g, 5).right_shift(5).left_shift(5) on our side, we should just not have the method? Maybe the output is good for C flint, but for us the output seems not very interesting.

oscarbenjamin Aug 12, 2024

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Maybe it is not worth having. I can imagine wanting the product of the leading terms or the leading coefficients but I'm not sure I when I would particularly want what this function does. It does not look like fmpz_mod_poly_mulhigh is actually used anywhere in Flint itself.

It can also be implemented in a fairly straight-forward way by calling right_shift before multiplying.

oscarbenjamin commented Aug 12, 2024

Copy link
Copy Markdown
Collaborator

the mul mod seems to not offer much speed up.

As far as I can tell all positive characteristic poly types have a mulmod function but in all cases it does literally just compute the multiplication followed by divrem apart from a minor optimisation to not bother with divrem if the degrees are small enough. In python-flint's case that would save a memory allocation over (f * g) % h.

I expect that it is a little faster for very small polynomials by saving the allocation. Probably in the context of python-flint though any saving here really comes from reducing the general Python overhead though:

In [5]: ctx = fmpz_mod_poly_ctx(127)

In [6]: f = ctx([1, 2])

In [7]: g = ctx([3, 4])

In [8]: h = ctx([1, 2, 3])

In [9]: %timeit (f*g)%h
3.11 µs ± 154 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [10]: %timeit f.mulmod(g, h)
1.23 µs ± 3.54 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

A more important question is how useful these functions actually are. There are many functions in flint that make a lot of sense for Flint's internal use but are perhaps not so useful to a user of python-flint especially if it they are trivially implemented using the features already provided.

For each of these functions we should consider what it means for all other types like if we have mulmod for fmpz_mod_poly are we going to have it for fmpq_poly as well?

Ideally we add methods to each type in such a way that there is a consistent set of methods across the different types. Currently fmpz_mod_poly has many more methods than the other poly types.

GiacomoPope commented Aug 12, 2024

Copy link
Copy Markdown
Contributor Author

Currently fmpz_mod_poly has many more methods than the other poly types.

So my plan was to "finish" methods for this type and then use this as a start for fq_default_poly and also updating nmod_poly.

I'm happy to * not* include some of these methods, but you mentioned about the truncation ones in another PR so I threw them all in

oscarbenjamin commented Aug 12, 2024

Copy link
Copy Markdown
Collaborator

my plan was to "finish" methods for this type and then use this as a start for fq_default_poly and also updating nmod_poly

That seems reasonable.

For each operation now we need to consider if it makes sense for the other types though. Also we are probably already beginning to see diminishing returns from adding further methods to fmpz_mod_poly.

The _trunc and _mullow etc methods are actually already exposed in some sense in python-flint because they are used in the series types. That doesn't mean we can't add them to the poly types as well though.

GiacomoPope commented Aug 12, 2024

Copy link
Copy Markdown
Contributor Author

If you're happy with the methods available for fmpz_mod_poly as presented here in this PR my next contribution will be fq_default_poly which will hopefully have all these features as well

oscarbenjamin commented Aug 12, 2024

Copy link
Copy Markdown
Collaborator

This looks good. Thanks

oscarbenjamin merged commit 7660dc7 into flintlib:master Aug 12, 2024

oscarbenjamin commented Aug 12, 2024

Copy link
Copy Markdown
Collaborator

my next contribution will be fq_default_poly

Excellent!

GiacomoPope deleted the fmpz_mod_trunc branch September 2, 2024 15:58
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

oscarbenjamin oscarbenjamin left review comments

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

Back | FazBrowse Home | New Git URL