Bagaimana cara menghitung angka-angka bilangan irasional satu per satu?

Seperti yang telah disebutkan, Anda perlu mengubah algoritma menjadi algoritma digit demi digit (ada beberapa contoh di Halaman Wikipedia tentang metode penghitungan akar kuadrat) dan gunakan pustaka aritmatika presisi arbitrer untuk melakukan penghitungan (misalnya, GMP).

Dalam cuplikan berikut saya menerapkan algoritma yang disebutkan sebelumnya, menggunakan GMP (tetapi bukan fungsi akar kuadrat yang disediakan perpustakaan). Daripada menghitung satu digit desimal dalam satu waktu, implementasi ini menggunakan basis yang lebih besar, kelipatan 10 terbesar yang muat di dalam unsigned long, sehingga dapat menghasilkan 9 atau 18 digit desimal pada setiap iterasi.

Ia juga menggunakan metode Newton yang diadaptasi untuk menemukan "digit" yang sebenarnya.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gmp.h>

unsigned long max_ul(unsigned long a, unsigned long b)
{
    return a < b ? b : a;   
}

int main(int argc, char *argv[])
{
    // The GMP functions accept 'unsigned long int' values as parameters.
    // The algorithm implemented here can work with bases other than 10,
    // so that it can evaluate more than one decimal digit at a time.
    const unsigned long base = sizeof(unsigned long) > 4
                             ? 1000000000000000000
                             : 1000000000;
    const unsigned long decimals_per_digit = sizeof(unsigned long) > 4 ? 18 : 9;

    // Extract the number to be square rooted and the desired number of decimal
    // digits from the command line arguments. Fallback to 0 in case of errors.
    const unsigned long number = argc > 1 ? atoi(argv[1]) : 0;
    const unsigned long n_digits = argc > 2 ? atoi(argv[2]) : 0;

    // All the variables used by GMP need to be properly initialized before use.
    // 'c' is basically the remainder, initially set to the original number
    mpz_t c;
    mpz_init_set_ui(c, number);

    // At every iteration, the algorithm "move to the left" by two "digits"
    // the reminder, so it multplies it by base^2.
    mpz_t base_squared;
    mpz_init_set_ui(base_squared, base);
    mpz_mul(base_squared, base_squared, base_squared);

    // 'p' stores the digits of the root found so far. The others are helper variables
    mpz_t p;
    mpz_init_set_ui(p, 0UL);    
    mpz_t y;
    mpz_init(y);
    mpz_t yy;
    mpz_init(yy);
    mpz_t dy;
    mpz_init(dy);
    mpz_t dx;
    mpz_init(dx);
    mpz_t pp;    
    mpz_init(pp);

    // Timing, for testing porpuses
    clock_t start = clock(), diff;

    unsigned long x_max = number;
    // Each "digit" correspond to some decimal digits
    for (unsigned long i = 0,
         last = (n_digits + decimals_per_digit) / decimals_per_digit + 1UL;
         i < last; ++i)
    {
        // Find the greatest x such that:  x * (2 * base * p + x) <= c
        // where x is in [0, base), using a specialized Newton method

        // pp = 2 * base * p
        mpz_mul_ui(pp, p, 2UL * base);

        unsigned long x = x_max;
        for (;;)
        {            
            // y = x * (pp + x)
            mpz_add_ui(yy, pp, x);
            mpz_mul_ui(y, yy, x);

            // dy = y - c
            mpz_sub(dy, y, c);

            // If y <= c we have found the correct x
            if ( mpz_sgn(dy) <= 0 )
                break;

            // Newton's step:  dx = dy/y'  where  y' = 2 * x + pp            
            mpz_add_ui(yy, yy, x);
            mpz_tdiv_q(dx, dy, yy);

            // Update x even if dx == 0 (last iteration)
            x -= max_ul(mpz_get_si(dx), 1);
        }        
        x_max = base - 1;

        // The actual format of the printed "digits" is up to you       
        if (i % 4 == 0)
        {
            if (i == 0)
                printf("%lu.", x);
            putchar('\n');
        }
        else
            printf("%018lu", x);

        // p = base * p + x
        mpz_mul_ui(p, p, base);
        mpz_add_ui(p, p, x);

        // c = (c - y) * base^2
        mpz_sub(c, c, y);
        mpz_mul(c, c, base_squared);
    }

    diff = clock() - start;
    long int msec = diff * 1000L / CLOCKS_PER_SEC;
    printf("\n\nTime taken: %ld.%03ld s\n", msec / 1000, msec % 1000);

    // Final cleanup
    mpz_clear(c);
    mpz_clear(base_squared);
    mpz_clear(p);
    mpz_clear(pp);
    mpz_clear(dx);
    mpz_clear(y);
    mpz_clear(dy);
    mpz_clear(yy);
}

