Arbitrary precision arithmetic with GMP

问题:

I'm using the GMP library to make a Pi program, that will calculate about 7 trillion digits of Pi. Problem is, I can't figure out how many bits are needed to hold that many decimal places.

回答1:

7 trillion digits can represent any of 10^(7 trillion) distinct numbers.

x bits can represent 2^x distinct numbers.

So you want to solve:

2^x = 10^7000000000000

Take the log-base-2 of both sides:

x = log2(10^7000000000000)

Recall that log(a^b) = b * log(a):

x = 7000000000000 * log2(10)

I get 23253496664212 bits. I would add one or two more just to be safe. Good luck finding the petabytes to hold them, though.

I suspect you are going to need a more interesting algorithm.

回答2:

I wanna just correct one thing about what was written in the response answer:

Recall that log(a^b) = a * log(b)

well it is the opposite :

log(a^b) = b * log(a)

回答3:

2^10 = 1024, so ten bits will represent slightly more than three digits. Since you're talking about 7 trillion digits, that would be something like 23 trillion bits, or about 3 terabytes, which is more than I could get on one drive from Costco last I visited.

You may be getting overambitious. I'd wonder about the I/O time to read and write entire disks for each operation.

(The mathematical way to solve it is to use logarithms, since a number that takes 7 trillion digits to represent has a log base 10 of about 7 trillion. Find the log of the number in the existing base, convert the base, and you've got your answer. For shorthand between base 2 and base 10, use ten bits==three digits, because that's not very far wrong. It says that the log base 10 of 2 is .3, when it's actually more like .301.)