🙌🏾 😋 👩🏻‍🏭 Sekali lagi tentang GCD, algoritma Euclidean dan sedikit tentang sejarah algoritma secara umum. Tentu saja dengan contoh Swift 👩🏿‍💻 💐 🌡️

Algoritma adalah salah satu topik utama dalam pemrograman , mereka ada di mana-mana (terutama dalam wawancara, haha).

gambar

(Apakah mungkin dilakukan tanpa akordeon tombol di pos seperti itu?)

Salah satu yang paling terkenal adalah yang disebut algoritma Euclidean - mungkin cara paling umum untuk menemukan pembagi umum terbesar (GCD) dari dua bilangan bulat non-negatif. Dia juga sering suka mulai belajar (dan belajar) bagian yang relevan dari matematika dan ilmu komputer .

Dan Donald Knuth , penulis terkenal risalah "The Art of Programming " (dan tidak hanya), bahkan menganggap algoritma sebagai yang pertama dalam sejarah (setidaknya berkenaan dengan definisi modern). Karena, terlepas dari kenyataan bahwa algoritma tersebut ditemukan dan digunakan sebelumnya, pada kenyataannya, Euclid , yang hidup pada abad IV-III. BC (sudah disebutkan oleh Aristoteles , yang hidup seabad sebelumnya), Euclid menggambarkan prosesnya secara iteratif , yang konsisten dengan makna modern dari kata tersebut.

Kata "algoritma" sendiri kembali ke nama ahli matematika Persia Al-Khwarizmi , yang hidup sekitar abad VIII-IX. sudah AD. Dan awal penggunaannya dalam arti dekat dengan yang modern dianggap hanya abad ke-20, lebih tepatnya - dekade pertama, kebangkitan teknologi informasi.

Algoritma Euclidean

Demi rasa ingin tahu, saya sarankan Anda membiasakan diri dengan deskripsi Euclidean tentang algoritma dalam pengeditan Knuth. Itu cukup panjang, karena itu tersembunyi di bawah luka:

Deskripsi algoritma Euclidean dekat dengan aslinya

Tawarkan. Untuk diberikan dua bilangan bulat positif, temukan pembagi umum terbesar mereka.

Misalkan A dan C menjadi dua bilangan bulat positif; Diperlukan untuk menemukan GCD mereka. Jika angka A dapat dibagi dengan C, maka angka C adalah pembagi umum dari angka C dan A, karena ia membagi dirinya sendiri. Dan jelas, itu akan menjadi pembagi terbesar, karena tidak ada angka lebih besar dari angka C yang membagi C.

Tetapi jika C tidak membagi angka A, maka kita akan terus mengurangi jumlah yang lebih kecil dari angka A dan C dari yang lebih besar sampai kita mendapatkan angka yang benar-benar membagi yang sebelumnya dikurangkan. Ini harus terjadi cepat atau lambat, karena jika perbedaannya sama dengan satu, maka unit akan membagi sebelumnya dikurangi.

Sekarang anggaplah bahwa E adalah sisa positif dari membagi angka A dengan C; biarkan F menjadi sisa positif dari membagi C dengan E dan biarkan F membagi E. Karena F membagi E dan E membagi C - F, F juga membagi C - F. Tetapi ia juga membagi dirinya sendiri, jadi F membagi C, dan C membagi A - E; karena itu, F juga membagi A - E, tetapi juga membagi E; oleh karena itu, F membagi A. Akibatnya, F adalah pembagi umum dari angka A dan C.

Sekarang saya menegaskan bahwa itu juga GCD. Memang, jika F bukan pembagi umum terbesar dari angka A dan C, maka ada angka yang lebih besar yang akan membagi kedua angka-angka ini. Biarkan nomor tersebut menjadi G.

Karena angka G membagi angka C, dan angka C membagi A - E, G juga membagi angka A - E. Angka G juga membagi seluruh angka A, sehingga ia membagi sisanya E. Tetapi E membagi C - F, jadi G juga membagi C - F. Dan angka G juga membagi seluruh angka C, karena ia membagi sisa F; jadi, jumlah yang lebih besar membagi yang lebih kecil, dan ini tidak mungkin.

Dengan demikian, tidak ada angka yang lebih besar dari F yang membagi A dan C; oleh karena itu, angka F adalah GCD.

Konsekuensi Alasan ini membuat asumsi jelas bahwa setiap angka yang membagi dua angka membagi GCD mereka. Rt

Deskripsi memberikan dua cara untuk menemukan GCD - dengan mengurangi dan membagi. Sebenarnya, dua metode penerapan algoritma ini sudah dikenal luas saat ini.

Berikut adalah contoh fungsi yang ditulis dalam Swift yang mengimplementasikan metode pertama:

func subtractionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber - secondNumber } else { secondNumber = secondNumber - firstNumber } } return firstNumber + secondNumber // One of them is 0. }

