Membuat perhitungan yang sangat besar

Saya ingin menghitung nilainya

X =n!/2^r

where n<10^6 and r<10^6
and it's guarantee that value of X is between O to 10

Bagaimana cara menghitung X karena saya tidak bisa dengan mudah membagi faktorial dan suku pangkat karena keduanya melebihi bilangan bulat panjang.

Pendekatan Saya
Lakukan dengan bantuan Modulus. Misalkan bilangan prima lebih besar dari 10 misalkan 101 

 X=  [(Factorial N%101)*inverse Modulo of(2^r)]%101;

Perhatikan bahwa modulo invers dapat dengan mudah dihitung dan 2^r%101 juga dapat dihitung.

Masalah:
Ini tidak menjamin bahwa X selalu bilangan bulat tetapi bisa float juga. Metode saya berfungsi dengan baik ketika X bilangan bulat? Bagaimana menangani bila X adalah bilangan floating point


module algorithm numbers
person Narendra Modi    schedule 07.02.2017    source sumber
comment
Bagaimana dengan sesuatu seperti 3/2.0*4/2.0*5/2.0*...?   -  person barak manos    schedule 07.02.2017

Jawaban (4)


arrow_upward
1
arrow_downward

Jika hasil perkiraan OK dan Anda memiliki akses ke perpustakaan matematika dengan eksponensial basis 2 (exp2 di C), log gamma natural (lgamma di C), dan log natural (log di C), maka Anda dapat melakukannya

exp2(lgamma(n+1)/log(2) - r).
person David Eisenstat    schedule 07.02.2017

arrow_upward
0
arrow_downward

Temukan pangkat 2 yang muncul di n!. Ini:

P = n / 2 + n / 2^2 + n / 2^3 + ...

Menggunakan pembagian bilangan bulat hingga Anda mencapai hasil 0.

Jika P >= r, maka Anda mendapatkan hasil bilangan bulat. Anda dapat menemukan hasil ini dengan menghitung faktorial sehingga Anda mengabaikan r pangkat 2. Sesuatu seperti:

factorial = 1
for i = 2 to n:

    factor = i
    while factor % 2 == 0 and r != 0:
        factor /= 2
        r -= 1

    factorial *= factor

Jika P < r, setel r = P, terapkan algoritme yang sama dan bagi hasilnya dengan 2^(initial_r - P) pada akhirnya.

person IVlad    schedule 07.02.2017

arrow_upward
0
arrow_downward

Kecuali untuk beberapa kasus (dengan n dan r kecil) X tidak akan berupa bilangan bulat -- karena jika n >= 11 maka 11 membagi n! tetapi tidak membagi pangkat dua apa pun, jadi jika X adalah integral, maka X haruslah paling sedikit 11.

Salah satu caranya adalah: inisialisasi X menjadi satu; lalu ulangi: jika X > 10 bagi dengan 2 sampai tidak; jika X ‹ 10 kalikan dengan faktor berikutnya sampai tidak; sampai Anda kehabisan faktor dan pangkat 2.

person dmuir    schedule 07.02.2017
comment
@Paul Anda dapat mengurangi X menjadi 10 atau lebih rendah dengan membaginya dengan 2, seperti yang saya katakan. Karena jawabannya tidak lebih besar dari 10, maka angka 2 harus cukup. - person dmuir; 07.02.2017
comment
Jawabannya adalah nilai floating-point di bawah 10. Dan seperti yang telah ditunjukkan dalam komentar saya, n tertinggi, sehingga X di setiap langkah dapat direduksi menjadi nilai di bawah 10 adalah 4. Coba saja pendekatan Anda dengan 5!. - person Paul; 07.02.2017

arrow_upward
0
arrow_downward

Pendekatan yang dapat disesuaikan dengan presisi/kinerja adalah sebagai berikut:

Simpan faktorial dalam bilangan bulat dengan jumlah bit tetap. Kita dapat menghilangkan beberapa digit terakhir jika angkanya menjadi terlalu besar, karena angka tersebut tidak akan terlalu mempengaruhi hasil keseluruhan. Dengan menskalakan bilangan bulat ini lebih besar/lebih kecil, algoritme menjadi dapat disesuaikan baik untuk performa maupun presisi.

Setiap kali bilangan bulat meluap karena perkalian, geser ke kanan beberapa tempat dan kurangi nilai tersebut dari r. Pada akhirnya harus ada angka kecil yang tersisa sebagai r dan bilangan bulat v dengan bit faktorial paling signifikan. v ini sekarang dapat diartikan sebagai bilangan titik tetap dengan r digit pecahan.

Bergantung pada ketelitian yang diperlukan, pendekatan ini bahkan mungkin berhasil dengan long, meskipun saya belum punya waktu untuk menguji pendekatan ini selain sedikit bereksperimen dengan kalkulator.

person Paul    schedule 07.02.2017