Function to find the nth digit of Pi

Question

I have always wanted to find an algorithm that did this. I do not care how slow it is, just as long as it can return the nth digit of Pi:

ex:

size_t piAt(long long int n)
{
}

Preferably, not using an infinite series.

If anyone has a function or class that does this, in C or C++ I'd really be interested in seeing it.

Thanks

Answer 1

This remarkable solution shows how to compute the N^th digit of π in O(N) time and O(log·N) space, and to do so without having to compute all the digits leading up to it.

Oh, and it’s in hex.

If you don’t want to do that, you can do this from the shell easily enough:

% perl -Mbignum=bpi -wle 'print bpi(20)'
3.1415926535897932385

% perl -Mbignum=bpi -wle 'print bpi(50)'
3.1415926535897932384626433832795028841971693993751

% perl -Mbignum=bpi -wle 'print bpi(200)'
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303820

% perl -Mbignum=bpi -wle 'print bpi(1000)'
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420199