Di sini, untuk digunakan kembali, demi saya, saya membawa kasus fungsi terpisah untuk mencari GCD, ketika diketahui segera, tanpa perlu mengikuti algoritma apa pun:

 func simpleCasesGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int? { if firstNumber == secondNumber { return firstNumber // Any. } if firstNumber == 0 { return secondNumber } if secondNumber == 0 { return firstNumber } return nil }

(Jika dua angka sama, maka secara alami GCD mereka juga sama dengan mereka. Jika ada angka yang nol, maka GCD akan sama dengan angka kedua, karena nol dapat dibagi dengan angka apa pun (dengan hasil, tentu saja, juga nol) .)

Hanya nilai-nilai non-negatif yang dapat digunakan sebagai input. Dengan demikian, untuk yang negatif, Anda dapat menggunakan metode yang sama, tetapi mengambil nomor modulo. (Ya, faktor umum juga bisa negatif, tetapi kami mencari secara khusus untuk GCD, dan angka positif jelas selalu lebih dari negatif.)

Dan di sini mungkin terlihat seperti implementasi versi algoritma berdasarkan pembagian:

 func divisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber % secondNumber } else { secondNumber = secondNumber % firstNumber } } return firstNumber + secondNumber // One of them is 0. }

Versi kedua hari ini dianggap lebih disukai, karena mengandung, rata-rata, jumlah langkah yang jauh lebih kecil. Namun, pada saat komputer besar dan lambat, operasi divisi bisa menjadi prosedur yang kompleks. Dan kemudian versi pertama dari algoritma bisa lebih efektif.

Untuk membandingkannya sedikit, saya melakukan beberapa pengukuran menggunakan metode measure(_:) dari kelas XCTestCase saya dari kerangka kerja "asli" untuk menguji kode dalam proyek-proyek Xcode- proyek XCTest .

Sebagai input, saya menggunakan array pasangan angka acak. Pengukuran dilakukan, tentu saja, menggunakan array yang sama untuk setiap metode. Saya mengambil penyebaran angka untuk pasangan dari nol hingga 9999. Pengukuran dilakukan pada jumlah perhitungan (pasangan angka): satu, sepuluh, 100, 1000, 10.000, 100.000, 1.000.000 dan 10.000.000. Yang terakhir membuat saya mengharapkan hasilnya selama beberapa menit, jadi saya memutuskan untuk melakukannya untuk berhenti.

Berikut ini adalah kode pembuatan input sederhana:

 let pairs = (0..<100).map { _ in (Int.random(in: 0..<10000), Int.random(in: 0..<10000)) } // Generates 100 pairs.

Pengukuran itu sendiri terlihat, misalnya, seperti ini:

 func testSubstractionGCDPerformance() { measure() { _ = pairs.map { substractionGCD($0, $1) } } }

Dan inilah hasil peluncurannya di komputer saya:

gambar

(Pengurangan - pengurangan, pembagian - pembagian.)

Secara umum, sangat jelas terlihat berapa banyak metode pengurangan yang hilang pada komputer modern.

"Peningkatan" versi algoritma Euclidean

Dalam literatur Anda dapat menemukan versi algoritma di mana salah satu angka di setiap langkah, bukannya sisa membagi dengan yang kedua, digantikan oleh perbedaan antara offset ini dan angka kedua, tetapi hanya jika sisa divisi lebih dari setengah angka kedua. Implementasi versi ini mungkin terlihat seperti ini:

 func improvedDivisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { let firstNumberClaim = firstNumber % secondNumber if firstNumberClaim > secondNumber / 2 { firstNumber = abs(firstNumberClaim - secondNumber) } else { firstNumber = firstNumberClaim } } else { let secondNumberClaim = secondNumber % firstNumber if secondNumberClaim > firstNumber / 2 { secondNumber = abs(secondNumberClaim - firstNumber) } else { secondNumber = secondNumberClaim } } } return firstNumber + secondNumber // One of them is 0. }

Modifikasi seperti itu mengurangi jumlah langkah dalam algoritma, tetapi menilai dari hasil pengukuran pada komputer saya, perhitungan tambahan dan pemeriksaan pada setiap langkah akan menetralisir keunggulan ini dan bahkan lebih:

gambar

(Peningkatan adalah versi "perbaikan".)

Sedikit lagi tentang pentingnya algoritma Euclidean

Algoritma ini juga memiliki versi geometris (untuk menemukan ukuran terbesar dari dua segmen).

Algoritma itu, tentu saja, digeneralisasi untuk menemukan GCD dari sejumlah angka, bukan hanya dua. Singkatnya, idenya adalah ini: jika kita menetapkan fungsi mencari GCD dari dua angka sebagai gcd (a, b), maka, katakanlah, GCD dari tiga angka gcd (a, b, c) sama dengan gcd (gcd (a, b), c). Dan seterusnya, untuk sejumlah angka GCD ditemukan dengan secara berurutan menghitung GCD dari GCD dari pasangan angka sebelumnya dan angka berikutnya. Meskipun, tentu saja, ini menyangkut pencarian GCD secara umum, dan bukan hanya algoritma Euclidean.

