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.

Sign up for GitHub

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

Jump to bottom

[Merged by Bors] - feat(data/num/prime): kernel-friendly decision procedure for prime #3525

Closed
wants to merge 5 commits into from
Closed

[Merged by Bors] - feat(data/num/prime): kernel-friendly decision procedure for prime #3525

wants to merge 5 commits into from

Conversation

digama0
Copy link
Member

@digama0 digama0 commented Jul 23, 2020 •
edited
Loading

No description provided.

@urkud
Copy link
Member

urkud commented Jul 23, 2020

I guess lint will ask you to write docstrings on defs. How fast/slow is kernel reduction of nat.prime now? It would be nice to say something like "you may use dec_trivial (am I right about the name?) for nat.prime n goals with n < N" in the docstrings of nat.prime and/or decidable instance.

@digama0
Copy link
Member Author

digama0 commented Jul 23, 2020

nat.prime is still as slow as ever. The discussion on Zulip also requires the to_num class for doing reification to num before calling num.prime instead. This file on its own only provides a quick prover for num.prime itself, meaning you can prove num.prime 617 using dec_trivial but nat.prime 617 requires a rewrite to num.prime first if you want to use the same proof method.

@robertylewis robertylewis added the awaiting-review The author would like community review of the PR label Jul 23, 2020
bryangingechen
bryangingechen approved these changes Jul 23, 2020
View reviewed changes
Copy link
Collaborator

@bryangingechen bryangingechen left a comment

Choose a reason for hiding this comment

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

Should the to_num class be added to mathlib too (in another PR, I guess)? I suppose it won't be used much by folks who don't care about computation, but it might be educational.

src/data/num/prime.lean Show resolved Hide resolved
@digama0
Copy link
Member Author

digama0 commented Jul 24, 2020

@bryangingechen I think it should be in a separate PR if so, and also in a locale because I think the instances might cause problems when used outside their intended use case.

robertylewis
robertylewis reviewed Jul 24, 2020
View reviewed changes
Copy link
Member

@robertylewis robertylewis left a comment

Choose a reason for hiding this comment

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

Besides a bit more in the module doc ("why does this file exist?") this looks good!

src/data/num/prime.lean Outdated
/-!
# Primality for binary natural numbers

Decision procedures for primality on `num`.
Copy link
Member

Choose a reason for hiding this comment

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

Could you write a bit more about the contents and intent of this file?

@robertylewis robertylewis added awaiting-author A reviewer has asked the author a question or requested changes and removed awaiting-review The author would like community review of the PR labels Jul 24, 2020
@robertylewis robertylewis removed the awaiting-author A reviewer has asked the author a question or requested changes label Jul 25, 2020
@robertylewis
Copy link
Member

bors merge

@github-actions github-actions bot added the ready-to-merge All that is left is for bors to build and merge this PR. (Remember you need to say `bors r+`.) label Jul 25, 2020
bors bot pushed a commit that referenced this pull request Jul 25, 2020
@digama0
feat(data/num/prime): kernel-friendly decision procedure for prime (#…
e90c7b9 
…3525)
@bors
Copy link

bors bot commented Jul 25, 2020

Pull request successfully merged into master.

Build succeeded:

@bors bors bot changed the title feat(data/num/prime): kernel-friendly decision procedure for prime [Merged by Bors] - feat(data/num/prime): kernel-friendly decision procedure for prime Jul 25, 2020
@bors bors bot closed this Jul 25, 2020
@bors bors bot deleted the num_prime branch July 25, 2020 11:20
@bryangingechen bryangingechen added the t-meta Tactics, attributes or user commands label Feb 7, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@robertylewis robertylewis robertylewis left review comments

@bryangingechen bryangingechen bryangingechen approved these changes

Assignees
No one assigned
Labels
ready-to-merge All that is left is for bors to build and merge this PR. (Remember you need to say `bors r+`.) t-meta Tactics, attributes or user commands
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

None yet
4 participants
@digama0 @urkud @robertylewis @bryangingechen