Apa yang paling efisien untuk GCD?

26

Saya tahu bahwa algoritma Euclid adalah algoritma terbaik untuk mendapatkan GCD (pembagi umum yang hebat) dari daftar bilangan bulat positif. Namun dalam praktiknya Anda dapat membuat kode algoritma ini dengan berbagai cara. (Dalam kasus saya, saya memutuskan untuk menggunakan Java, tetapi C / C ++ mungkin merupakan pilihan lain).

Saya perlu menggunakan kode seefisien mungkin dalam program saya.

Dalam mode rekursif, Anda dapat menulis:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

Dan dalam mode berulang, tampilannya seperti ini:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

Ada juga algoritma Biner untuk GCD, yang mungkin dikodekan seperti ini:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
Jonaprieto
sumber
3
Saya pikir ini terlalu subjektif, dan mungkin lebih cocok untuk StackOverflow. "Paling efisien dalam praktik" tergantung pada banyak (bahkan tidak dapat diprediksi) faktor, seperti arsitektur yang mendasarinya, hirarki memori, ukuran dan bentuk input dll.
Juho
5
Ini adalah algoritma yang sama yang diekspresikan dengan cara rekursif dan berulang. Saya pikir perbedaan mereka dapat diabaikan karena algoritma Euclid menyatu cukup cepat. Pilih satu yang sesuai dengan preferensi Anda.
pad
6
Anda mungkin ingin mencoba membuat profil keduanya. Karena versi rekursif adalah panggilan ekor, bukan tidak mungkin kompiler benar-benar memancarkan kode yang hampir sama.
Louis
1
ini salah. harus sementara b! = 0, lalu kembalikan a. Kalau tidak, bug di divisi dengan nol. juga tidak menggunakan rekursi jika Anda memiliki gcds yang sangat besar .... Anda mendapatkan setumpuk fungsi tumpukan dan fungsi ... mengapa tidak beralih saja?
Cris Stringfellow
4
Perhatikan bahwa ada algoritme GCD yang lebih cepat secara asimptotik. Contoh: en.wikipedia.org/wiki/Binary_GCD_algorithm
Neal Young

Jawaban:

21

Kedua algoritma Anda adalah setara (setidaknya untuk bilangan bulat positif, apa yang terjadi dengan bilangan bulat negatif dalam versi imperatif tergantung pada semantik Java %yang saya tidak hafal). Dalam versi rekursif, biarkan dan b i menjadi argumen dari saya th panggilan rekursif: a i + 1 = b i b i + 1 = a i m o d b iaibii

ai+1=bibi+1=aimodbi

Dalam versi imperatif, biarkan danb ' i menjadi nilai-nilai variabeldanpada awalith iterasi dari loop. a i + 1 = b i b i + 1 = a i m o d b iaibiabi

ai+1=bibi+1=aimodbi