Ada juga generalisasi dari algoritma untuk menemukan polinomial GCD. Tapi ini sudah di luar lingkup tulisan sederhana ini, dan sampai batas tertentu, pengetahuan saya tentang matematika.

Kompleksitas Algoritma Euclidean

Kompleksitas temporal dari algoritma ini telah diselidiki untuk waktu yang lama, tidak dengan cepat dan oleh orang-orang yang lebih terpelajar daripada pelayan Anda yang rendah hati. Namun, pertanyaannya telah lama ditutup dan jawaban telah diterima. Sebenarnya, kembali pada pertengahan abad sebelum yang lalu. Gabriel Lame .

Singkatnya, jawabannya dirumuskan, pada kenyataannya, oleh teorema Lame terkait dengan algoritma ini. Jumlah langkah dalam algoritma akan sama dengan nomor urut angka Fibonacci terdekat yang lebih besar , yang terkecil dari dua angka parameter input minus 2. Dengan menggunakan notasi matematika yang sedikit lebih tradisional, maka jika u> v (dan v> 1), maka jumlah lintasan algoritma akan n - 2 untuk v <Fn (Fn adalah bilangan Fibonacci v terdekat, dan n adalah nomor urutnya).

Angka-angka Fibonacci tumbuh secara eksponensial, masing-masing, kami memiliki fungsi logaritmik dari waktu eksekusi algoritma (dari yang lebih kecil dari dua angka input).

Perhitungan yang sama menunjukkan bahwa data input terburuk untuk algoritma adalah dua angka Fibonacci berturut-turut.

Metode biner untuk menemukan NOD

Berbicara tentang pencarian GCD, ada baiknya menyebutkan algoritma yang diusulkan sudah di tahun 60-an abad terakhir oleh Joseph Stein tertentu tentang yang saya tidak menemukan informasi di Web sama sekali. Ini (algoritma) berorientasi ke aritmatika biner dan tidak mengandung operasi divisi. Algoritma hanya beroperasi dengan parity check dan separuh, yang layak dengan kemampuan aritmatika biner saja.

Algoritma ini didasarkan pada empat fakta:

Jika u dan v keduanya genap, maka gcd (u, v) = 2 * gcd (u / 2, v / 2);
Jika Anda genap dan v tidak, gcd (u, v) = gcd (u / 2, v);
gcd (u, v) = gcd (u - v, v) (ini mengikuti dari algoritma Euclidean);
Jika u dan v keduanya aneh, maka u - v adalah genap dan | u - v | <maks (u, v)

Di Wikipedia Anda dapat melihat versi algoritme rekursif (ditulis dalam beberapa baris dalam bahasa pemrograman modern), saya tidak menulis ulang di Swift. Dan di sini saya memberikan implementasi berulang:

 func binaryGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber var shift = 0 while (firstNumber | secondNumber) & 1 == 0 { shift += 1 firstNumber >>= 1 secondNumber >>= 1 } while firstNumber & 1 == 0 { firstNumber >>= 1 } repeat { while secondNumber & 1 == 0 { secondNumber >>= 1 } if firstNumber > secondNumber { swap(&firstNumber, &secondNumber) } secondNumber -= firstNumber } while secondNumber != 0 return firstNumber << shift }

Setelah melakukan pengukuran pada data yang sama, sayangnya, algoritma canggih ini di komputer saya tidak memenuhi harapan yang ada di dalamnya. Tentu saja, ia masih bekerja dua kali lebih cepat dari algoritma Euclidean dengan pengurangan, tetapi secara nyata lebih rendah daripada versi divisi klasiknya. Tabel ringkasan lengkap:

gambar

(Binary adalah algoritma biner.)

(Saya tidak mengesampingkan bahwa algoritma dapat ditulis lebih efisien daripada yang saya lakukan, dan ini akan mempengaruhi hasilnya, tetapi untuk apa kita memerlukan kompiler?!

Omong-omong, algoritma ini, yang tidak diragukan lagi memperoleh ketenaran selama 15 menit di era teknologi informasi (di bagian yang lebih awal daripada yang sekarang), dikenal di Cina kuno. Deskripsinya ditemukan dalam karya-karya yang berasal dari abad ke-1. AD Tentu saja, dalam istilah seperti "setengah pembagian" dan pengurangan. Dan juga dalam konteks mengurangi pecahan.

Kesimpulan

Jujur, dengan "penelitian" sederhana ini saya tidak akan membuktikan apa pun dan tidak ingin membuat kesimpulan revolusioner (dan saya tidak melakukannya!). Saya hanya ingin memuaskan rasa ingin tahu saya, melihat karya berbagai pendekatan untuk menyelesaikan masalah klasik, dan sedikit merentangkan jari saya. Meskipun demikian, saya harap Anda juga penasaran untuk mengamati hasilnya!