apa cara yang efisien untuk menemukan desimal berulang

24

Saya mencoba untuk menemukan algoritma yang efisien di Jawa untuk menemukan bagian desimal berulang dari dua bilangan bulat adan di bmana a/b.

misalnya. 5/7 = 0.714258 714258 ....

Saat ini saya hanya tahu metode pembagian panjang.

Jun Hao
sumber
2
Jadi Anda memiliki a = 5 dan b = 7, dan Anda dapat menghitung a / b di floating point dengan cukup mudah, tetapi yang ingin Anda ketahui adalah bahwa ia berulang setelah 6 tempat desimal?
Sparr

Jawaban:

10

Saya percaya bahwa ada dua pendekatan umum di sini, Anda pada dasarnya dapat "brute force" mencari string berulang berulang, atau Anda dapat menyelesaikannya sebagai masalah teori bilangan.

Sudah lama sejak saya menemukan masalah ini, tetapi kasus khusus (1 / n) adalah masalah # 26 di Project Euler, jadi Anda mungkin dapat menemukan informasi lebih lanjut dengan mencari solusi efisien untuk nama spesifik tersebut. Satu pencarian membawa kita ke situs web Eli Bendersky, tempat dia menjelaskan solusinya . Berikut beberapa teori dari halaman Desimal Ekspansi Mathworld :

Setiap fraksi tidak beraturan m/nbersifat periodik, dan memiliki periode yang tidak lambda(n)bergantung pada m, yang paling n-1 panjang digit. Jika nrelatif prima terhadap 10, maka periode lambda(n)dari m/nadalah pembagi dari phi(n)dan memiliki paling banyak phi(n)digit, dimana phiadalah fungsi totient. Ternyata itu lambda(n)adalah urutan multiplikasi 10 (mod n) (Glaisher 1878, Lehmer 1941). Jumlah digit dalam bagian berulang dari ekspansi desimal dari bilangan rasional juga dapat ditemukan langsung dari urutan multiplikatif dari penyebutnya.

Teori bilangan saya agak berkarat saat ini, jadi yang terbaik yang bisa saya lakukan adalah mengarahkan Anda ke arah itu.

Daniel B
sumber
8

Biarkan n < d, dan Anda mencoba mencari tahu bagian yang berulang n/d. Membiarkan pmenjadi jumlah digit di bagian berulang: lalu n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). Bagian kurung adalah deret geometris, sama dengan 1/(10^p - 1).

Jadi n / d = R / (10^p - 1). Atur ulang untuk mendapatkan R = n * (10^p - 1) / d. Untuk menemukan R, loop pdari 1 hingga tak terbatas, dan berhenti segera setelah dmembagi secara merata n * (10^p - 1).

Berikut ini adalah implementasi dengan Python:

def f(n, d):
    x = n * 9
    z = x
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1
    return k, z / d

( kmelacak panjang urutan berulang, sehingga Anda dapat membedakan antara 1/9 dan 1/99, misalnya)

Perhatikan bahwa implementasi ini (ironisnya) berulang selamanya jika ekspansi desimal terbatas, tetapi berakhir jika tidak terbatas! Anda dapat memeriksa kasus ini, karena n/dhanya akan memiliki representasi desimal terbatas jika semua faktor prima dyang bukan 2 atau 5 juga ada n.

valtron
sumber
1
Jawaban ini sepertinya benar. Metode ini didasarkan pada "aturan" berikut: 0.123123... = 123/999 0.714258714258... = 714258/999999 (=5/7)dll.
DATANG DARI
4
Gagal kasus seperti 1/6 atau 5/12: \
razpeitia
1
@razpeitia Saya telah membuat sesuatu yang serupa, tetapi bekerja di semua kasus (termasuk divisi integer). Lihat: codepad.org/hKboFPd2
Tigran Saluev
Saya telah membuat implementasi javascript yang mirip dengan @ TigranSaluev di github.com/Macil/cycle-division
Macil
2

Divisi panjang? : /

Ubah hasilnya menjadi string, dan kemudian terapkan algoritma ini ke sana. Gunakan BigDecimal jika string Anda tidak cukup panjang dengan tipe biasa.

Robert Harvey
sumber
4
"Ubah menjadi string" dapat memerlukan perhitungan presisi yang sewenang-wenang dan string yang sangat panjang untuk menghitung dua salinan bagian berulang dari string (dan bagaimana Anda tahu kapan harus berhenti menghitung? .121212312121231212123 ... akan menjadi masalah)
Sparr
@Sparr Panjang pengulangan selalu lebih kecil dari penyebut.
@MichaelT aku tidak tahu itu. Jika benar, ketepatannya tidak tepat "arbitrer", tetapi bisa sangat tinggi tergantung pada penyebutnya.
Sparr
Saya tidak berpikir bahwa algoritma yang Anda tautkan akan berfungsi tanpa modifikasi. Ini termasuk pengulangan yang tumpang tindih dan mencari seluruh string (tidak hanya untuk pertandingan berturut-turut). Misalnya, substring berulang yang terpanjang dalam "pisang" adalah "ana".
Web_Designer