Skip to content

/ Python

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

Bbp formula #1989

Open
wants to merge 12 commits into
base: master
from
Open

Bbp formula #1989

wants to merge 12 commits into from

Conversation

@ken437
Copy link
Contributor

ken437 commented May 16, 2020

Describe your change:

Adds an algorithm that approximates pi using the Bailey-Borwein-Plouffe formula, described at https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula

  • Add an algorithm?
  • Fix a bug or typo in an existing algorithm?
  • Documentation change?

Checklist:

  • I have read CONTRIBUTING.md.
  • This pull request is all my own work -- I have not plagiarized.
  • I know that pull requests will not be merged if they fail the automated tests.
  • This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
  • All new Python files are placed inside an existing directory.
  • All filenames are in all lowercase characters with no spaces or dashes.
  • All functions and variable names follow Python naming conventions.
  • All function parameters and return values are annotated with Python type hints.
  • All functions have doctests that pass the automated testing.
  • All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
  • If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.
ken437 and others added 11 commits May 15, 2020
@ken437
Added file aliquot_sum.py containing a function to find theo
4bf73aa
@ken437
Added parameter type info to aliquot_sum.py
Loading status checks…
245369f
@ken437 @cclauss
Update maths/aliquot_sum.py
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
05b344f 
Co-authored-by: Christian Clauss <cclauss@me.com>
@ken437 @cclauss
Update maths/aliquot_sum.py
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
e014506 
Co-authored-by: Christian Clauss <cclauss@me.com>
@ken437
Updated code to raise ValueErrors if input is bad
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
a8a04df
@ken437
Fixed logical operators
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
357695c
@ken437
Removed unnecessary import
Verified
This commit was created on GitHub.com and signed with a verified signature using GitHub’s key.
GPG key ID: 4AEE18F83AFDEB23 Learn about signing commits
Loading status checks…
1e2ba33
@ken437
Updated aliquot_sum.py
Loading status checks…
2a11167
@ken437
fixed formatting
Loading status checks…
eb79bdd
@ken437
fixed documentation
Loading status checks…
366b5e8
@ken437
added bbp_formula.py
Loading status checks…
a76a21c
@ken437
Copy link
Contributor Author

ken437 commented May 16, 2020

I didn't intend to include aliquot_sum.py in the pull request but it was added for some reason. Is there a way to make my pull request only include the addition of bbp_formula.py?
@TheSuperNoob
Copy link
Contributor

TheSuperNoob commented May 16, 2020 •
edited by cclauss

This is pretty cool! One issue with this implementation however:

Currently it is limited to Python’s standard double precision calculation. Which means regardless of how many iterations you supply you function with it will not get any more precise than that. To get around this we can use Python’s builtin module Decimal which allows for arbitrary precision.

One note about the formula itself:

This is mainly used for finding the n-th number of pi without needing to calculate any of the previous digits! Which means we can efficiently calculate the 1 billionth digit of pi without needing to know the digits leading up to that one. So maybe another PR can be opened using with this same file but implements a new function called nth_digit_of_pi() or something similar to more fully explore the power of this formula.
@TheSuperNoob
TheSuperNoob reviewed May 16, 2020
View changes
maths/bbp_formula.py Outdated
# num_iterations + 1 because sum notation includes the last term
for index in range(num_iterations + 1):
Comment on lines 32 to 33

This comment has been minimized.

Sign in to view
Copy link
@TheSuperNoob

TheSuperNoob May 16, 2020

Contributor

I'm not sure the + 1 part actually is needed. By definition this is an infinite sum which just gets more and more accurate with each iteration, so anytime you stop is technically the last iteration :)
And it might fit better to how you define num_iterations as well. As an example, default value for num_iterations is 1000, and starting with 0 and ending with 999 gives you a total of 1000 iterations.

Very minor detail though and shouldn't affect the final result.

This comment has been minimized.

Sign in to view
Copy link
@ken437

ken437 May 17, 2020

Author Contributor

I tried to design it so that num_iterations represented the number on top of the sigma expression in the formula. Now that I think about it, though, it might have been better to name the variable something like upper_limit_of_summation rather than num_iterations
@cclauss
Copy link
Member

cclauss commented May 17, 2020

I didn't intend to include aliquot_sum.py

Rebase this branch on master.
@ken437
Copy link
Contributor Author

ken437 commented May 17, 2020

This is pretty cool! One issue with this implementation however:

Currently it is limited to Python’s standard double precision calculation. Which means regardless of how many iterations you supply you function with it will not get any more precise than that. To get around this we can use Python’s builtin module Decimal which allows for arbitrary precision.

One note about the formula itself:

This is mainly used for finding the n-th number of pi without needing to calculate any of the previous digits! Which means we can efficiently calculate the 1 billionth digit of pi without needing to know the digits leading up to that one. So maybe another PR can be opened using with this same file but implements a new function called nth_digit_of_pi() or something similar to more fully explore the power of this formula.

The first paragraph definitely sounds like a good idea. Maybe I could even let the user input the number of digits after the decimal point to round to (e.g. if they input "2" they get 3.14). As for the second paragraph, I could definitely do that in another pull request; I think it would be cool if our repository had an efficient general pi algorithm in one file and a digit extraction algorithm in another file.
@TheSuperNoob
Copy link
Contributor

TheSuperNoob commented May 17, 2020

The first paragraph definitely sounds like a good idea. Maybe I could even let the user input the number of digits after the decimal point to round to (e.g. if they input "2" they get 3.14).

Yes you can do this! From what i can tell each iteration of this formula gives 1 digit of pi so theres not a whole lot you need to change, only update the calculations to be of type Decimal where the precision is equal to the number of iterations you do. :)

I think it would be cool if our repository had an efficient general pi algorithm in one file and a digit extraction algorithm in another file.

I have already in the past implemented Chudnovsky's algorithm which is as far as im aware the most efficiant method of calculating many digits of pi. chudnovsky_algorithm.py
this yields around 14 digits of pi each iteration.
@ken437
modified bbp_formula.py to use a digit extraction formula
Loading status checks…
d70e86d
@TheSuperNoob
Copy link
Contributor

TheSuperNoob commented May 22, 2020

I assume this revision is abandoned in favor of #1996?
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@TheSuperNoob TheSuperNoob

At least 1 approving review is required to merge this pull request.

Assignees
No one assigned
Labels
automated tests are failing
Projects
None yet
Milestone
No milestone
Linked issues

Successfully merging this pull request may close these issues.

None yet

3 participants
@ken437 @TheSuperNoob @cclauss
You can’t perform that action at this time.