How to Calculate Pi without a Calculator?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Re: How to Calculate Pi without a Calculator?

The digits on that thread are not really random, though. Humans are terrible at emulating randomness.

At any rate, if you're willing to get your digits from an outside internet source, you can always get (almost) as many true random digits as you wish at random.org.

commodorejohn
Posts: 1106
Joined: Thu Dec 10, 2009 6:21 pm UTC
Location: Placerville, CA
Contact:

Re: How to Calculate Pi without a Calculator?

PsiCubed wrote:The digits on that thread are not really random, though. Humans are terrible at emulating randomness.

Absolutely. We need to more strictly adhere to the standard randomness!
"'Legacy code' often differs from its suggested alternative by actually working and scaling."
- Bjarne Stroustrup
www.commodorejohn.com - in case you were wondering, which you probably weren't.

LaserGuy
Posts: 4549
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
PsiCubed wrote:
lorb wrote:Also you don't really need many digits. Even NASA uses only 16 digits for the program that controls and stabilizes spacecraft during missions. And that includes some extra digits just to be on the safe side.

Somehow I doubt the OP is asking this for any practical purpose.

If you want "practical", just memorize the number of digits you need in advance. Of-course this answer sucks all the fun out the challenge, but you can't deny that it works.

You are correct.
I want to calculate Pi for three reasons.
I need a predictable number sequence with no patterns.
I am trying to learn some higher math.
I think it would be interesting to see how far I can get.

