Calculating Pi in Binary: How Many Decimals Do I Need?

[Priha]

My first topic here.
Here goes
I've written a small program that first calculates pi in decimal and then changes it into binary.
But as you know there's no accurate binary presentation even for 0.1 so I just can't change the whole 20000 decimal representation of pi into binary. I there for calculate x decimals(?) in binary.The question is how many correct decimals do I need in the base 10 form to get x accurate digits in binary form?

 

[CRGreathouse]

One decimal digit has the same expressive power as log_2(10) ~= 3.32 binary digits, and you should have a few spare decimal digits on hand 'just in case'. So 20,000 decimal digits would get you 66,438 bits or so, but I might only report the first 66,400 bits to guard against rounding errors in calculation and the like.

 

[jim mcnamara]

You can also represent numbers in BCD format this is a common way to do it, there is no industry standard like IEEE-754 for floating point storage:

Decimal:    0     1     2     3     4     5     6     7     8     9
BCD:     0000  0001  0010  0011  0100  0101  0110  0111  1000  1001

Each number uses 4 bits, 20000 digits require 80000 bits or 10000 bytes.
There is no loss of precision, as with floating point, but there is massive loss of computing ability. Not even IBM mainfram cpus can natively handle a 10000 byte BCD.

 

[Hurkyl]

Have you really computed pi in decimal? That seems very unusual; are you sure you haven't actually computed pi in binary, but simply (and possibly unwittingly) asked the computer to print the result in decimal?

And for the record

But as you know there's no accurate binary presentation even for 0.1

There is no problem getting a binary presentation for 0.1 to whatever level of precision you want; the thing that's impossible is getting an exact representation with a terminating binary string.

(I think you meant "precise", not "accurate")

 

[Tac-Tics]

It sounds like you're trying to translate the decimal string directly into binary. I'm not sure that's guaranteed to work.

If you want to represent pi with arbitrary precision in a base n, the standard way to do it would be to find a rational number very close to pi, and then convert that rational to an n-ary representation. So, for example, do binary long division on 22/7 = 10110b/111b which would start off 11.001.

Better rational approximations would lead to better binary expansions.

If you have an appropriate series which equals pi in the limit, (probably monotonic ones or series which converge "fast enough" in some other sense) you can calculate the digits out perfectly. That is, if you want to know the k-th digit in the expansion of pi, you simply need to add enough terms (a number of terms dependent on the value of k) of the series together.

Edit:

Also, I should add that decimal expansions are a minefield, suitable only for scientists and accountants! In reality, the number of rationals that you can represent with finite, non-repeating expansions is pretty small. It has to do with the prime factors of the base. Even in decimal, 1/3, 1/6, 1/7, 1/9, 1/11, 1/12, 1/13, 1/14, and 1/15 all repeat indefinitely. But since we're so used to always seeing things either rounded or based on a multiple of 1/2, 1/5, or 1/10, we don't really notice how so many numbers behave like this.

 

[Priha]

Thanks for the answer greathouse
And to Hurkyl I used Java's BigDecimal class to calculate it. So no floats or doubles used.
And yes I meant precise (English is not my native language). I , as you said, am translating the decimal string directly into binary. I'm dividing the string with 2^n and then subtracting 1/2^n based on whether it is dividable. Why wouldn't this work?
I'm using this formula to calculate pi
http://upload.wikimedia.org/math/0/8/e/08ea94b2c5878f0d27f1b867293fb6b0.png

 

[Hurkyl]

Thanks for the answer greathouse
And to Hurkyl I used Java's BigDecimal class to calculate it. So no floats or doubles used.
And yes I meant precise (English is not my native language). I , as you said, am translating the decimal string directly into binary. I'm dividing the string with 2^n and then subtracting 1/2^n based on whether it is dividable. Why wouldn't this work?
I'm using this formula to calculate pi
http://upload.wikimedia.org/math/0/8/e/08ea94b2c5878f0d27f1b867293fb6b0.png

I am 99.9% sure that, internally, BigDecimal is a binary floating point number. (Actually, it's probably written in base 18446744073709551616, but one digit in base 18446744073709551616 is the same thing as 64 binary digits) BigDecimal is an unfortunately chosen name.

 

[HallsofIvy]

You are using words like "precise" and "accurate" in strange ways. You certainly can give either "precise" or "accurate" values of pi whether in decimal or binary by taking enough decimal or binary place to get whatever "precision" or "accuracy" you want.

You cannot give an "exact" value (which appears to be the word you want to use) for pi in either decimal or binary because it is not a rational number: and only rational numbers have terminating or repeating numeric expansions in any integer (or rational) base.

 

[rscosa]

Hi!
the answer to this question, IMPOSSIBLE, because you don't have the whole number in memory but just an approximation of PI, so you can get a very acurate approximation of the approximation of PI :).

 

[HallsofIvy]

Hi!
the answer to this question, IMPOSSIBLE, because you don't have the whole number in memory but just an approximation of PI, so you can get a very acurate approximation of the approximation of PI :).

Since the question was entirely about accuracy, what is it that you are saying is "impossible"?