Найти n-ую цифру после запятой числа Pi (3.14…)

#java #c_sharp #cpp #python

Найти n-ую цифру после запятой числа Пи 
Например вводим 2000 и должен вывести нам то число которое стоит на 2000 месте после
запятой.

Я попробовал сделать на с++ с помощью формулы. но мой код выводит мне 0



вот код:

#include "stdafx.h"
#include 
#include 
using namespace std;
using namespace System;

int main()
{
    int i=0;
    double S=0;
    cout<<"Enter n:";
    cin>>i;
    for(int n=0;n

Ответы
Ответ 1

Вот реализация формулы Чудновского на Python (c) Nick Craig-Wood:

"""
Python3 program to calculate Pi using python long integers, and the
Chudnovsky algorithm

See: http://www.craig-wood.com/nick/articles/pi-chudnovsky/ for more
info

Nick Craig-Wood 
"""

import math
from time import time

def sqrt(n, one):
    """
    Return the square root of n as a fixed point number with the one
    passed in.  It uses a second order Newton-Raphson convgence.  This
    doubles the number of significant figures on each iteration.
    """
    # Use floating point arithmetic to make an initial guess
    floating_point_precision = 10**16
    n_float = float((n * floating_point_precision) // one) / floating_point_precision
    x = (int(floating_point_precision * math.sqrt(n_float)) * one) // floating_point_precision
    n_one = n * one
    while 1:
        x_old = x
        x = (x + n_one // x) // 2
        if x == x_old:
            break
    return x

def pi_chudnovsky(one=1000000):
    """
    Calculate pi using Chudnovsky's series

    This calculates it in fixed point, using the value for one passed in
    """
    k = 1
    a_k = one
    a_sum = one
    b_sum = 0
    C = 640320
    C3_OVER_24 = C**3 // 24
    while 1:
        a_k *= -(6*k-5)*(2*k-1)*(6*k-1)
        a_k //= k*k*k*C3_OVER_24
        a_sum += a_k
        b_sum += k * a_k
        k += 1
        if a_k == 0:
            break
    total = 13591409*a_sum + 545140134*b_sum
    pi = (426880*sqrt(10005*one, one)*one) // total
    return pi

if __name__ == "__main__":
    print(pi_chudnovsky(10**100))
    for log10_digits in range(1,7):
        digits = 10**log10_digits
        one = 10**digits

        start =time()
        pi = pi_chudnovsky(one)
        #print(pi)
        print("chudnovsky: digits",digits,"time",time()-start)


Результат и "timing":

In [29]: str(pi_chudnovsky(10**2000))[-1]
Out[29]: '5'

In [30]: %timeit str(pi_chudnovsky(10**2000))[-1]
1.53 ms ± 91.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


Ответ 2

Рекомендую использовать алгоритм Spigot. Встроенными числовыми типами вы ничего не
добьетесь... Пи - число иррациональное и где-то даже трансцендентное :), так что вычислить
N-ю цифру, не вычисляя предыдущие, вряд ли у вас получится. А double - это в лучшем
случае 18 цифр, и те с накоплением ошибки.

Чтобы ответ не был просто ссылкой - вот быстрый поиск числа "пи" с заданной точностью.
на С++ по этому алгоритму:

#include 
#include 
#include 
#include 

using namespace std;

string Pi(int N)
{
    int M = (N*10+2)/3;
    vector r(M,2);
    string pi;
    pi.reserve(N+1);
    for(int i = 0; i < N; ++i)
    {
        int carry = 0;
        int sum = 0;
        for(int j = M-1; j >= 0; --j)
        {
            r[j] *= 10;
            sum = r[j] + carry;
            int q = sum / (2*j+1);
            r[j]  = sum % (2*j+1);
            carry = q * j;
        }
        r[0] = sum % 10;
        int q = sum / 10;
        if (q >= 10)
        {
            q = q - 10;
            for(int j = pi.length()-1;;--j)
            {
                if (pi[j] == '9')
                    pi[j] = '0';
                else
                {
                    ++pi[j];
                    break;
                }
            }
        }
        pi += ('0' + q);
        if (i== 0) pi += '.';
    }
    return pi;
}

int main(int argc, const char * argv[])
{
    cout << Pi((argc == 1) ? 10 : atoi(argv[1])) << endl;
}


Вот, тут для 2000 знаков в действии.