For a predictable sequence with no patterns (but isn't pi), you could also say, calculate sqrt(2) (or any other sqrt you want). This can be done fairly easily with the divide-and-average method and the algorithm is very efficient.

liberonscien
-ce
Posts: 121
Joined: Thu Jan 21, 2016 7:04 pm UTC
Contact:

Re: How to Calculate Pi without a Calculator?

LaserGuy wrote:
liberonscien wrote:
PsiCubed wrote:
lorb wrote:Also you don't really need many digits. Even NASA uses only 16 digits for the program that controls and stabilizes spacecraft during missions. And that includes some extra digits just to be on the safe side.

Somehow I doubt the OP is asking this for any practical purpose.

If you want "practical", just memorize the number of digits you need in advance. Of-course this answer sucks all the fun out the challenge, but you can't deny that it works.

You are correct.
I want to calculate Pi for three reasons.
I need a predictable number sequence with no patterns.
I am trying to learn some higher math.
I think it would be interesting to see how far I can get.

For a predictable sequence with no patterns (but isn't pi), you could also say, calculate sqrt(2) (or any other sqrt you want). This can be done fairly easily with the divide-and-average method and the algorithm is very efficient.

What is it?
Warning: This user is currently questioning its beliefs. This user offers its sincerest apologies if it accidentally offends another user. This user never offends others on purpose and may accidentally offend other users because it lacks knowledge regarding how to be a normal human.

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3550
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
LaserGuy wrote:For a predictable sequence with no patterns (but isn't pi), you could also say, calculate sqrt(2) (or any other sqrt you want). This can be done fairly easily with the divide-and-average method and the algorithm is very efficient.

What is it?

jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
LaserGuy wrote:
liberonscien wrote:You are correct.
I want to calculate Pi for three reasons.
I need a predictable number sequence with no patterns.
I am trying to learn some higher math.
I think it would be interesting to see how far I can get.

For a predictable sequence with no patterns (but isn't pi), you could also say, calculate sqrt(2) (or any other sqrt you want). This can be done fairly easily with the divide-and-average method and the algorithm is very efficient.

What is it?

Divide and average method:
http://mathforum.org/library/drmath/view/52623.html
It is basically Newton's Method applied to f(x) = x^2 - 2

LaserGuy
Posts: 4549
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
LaserGuy wrote:
liberonscien wrote:
PsiCubed wrote:
lorb wrote:Also you don't really need many digits. Even NASA uses only 16 digits for the program that controls and stabilizes spacecraft during missions. And that includes some extra digits just to be on the safe side.

Somehow I doubt the OP is asking this for any practical purpose.

If you want "practical", just memorize the number of digits you need in advance. Of-course this answer sucks all the fun out the challenge, but you can't deny that it works.

You are correct.
I want to calculate Pi for three reasons.
I need a predictable number sequence with no patterns.
I am trying to learn some higher math.
I think it would be interesting to see how far I can get.

For a predictable sequence with no patterns (but isn't pi), you could also say, calculate sqrt(2) (or any other sqrt you want). This can be done fairly easily with the divide-and-average method and the algorithm is very efficient.

What is it?

Example calculation of sqrt 3:
Guess 2.
Divide into 3: 3/2 = 1.5
Average the two: (2 + 1.5)/2 = 1.75
Guess 1.75
Divide into 3: 3/1.75 = 1.714286571
Average the two: (1.75 + 1.714286571)/2 = 1.732428571
Guess 1.732428571.
Divide into 3: 3/1.732428571 = 1.731673165
Average = 1.732079418

Iterate until you get the precision you want. At this point we're correct to 5 significant digits.

liberonscien
-ce
Posts: 121
Joined: Thu Jan 21, 2016 7:04 pm UTC
Contact:

Re: How to Calculate Pi without a Calculator?

LaserGuy wrote:
liberonscien wrote:
LaserGuy wrote:
liberonscien wrote:
PsiCubed wrote:
lorb wrote:Also you don't really need many digits. Even NASA uses only 16 digits for the program that controls and stabilizes spacecraft during missions. And that includes some extra digits just to be on the safe side.

Somehow I doubt the OP is asking this for any practical purpose.

If you want "practical", just memorize the number of digits you need in advance. Of-course this answer sucks all the fun out the challenge, but you can't deny that it works.

You are correct.
I want to calculate Pi for three reasons.
I need a predictable number sequence with no patterns.
I am trying to learn some higher math.
I think it would be interesting to see how far I can get.

For a predictable sequence with no patterns (but isn't pi), you could also say, calculate sqrt(2) (or any other sqrt you want). This can be done fairly easily with the divide-and-average method and the algorithm is very efficient.

What is it?

Example calculation of sqrt 3:
Guess 2.
Divide into 3: 3/2 = 1.5
Average the two: (2 + 1.5)/2 = 1.75
Guess 1.75
Divide into 3: 3/1.75 = 1.714286571
Average the two: (1.75 + 1.714286571)/2 = 1.732428571
Guess 1.732428571.
Divide into 3: 3/1.732428571 = 1.731673165
Average = 1.732079418

Iterate until you get the precision you want. At this point we're correct to 5 significant digits.

There is an actual algorithm for solving square roots.
Is there one for cube roots?
Warning: This user is currently questioning its beliefs. This user offers its sincerest apologies if it accidentally offends another user. This user never offends others on purpose and may accidentally offend other users because it lacks knowledge regarding how to be a normal human.

jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
LaserGuy wrote:Example calculation of sqrt 3:
Guess 2.
Divide into 3: 3/2 = 1.5
Average the two: (2 + 1.5)/2 = 1.75
Guess 1.75
Divide into 3: 3/1.75 = 1.714286571
Average the two: (1.75 + 1.714286571)/2 = 1.732428571
Guess 1.732428571.
Divide into 3: 3/1.732428571 = 1.731673165
Average = 1.732079418

Iterate until you get the precision you want. At this point we're correct to 5 significant digits.

There is an actual algorithm for solving square roots.
Is there one for cube roots?

Newton's method applied to cube roots gives you a very similar procedure. For square roots you had to average the your guess, x, with n/x to get a better approximation. For cube roots you have to average the three numbers x, x, and n/x2.

For the cube root of 5:
Guess 2.
Divide into 5 twice: 5/2/2 = 1.25
Average the three: (2 + 2 + 1.25)/3 = 1.75
Guess 1.75
Divide into 5 twice: 5/1.75/1.75 = 1.632653061
Average the three: (1.75 + 1.75 + 1.632653061)/3 = 1.710884353
Guess 1.710884353.
Divide into 5 twice: 5/1.710884353/1.710884353 = 1.708160579
Average the three: (1.710884353 + 1.710884353 + 1.708160579)/3 = 1.709976428

Edit:
This is already correct in 5 decimals, almost 6, as the actual cube root is 1.709975946...

gmalivuk
GNU Terry Pratchett
Posts: 26452
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: How to Calculate Pi without a Calculator?

There is also a long-division-like algorithm for square and cube roots.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

liberonscien
-ce
Posts: 121
Joined: Thu Jan 21, 2016 7:04 pm UTC
Contact:

Re: How to Calculate Pi without a Calculator?

gmalivuk wrote:There is also a long-division-like algorithm for square and cube roots.

Would you be willing to post information about it here?
Warning: This user is currently questioning its beliefs. This user offers its sincerest apologies if it accidentally offends another user. This user never offends others on purpose and may accidentally offend other users because it lacks knowledge regarding how to be a normal human.

Drumheller769
Posts: 732
Joined: Mon May 11, 2009 7:46 pm UTC
Location: ♞♞♞

Re: How to Calculate Pi without a Calculator?

Google is pretty good at answering simple questions like that, and would likely be faster than waiting for an answer here.
The Great Hippo wrote:Arguing with the internet is a lot like arguing with a bullet. The internet's chief exports are cute kittens, porn, and Reasons Why You Are Completely Fucking Wrong.

gmalivuk
GNU Terry Pratchett
Posts: 26452
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: How to Calculate Pi without a Calculator?

Yeah, I'm on my phone (and was between classes at that point), so it would be faster for you to just google "square root long division algorithm" than for me to do it and then go to the resulting page, copy the url, and try to paste it here (I say "try" because my phone often has trouble with pasting here).

Class is over now, so http://www.homeschoolmath.net/teaching/ ... orithm.php
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

liberonscien
-ce
Posts: 121
Joined: Thu Jan 21, 2016 7:04 pm UTC
Contact:

Re: How to Calculate Pi without a Calculator?

gmalivuk wrote:Yeah, I'm on my phone (and was between classes at that point), so it would be faster for you to just google "square root long division algorithm" than for me to do it and then go to the resulting page, copy the url, and try to paste it here (I say "try" because my phone often has trouble with pasting here).

Class is over now, so http://www.homeschoolmath.net/teaching/ ... orithm.php

This is interesting.
I notice it appears to, upon my first read, involve some guessing.
This is unfortunate.
Warning: This user is currently questioning its beliefs. This user offers its sincerest apologies if it accidentally offends another user. This user never offends others on purpose and may accidentally offend other users because it lacks knowledge regarding how to be a normal human.

Sizik
Posts: 1215
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
gmalivuk wrote:Yeah, I'm on my phone (and was between classes at that point), so it would be faster for you to just google "square root long division algorithm" than for me to do it and then go to the resulting page, copy the url, and try to paste it here (I say "try" because my phone often has trouble with pasting here).

Class is over now, so http://www.homeschoolmath.net/teaching/ ... orithm.php

This is interesting.
I notice it appears to, upon my first read, involve some guessing.
This is unfortunate.

If you always start with the average of the roots of the previous and next square numbers, you can call it an "initial estimate", rather than a "guess".
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Xanthir
My HERO!!!
Posts: 5319
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

Re: How to Calculate Pi without a Calculator?

And if you really feel like it you can just bake a starting point into the algorithm so there's zero "guessing" at all, it just means you'll spend a few iterations wandering toward the vicinity of the answer rather than starting there in the first place.

The point of the "guess" in these types of algorithms is to just use faster methods (rough estimation) to cut out some of the more tedious algorithm work at the beginning.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: How to Calculate Pi without a Calculator?

Sizik wrote:
liberonscien wrote:
gmalivuk wrote:Yeah, I'm on my phone (and was between classes at that point), so it would be faster for you to just google "square root long division algorithm" than for me to do it and then go to the resulting page, copy the url, and try to paste it here (I say "try" because my phone often has trouble with pasting here).

Class is over now, so http://www.homeschoolmath.net/teaching/ ... orithm.php

This is interesting.
I notice it appears to, upon my first read, involve some guessing.
This is unfortunate.

If you always start with the average of the roots of the previous and next square numbers, you can call it an "initial estimate", rather than a "guess".

liberonscien is referring to the 'long division' type of algorithm that gmalivuk linked to, not the Newton method.
In the example on that page, it involves guessing the largest digit such that 4?*?<=245 (where both ? are replaced by that digit) or the largest digit such that 50?*?<=2000.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: How to Calculate Pi without a Calculator?

In the 50?*?<=2000, and such, you can use division and 1 or 2 multiplications.
It's just (a+x)*x<=b, with x a digit.
I am pretty sure that x=floor(b/a)-1 (with -1 mapped to 0) will always work, but I think that x=floor(b/a) might work sometimes, so unless someone can prove otherwise, that's 2 digits to check.
Floor(a/b) is just integer division, and computers do that pretty fast.

PM 2Ring
Posts: 3647
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
gmalivuk wrote:Yeah, I'm on my phone (and was between classes at that point), so it would be faster for you to just google "square root long division algorithm" than for me to do it and then go to the resulting page, copy the url, and try to paste it here (I say "try" because my phone often has trouble with pasting here).

Class is over now, so http://www.homeschoolmath.net/teaching/ ... orithm.php

This is interesting.
I notice it appears to, upon my first read, involve some guessing.
This is unfortunate.

The fact that you need to make a guess for the next digit always annoyed me about the square root long division algorithm, but the same thing happens in the standard long division algorithm, too. But my main objection to that algorithm is that it's so slow: you only get one digit per loop, whereas with Hero's / Newton's averaging algorithm you can double the number of correct digits on each loop (once it starts converging). If you actually want to use that algorithm to calculate square roots without a calculator I suggest working with fractions rather than decimals. And because it converges so quickly it's ok to round the numbers a little if it makes the computation easier.

Let p/q be an estimate of sqrt(n). Then by the averaging algorithm, a better estimate is
p' / q' = (p/q + nq/p) / 2
Simplifying,
p' / q' = (p² + nq²) / 2pq
So we can let
p' = p² + nq²
and
q' = 2pq

If p' and q' have a common factor, that can be canceled.

liberonscien
-ce
Posts: 121
Joined: Thu Jan 21, 2016 7:04 pm UTC
Contact:

Re: How to Calculate Pi without a Calculator?

Demki wrote:In the 50?*?<=2000, and such, you can use division and 1 or 2 multiplications.
It's just (a+x)*x<=b, with x a digit.
I am pretty sure that x=floor(b/a)-1 (with -1 mapped to 0) will always work, but I think that x=floor(b/a) might work sometimes, so unless someone can prove otherwise, that's 2 digits to check.
Floor(a/b) is just integer division, and computers do that pretty fast.

This thread is about doing the math without electronic devices.
Warning: This user is currently questioning its beliefs. This user offers its sincerest apologies if it accidentally offends another user. This user never offends others on purpose and may accidentally offend other users because it lacks knowledge regarding how to be a normal human.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
Demki wrote:In the 50?*?<=2000, and such, you can use division and 1 or 2 multiplications.
It's just (a+x)*x<=b, with x a digit.
I am pretty sure that x=floor(b/a)-1 (with -1 mapped to 0) will always work, but I think that x=floor(b/a) might work sometimes, so unless someone can prove otherwise, that's 2 digits to check.
Floor(a/b) is just integer division, and computers do that pretty fast.

This thread is about doing the math without electronic devices.

There some simple algorithms you can use with pen and paper to do integer division.

liberonscien
-ce
Posts: 121
Joined: Thu Jan 21, 2016 7:04 pm UTC
Contact:

Re: How to Calculate Pi without a Calculator?

Demki wrote:
liberonscien wrote:
Demki wrote:In the 50?*?<=2000, and such, you can use division and 1 or 2 multiplications.
It's just (a+x)*x<=b, with x a digit.
I am pretty sure that x=floor(b/a)-1 (with -1 mapped to 0) will always work, but I think that x=floor(b/a) might work sometimes, so unless someone can prove otherwise, that's 2 digits to check.
Floor(a/b) is just integer division, and computers do that pretty fast.

This thread is about doing the math without electronic devices.

There some simple algorithms you can use with pen and paper to do integer division.

What does the "floor" mean?
Warning: This user is currently questioning its beliefs. This user offers its sincerest apologies if it accidentally offends another user. This user never offends others on purpose and may accidentally offend other users because it lacks knowledge regarding how to be a normal human.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

Re: How to Calculate Pi without a Calculator?

liberonscien wrote:
Demki wrote:
liberonscien wrote:
Demki wrote:In the 50?*?<=2000, and such, you can use division and 1 or 2 multiplications.
It's just (a+x)*x<=b, with x a digit.
I am pretty sure that x=floor(b/a)-1 (with -1 mapped to 0) will always work, but I think that x=floor(b/a) might work sometimes, so unless someone can prove otherwise, that's 2 digits to check.
Floor(a/b) is just integer division, and computers do that pretty fast.

This thread is about doing the math without electronic devices.

There some simple algorithms you can use with pen and paper to do integer division.

What does the "floor" mean?

Floor function, that is floor(x) is the greatest integer less than or equal to x. You could replace floor(a/b) with a/b if you take / as integer division.

Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3550
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: How to Calculate Pi without a Calculator?

Technically correct, but might just be easiest to say "round down to a whole number", or just remove1 any fractional part.

Mnemonically, for any given real number, the 'floor' tends to be the whole-number boundary below it (number line orientated upwards as greater) and the 'ceiling' is the whole-number boundary above it. Unless you're already on such a boundary, in which case you're there already. Like defining which floor's floor/ceiling applies to a random elevation within a building's elevator shaft2, perhaps.

1 For positive numbers only. For negatives, that gives you the ceiling. See next para, above, for why.

2 *Ahem* Also, makes more sense under UK system of "Ground floor as zero, first floor is above that" rather than First Floor being on the ground as per US convention. (Never mind sometimes esoteric numbering/lettering of multiple basement levels.)

liberonscien
-ce
Posts: 121
Joined: Thu Jan 21, 2016 7:04 pm UTC
Contact:

Re: How to Calculate Pi without a Calculator?

jaap wrote:
Sizik wrote:
liberonscien wrote:
gmalivuk wrote:Yeah, I'm on my phone (and was between classes at that point), so it would be faster for you to just google "square root long division algorithm" than for me to do it and then go to the resulting page, copy the url, and try to paste it here (I say "try" because my phone often has trouble with pasting here).

Class is over now, so http://www.homeschoolmath.net/teaching/ ... orithm.php

This is interesting.
I notice it appears to, upon my first read, involve some guessing.
This is unfortunate.

If you always start with the average of the roots of the previous and next square numbers, you can call it an "initial estimate", rather than a "guess".

liberonscien is referring to the 'long division' type of algorithm that gmalivuk linked to, not the Newton method.
In the example on that page, it involves guessing the largest digit such that 4?*?<=245 (where both ? are replaced by that digit) or the largest digit such that 50?*?<=2000.

I was actually referring to the guess and check method. The other one was perfect.
Warning: This user is currently questioning its beliefs. This user offers its sincerest apologies if it accidentally offends another user. This user never offends others on purpose and may accidentally offend other users because it lacks knowledge regarding how to be a normal human.

Eebster the Great
Posts: 3079
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: How to Calculate Pi without a Calculator?

Soupspoon wrote:2 *Ahem* Also, makes more sense under UK system of "Ground floor as zero, first floor is above that" rather than First Floor being on the ground as per US convention. (Never mind sometimes esoteric numbering/lettering of multiple basement levels.)

It seems like in the U.S., you tend to see the British numbering convention only in upscale, effete establishments that refer to their floors as "levels" and name them variously as (for example) G (ground), L (lobby), M (mezzanine), 3, 4, etc. That is, unless the building decides that "G" means "garage", which is below ground, and now L is the ground floor, M is still mezzanine, and suddenly we're at 3 again, because it's following the U.S. system. And it only gets worse at the 13th floor. It actually just makes it harder to find your way around the building. Either standard is fine, just be explicit, please.

DavidSh
Posts: 132
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: How to Calculate Pi without a Calculator?

in the distant past, Demki wrote:In the 50?*?<=2000, and such, you can use division and 1 or 2 multiplications.
It's just (a+x)*x<=b, with x a digit.
I am pretty sure that x=floor(b/a)-1 (with -1 mapped to 0) will always work, but I think that x=floor(b/a) might work sometimes, so unless someone can prove otherwise, that's 2 digits to check.
Floor(a/b) is just integer division, and computers do that pretty fast.

When calculating the second digit of the square root, you might need to look at x=floor(b/a)-2 or below.
The second step for calculating sqrt(289) is solving (20+x)*x <= 189. floor(189/20) =9, while the correct value for x is 7.
Calculating sqrt(288) is worse. Here the second step is solving (20+x)*x <= 188, floor(188/20)=9, while the correct value for x is now 6.

If I calculate correctly, it's only the second digit where this is an issue -- later digits only require looking at x=floor(b/a) and x=floor(b/a)-1.