Perhatikan kemiripan? Versi imperatif Anda dan versi rekursif Anda menghitung nilai yang persis sama. Selain itu, mereka berdua akhirnya pada saat yang sama, ketika (resp. A ' i = 0 ), sehingga mereka melakukan jumlah yang sama iterasi. Jadi secara algoritmik, tidak ada perbedaan di antara keduanya. Perbedaannya adalah masalah implementasi, sangat tergantung pada kompiler, perangkat keras yang dijalankannya, dan sangat mungkin sistem operasi dan program apa yang dijalankan secara bersamaan.ai=0ai=0

Versi rekursif hanya membuat panggilan rekursif ekor . Sebagian besar kompiler untuk bahasa imperatif tidak mengoptimalkannya, sehingga kemungkinan kode yang mereka hasilkan akan menghabiskan sedikit waktu dan memori membangun kerangka tumpukan pada setiap iterasi. Dengan kompiler yang mengoptimalkan panggilan ekor (kompiler untuk bahasa fungsional hampir selalu melakukannya), kode mesin yang dihasilkan mungkin sama untuk keduanya (dengan asumsi Anda menyelaraskan panggilan tersebut dengan abs).

Gilles 'SANGAT berhenti menjadi jahat'
sumber
8

Untuk angka yang kecil, algoritma GCD biner sudah cukup.

GMP, sebuah perpustakaan yang teruji dengan baik dan nyata, akan beralih ke setengah algoritma GCD khusus setelah melewati ambang khusus, generalisasi dari Algoritma Lehmer. Lehmer menggunakan perkalian matriks untuk meningkatkan algoritma Euclidian standar. Menurut dokumen, waktu berjalan asimtotik dari HGCD dan GCD adalah O(M(N)*log(N)), di mana M(N)waktu untuk mengalikan dua nomor N-tungkai.

Detail lengkap tentang algoritme mereka dapat ditemukan di sini .

qwr
sumber
Tautan ini benar-benar tidak memberikan perincian lengkap, dan bahkan tidak mendefinisikan apa "anggota badan" itu ...
einpoklum - mengembalikan Monica
2

Seperti yang saya tahu Java tidak mendukung optimasi rekursi ekor secara umum, tetapi Anda dapat menguji implementasi Java Anda untuk itu; jika tidak mendukungnya, forsimplo-simpangan seharusnya lebih cepat, jika tidak rekursi harus sama cepatnya. Di sisi lain, ini adalah optimasi bit, pilih kode yang Anda pikir lebih mudah dan lebih mudah dibaca.

Saya juga harus mencatat bahwa algoritma GCD tercepat bukan algoritma Euclid, algoritma Lehmer sedikit lebih cepat.

PJTraill
sumber
Apakah yang Anda maksud sebagai sejauh yang saya tahu ? Apakah maksud Anda spesifikasi bahasa tidak mengamanatkan pengoptimalan ini (akan mengejutkan jika memang demikian), atau sebagian besar implementasi tidak mengimplementasikannya?
PJTraill
1

Pertama, jangan gunakan recursivity untuk mengganti loop ketat. Itu lambat. Jangan mengandalkan kompiler untuk mengoptimalkannya. Kedua, dalam kode Anda, Anda memanggil Math.abs () dalam setiap panggilan rekursif, yang tidak berguna.

Dalam loop Anda, Anda dapat dengan mudah menghindari variabel sementara dan bertukar a dan b sepanjang waktu.

int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

Bertukar menggunakan a ^ = b ^ = a ^ = b membuat sumber lebih pendek tetapi membutuhkan banyak instruksi untuk dieksekusi. Ini akan lebih lambat daripada swap membosankan dengan variabel sementara.

Florian F
sumber
3
“Hindari rekursivitas. Itu lambat ”- disajikan sebagai saran umum, ini palsu. Itu tergantung pada kompiler. Biasanya, bahkan dengan kompiler yang tidak mengoptimalkan rekursi, itu tidak lambat, hanya memakan tumpukan.
Gilles 'SANGAT berhenti menjadi jahat'
3
Tetapi untuk kode pendek seperti ini, perbedaannya signifikan. Mengonsumsi tumpukan berarti menulis ke dan membaca dari memori. Itu lambat. Kode di atas berjalan di 2 register. Recursivity juga berarti melakukan panggilan, yang lebih lama dari lompatan bersyarat. Panggilan rekursif jauh lebih sulit untuk prediksi cabang dan lebih sulit untuk inline.
Florian F
-2

Untuk angka kecil ,% adalah operasi yang cukup mahal, mungkin rekursif yang lebih sederhana

GCD[a,b] := Which[ 
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

lebih cepat? (Maaf, kode Mathematica dan bukan C ++)

Per Alexandersson
sumber
Itu tidak beres. Untuk b == 1, itu harus mengembalikan 1. Dan GCD [2,1000000000] akan lambat.
Florian F
Ah, ya, saya membuat kesalahan. Memperbaiki (saya pikir), dan mengklarifikasi.
Per Alexandersson
Biasanya, GCD [a, 0] juga harus mengembalikan a. Milikmu loop selamanya.
Florian F
Saya downvoting karena jawaban Anda hanya berisi kode. Kami ingin fokus pada ide-ide di situs ini. Misalnya, mengapa% operasi mahal? Spekulasi pada sepotong kode sebenarnya bukan jawaban yang bagus untuk situs ini, menurut saya.
Juho
1
Saya pikir gagasan bahwa modulo lebih lambat daripada pengurangan dapat dianggap sebagai cerita rakyat. Ini berlaku baik untuk bilangan bulat kecil (pengurangan biasanya membutuhkan satu siklus, modulo jarang) dan untuk bilangan bulat besar (pengurangan linear, saya tidak yakin apa kompleksitas terbaik untuk modulo tapi jelas lebih buruk dari itu). Tentu saja Anda juga perlu mempertimbangkan jumlah iterasi yang diperlukan.
Gilles 'SANGAT berhenti menjadi jahat'
-2

Algoritma Euclid paling efisien untuk menghitung GCD:

Gcd panjang statis (panjang a, panjang b)
{
jika (b == 0)
mengembalikan a;
lain
return gcd (, a% b);
}

contoh:-

Misalkan A = 16, B = 10.
GCD (16, 10) = GCD (10, 16% 10) = GCD (10, 6)
GCD (10, 6) = GCD (6, 10% 6) = GCD (6, 4)
GCD (6, 4) = GCD (4, 6% 4) = GCD (4, 2)
GCD (4, 2) = GCD (2, 4% 2) = GCD (2, 0)


Karena B = 0 maka GCD (2, 0) akan mengembalikan 2. 
Rohit-Pandey
sumber
4
Ini tidak menjawab pertanyaan. Penanya menyajikan dua versi Euclid dan bertanya mana yang lebih cepat. Anda tampaknya tidak memperhatikan itu dan hanya menyatakan versi rekursif sebagai satu-satunya algoritma Euclid, dan menyatakan tanpa bukti apa pun bahwa itu lebih cepat daripada yang lainnya.
David Richerby