Anda dapat melihat digit keluarannya di sini.

Apa yang Anda tanyakan adalah masalah yang sangat sulit, dan apakah mungkin untuk melakukan "satu per satu" (yaitu tanpa persyaratan ruang kerja yang disesuaikan dengan seberapa jauh Anda ingin pergi) bergantung pada bilangan irasional tertentu dan basis yang ingin direpresentasikan. Misalnya, pada tahun 1995 ketika rumus untuk pi ditemukan yang memungkinkan penghitungan digit biner ke-n dalam ruang O(1), ini adalah masalah yang sangat besar. Itu bukanlah sesuatu yang diharapkan orang bisa terjadi.

Jika Anda bersedia menerima ruang O(n), maka beberapa kasus seperti yang Anda sebutkan cukup mudah. Misalnya, jika Anda memiliki n digit pertama dari akar kuadrat suatu angka sebagai string desimal, Anda cukup mencoba menambahkan setiap digit 0 hingga 9, lalu mengkuadratkan string tersebut dengan perkalian panjang (sama seperti yang Anda pelajari di sekolah dasar), dan memilih yang terakhir yang tidak melampaui batas. Tentu saja ini sangat lambat, tapi sederhana. Cara mudah untuk membuatnya jauh lebih cepat (tetapi tetap sama buruknya secara asimtotik) adalah dengan menggunakan perpustakaan matematika presisi sewenang-wenang sebagai pengganti string. Melakukan hal yang lebih baik secara signifikan memerlukan pendekatan yang lebih maju dan secara umum mungkin tidak dapat dilakukan.

Judul Anda mengatakan:

Bagaimana cara menghitung angka-angka bilangan irasional satu per satu?

Bilangan irasional tidak terbatas pada sebagian besar akar kuadrat saja. Mereka juga menyertakan bilangan dalam bentuk log(x), exp(z), sin(y), dst. (bilangan transendental). Namun, ada beberapa faktor penting yang menentukan apakah atau seberapa cepat Anda dapat menghitung digit bilangan irasional tertentu satu per satu (yaitu, dari kiri ke kanan).

• Tidak semua bilangan irasional dapat dihitung; yaitu, tidak ada seorang pun yang menemukan cara untuk memperkirakannya hingga panjang yang diinginkan (baik dengan ekspresi bentuk tertutup, rangkaian, atau lainnya).
• Ada banyak cara untuk menyatakan bilangan, misalnya dengan perluasan biner atau desimalnya, sebagai pecahan lanjutan, sebagai deret, dll. Dan terdapat algoritma yang berbeda untuk menghitung digit suatu bilangan tergantung pada representasinya.
• Beberapa rumus menghitung digit bilangan tertentu dalam basis tertentu (misalnya basis 2), bukan dalam basis sembarang.

Misalnya, selain rumus pertama untuk mengekstrak digit π tanpa menghitung digit sebelumnya, ada rumus lain dari jenis ini (dikenal sebagai Rumus tipe BBP) yang mengekstrak digit bilangan irasional tertentu. Namun rumus-rumus ini hanya berlaku untuk bilangan pokok tertentu, tidak semua rumus berjenis BBP mempunyai pembuktian formal, dan yang paling penting, tidak semua bilangan irasional mempunyai rumus berjenis BBP (pada dasarnya, hanya konstanta log dan arctan tertentu saja yang mempunyai pembuktian, bukan bilangan-bilangan bentuk exp(x) atau sqrt(x)).

Di sisi lain, jika Anda dapat menyatakan bilangan irasional sebagai pecahan lanjutan (yang dimiliki semua bilangan real), Anda dapat mengekstrak digitnya dari kiri ke kanan, dan dalam basis apa pun yang diinginkan, menggunakan bilangan tertentu. algoritma. Terlebih lagi, algoritme ini dapat digunakan untuk konstanta bilangan real apa pun, termasuk akar kuadrat, eksponensial (e dan exp(x)), logaritma, dll., selama Anda tahu cara menyatakannya sebagai pecahan lanjutan. Untuk implementasinya lihat Digit pi dan Python generator. Lihat juga Kode untuk Menghasilkan satu Digit Sekaligus.