القاسم المشترك الأكبر

من موسوعة حسوب

القاسم المشترك الأكبر (Greatest Common Divisor GCD) لعددين هو أكبر عدد يقسم هذين العددين قسمة تامة، وأبسط طريقة لإيجاد القاسم المشترك الأكبر لعددين هو إيجاد حاصل ضرب العوامل المشتركة لهما.

الخوارزمية الإقليدية

تستند الخوارزمية الإقليدية Euclidean algorithm على الحقائق التالية:

1- إن طرحنا العدد الأصغر من العدد الأكبر، فإنّ القاسم المشترك الأكبر لن يتغير، وهذا يعني أنّه لو استمررنا في طرح العدد الأصغر من العدد الأكبر، فإنّنا سنصل في النهاية إلى القاسم المشترك الأكبر.

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

  • C++‎:
#include <iostream> 
using namespace std; 
// دالة تعاودية تعيد القاسم المشترك الأكبر للعددين المعطيين
int gcd(int a, int b) 
{ 
	// كل الأعداد تقسم العدد 0
	if (a == 0) 
	return b; 
	if (b == 0) 
	return a; 

	// الحالة الأساس
	if (a == b) 
		return a; 

	// العدد الأول أكبر من الثاني
	if (a > b) 
		return gcd(a-b, b); 
	return gcd(a, b-a); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int a = 98, b = 56; 
	cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b); 
	return 0; 
}
  • بايثون:
# دالة تعاودية تعيد القاسم المشترك الأكبر للعددين المعطيين
def gcd(a,b): 
	
	# كل الأعداد تقسم العدد 0
	if (a == 0): 
		return b 
	if (b == 0): 
		return a 

	# الحالة الأساس
	if (a == b): 
		return a 

	# العدد الأول أكبر من الثاني
	if (a > b): 
		return gcd(a-b, b) 
	return gcd(a, b-a) 

# اختبار الدالة السابقة
a = 98
b = 56
if(gcd(a, b)): 
	print('GCD of', a, 'and', b, 'is', gcd(a, b)) 
else: 
	print('not found')
  • جافا:
class Test 
{ 
	// دالة تعاودية تعيد القاسم المشترك الأكبر للعددين المعطيين
	static int gcd(int a, int b) 
	{ 
		// كل الأعداد تقسم العدد 0
		if (a == 0) 
		return b; 
		if (b == 0) 
		return a; 
	
		// الحالة الأساس
		if (a == b) 
			return a; 
	
		// العدد الأول أكبر من الثاني
		if (a > b) 
			return gcd(a-b, b); 
		return gcd(a, b-a); 
	} 
	
	// اختبار الدالة السابقة
	public static void main(String[] args) 
	{ 
		int a = 98, b = 56; 
		System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b)); 
	} 
}

2- عوضًا عن طرح الأرقام، يمكن قسمة العدد الأصغر، وعندما يكون باقي القسمة صفرًا تتوقف الخوارزمية عن العمل.

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

  • C++‎:
// C++ program to find GCD of two numbers 
#include <iostream> 
using namespace std; 
// دالة تعاودية تعيد القاسم المشترك الأكبر للعددين المعطيين
int gcd(int a, int b) 
{ 
	if (b == 0) 
		return a; 
	return gcd(b, a % b); 
	
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int a = 98, b = 56; 
	cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b); 
	return 0; 
}
  • بايثون:
# دالة تعاودية تعيد القاسم المشترك الأكبر للعددين المعطيين 
def gcd(a,b): 
	
	# Everything divides 0 
	if (b == 0): 
		return a 
	return gcd(b, a%b) 

# اختبار الدالة السابقة 
a = 98
b = 56
if(gcd(a, b)): 
	print('GCD of', a, 'and', b, 'is', gcd(a, b)) 
else: 
	print('not found')
  • جافا:
class Test 
{ 
	// دالة تعاودية تعيد القاسم المشترك الأكبر للعددين المعطيين
	static int gcd(int a, int b) 
	{ 
	if (b == 0) 
		return a; 
	return gcd(b, a % b); 
	} 
	
	// اختبار الدالة السابقة
	public static void main(String[] args) 
	{ 
		int a = 98, b = 56; 
		System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b)); 
	} 
}

الخوارزمية الإقليدية الموسّعة

تحسب الخوارزمية الإقليدية الموسّعة Extended Euclidean algorithm إضافة إلى ما سبق معاملين صحيحين x و y بشرط تحقق العلاقة: 

  ax + by = gcd(a, b)

أمثلة: 

المدخلات: a = 30, b = 20
المخرجات: gcd = 10
        x = 1, y = -1
لاحظ أنّ ‎30*1 + 20*(-1) = 10‎‎

المدخلات: a = 35, b = 15
المخرجات: gcd = 5
        x = 1, y = -2
لاحظ أنّ ‎35*1 + 15*(-2) = 5‎

تحدّث الخوارزمية الإقليدية الموسّعة النتيجة المعادة من الدالة gcd(a, b)‎ باستخدام النتائج المحسوبة بواسطة الاستدعاء التعاودي gcd(b%a, a)‎. ولو افترضنا أن قيمتي x و y المحسوبتين بواسطة الاستدعاء التعاودي هما x1 و y1 فإنّ قيمتي x و y ستحدّثان بالاعتماد على العلاقة التالية: 

x = y1 - ⌊b/a⌋ * x1
y = x1

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

  • C:
#include <stdio.h> 

int gcdExtended(int a, int b, int *x, int *y) 
{ 
	// الحالة الأساس
	if (a == 0) 
	{ 
		*x = 0; 
		*y = 1; 
		return b; 
	} 

	int x1, y1; // لتخزين نتائج الاستدعاء التعاودي
	int gcd = gcdExtended(b%a, a, &x1, &y1); 

	// تحديث قيم المتغيرين باستخدام نتائج الاستدعاء التعاودي
	*x = y1 - (b/a) * x1; 
	*y = x1; 

	return gcd; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int x, y; 
	int a = 35, b = 15; 
	int g = gcdExtended(a, b, &x, &y); 
	printf("gcd(%d, %d) = %d", a, b, g); 
	return 0; 
}
  • بايثون:
def gcdExtended(a, b, x, y): 
	# الحالة الأساس
	if a == 0 : 
		x = 0
		y = 1
		return b 
		
	x1 = 1
	y1 = 1 # تخزين نتائج الاستدعاء التعاودي
	gcd = gcdExtended(b%a, a, x1, y1) 

	# تحديث قيم المتغيرين باستخدام الاستدعاء التعاودي
	x = y1 - (b/a) * x1 
	y = x1 

	return gcd 


x = 1
y = 1
a = 35
b = 15
g = gcdExtended(a, b, x, y) 
print("gcd(", a , "," , b, ") = ", g)
  • جافا:
import java.util.*; 
import java.lang.*; 

class GFG 
{ 
	public static int gcdExtended(int a, int b, int x, int y) 
	{ 
		// الحالة الأساس 
		if (a == 0) 
		{ 
			x = 0; 
			y = 1; 
			return b; 
		} 

		int x1=1, y1=1; // تخزين نتائج الاستدعاء التعاودي 
		int gcd = gcdExtended(b%a, a, x1, y1); 

		// تحديث قيم المتغيرين باستخدام الاستدعاء التعاودي
		x = y1 - (b/a) * x1; 
		y = x1; 

		return gcd; 
	} 

// اختبار الشيفرة السابقة
	public static void main(String[] args) 
	{ 
		int x=1, y=1; 
		int a = 35, b = 15; 
		int g = gcdExtended(a, b, x, y); 
		System.out.print("gcd(" + a + " , " + b+ ") = " + g); 

	} 
}

تبين الشيفرة أعلاه أنّ قيمتي x و y هما نتيجتان للمدخلات a و b: 

   a.x + b.y = gcd                      ----(1)

وأنّ قيمتي x1 و y1 هما نتيجتان للمدخلات b%a و a: 

   (b%a).x1 + a.y1 = gcd

وعند وضع ‎b%a = (b - (⌊b/a⌋).a)‎ في أعلاه، نحصل على ما يلي: (⌊b/a⌋ تعني floor(a/b)‎). 

   (b - (⌊b/a⌋).a).x1 + a.y1  = gcd

ويمكن كتابة المعادلة أعلاه كما يلي: 

   b.x1 + a.(y1 - (⌊b/a⌋).x1) = gcd      ---(2)

وبعد مقارنة معاملي a و b في المعادلة (1) و (2) نحصل على ما يلي: 

   x = y1 - ⌊b/a⌋ * x1
   y = x1

إنّ الخوارزمية الإقليدية الموسّعة مفيدة جدًّا عندما يكون العددان a و b عددين أوليين نسبيًا coprime (أو أنّ القاسم المشترك الأكبر بينهما هو 1)؛ وذلك لأنّ x هو المقلوب النمطي modular multiplicative inverse لـ ‎a ‎modulo b و y هو المقلوب النمطي لـ b modulo a. ومن الجدير بالذكر أنّ حساب المقلوب النمطي من الخطوات المهمّة في خوارزمية RSA للتشفير باستخدام المفتاح العام public-key encryption.

إيجاد القاسم المشترك الأكبر لمجموعة من الأعداد

يساوي القاسم المشترك الأكبر لثلاثة أعداد أو أكثر حاصل ضرب العوامل المشترك لكل هذه الأعداد، ولكن يمكن حساب القاسم المشترك الأكبر لها بالاستمرار في حساب القواسم المشتركة الكبرى لأزواج من الأعداد. 

gcd(a, b, c) = gcd(a, gcd(b, c)) 
             = gcd(gcd(a, b), c) 
             = gcd(gcd(a, c), b)

ويمكن تنفيذ ما يلي لحساب القاسم المشترك الأكبر لمصفوفة من الأعداد: 

result = arr[0]
For i = 1 to n-1
   result = GCD(result, arr[i])

تعرض الأمثلة التالية كيفية تنفيذ هذه الطريقة في عدد من لغات البرمجة:

  • C++‎:
#include <bits/stdc++.h> 
using namespace std; 

// تعيد الدالة القاسم المشترك الأكبر للعددين المعطيين
int gcd(int a, int b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 

// تعيد الدالة القاسم المشترك الأكبر لمصفوفة الأعداد المعطاة
int findGCD(int arr[], int n) 
{ 
	int result = arr[0]; 
	for (int i = 1; i < n; i++) 
		result = gcd(arr[i], result); 

	return result; 
} 

// اختبار الدوال السابقة 
int main() 
{ 
	int arr[] = { 2, 4, 6, 8, 16 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	cout << findGCD(arr, n) << endl; 
	return 0; 
}
  • بايثون:
# تعيد الدالة القاسم المشترك الأكبر للعددين المعطيين 
def find_gcd(x, y): 
	
	while(y): 
		x, y = y, x % y 
	
	return x 
		
# اختبار الدالة السابقة		 
l = [2, 4, 6, 8, 16] 

num1 = l[0] 
num2 = l[1] 
gcd = find_gcd(num1, num2) 

# إيجاد القاسم المشترك الأكبر لمصفوفة الأعداد
for i in range(2, len(l)): 
	gcd = find_gcd(gcd, l[i]) 
	
print(gcd)
  • جافا:
public class GCD { 
	// تعيد الدالة القاسم المشترك الأكبر للعددين المعطيين
	static int gcd(int a, int b) 
	{ 
		if (a == 0) 
			return b; 
		return gcd(b % a, a); 
	} 

	تعيد الدالة القاسم المشترك الأكبر لمصفوفة الأعداد المعطاة 
	static int findGCD(int arr[], int n) 
	{ 
		int result = arr[0]; 
		for (int i = 1; i < n; i++) 
			result = gcd(arr[i], result); 

		return result; 
	} 

	// اختبار الدوال السابقة
	public static void main(String[] args) 
	{ 
		int arr[] = { 2, 4, 6, 8, 16 }; 
		int n = arr.length; 
		System.out.println(findGCD(arr, n)); 
	} 
}

خوارزمية شتاين

خوارزمية شتاين Stein's Algorithm أو خوارزمية القاسم المشترك الأكبر الثنائية binary GCD هي خوارزمية تحسب القاسم المشترك الأكبر لعددين صحيحين غير سالبين. تستخدم خوارزمية شتاين الإزاحات الحسابية arithmetic shfits والمقارانات وعملية الطرح عوضًا عن عملية القسمة.

يمكن تقسيم عمل خوارزمية شتاين إلى الخطوات التالية:

  1. إن كان العددان a و b صفرًا، فإنّ القاسم المشترك الأكبر لهما هو 0.
  2. إن كان أحد العددين صفرًا فإنّ القاسم المشترك الأكبر لهما هو 0 كذلك؛ وذلك لأنّ الصفر يقبل القسم على جميع الأعداد.
  3. إن كان العددان a و b زوجيين فإنّ gcd(a, b) - 2*gcd(a/2, b/2)‎ لأنّ 2 هو قاسم مشترك لهما. يمكن إجراء عملية الضرب بالرقم 2 باستخدام معامل الإزاحة بالبتات bitwise shift operator.
  4. إن كان a عددًا زوجيًا وb عددًا فرديًا فإنّ gcd(a,b) = gcd(a/2 , b)‎. وإن كان a عددًا فرديًا وb عددًا زوجيًا فإنّ gcd(a, b) = gcd(a, b/2)‎. العدد 2 ليس قاسمًا مشتركًا.
  5. إن كان العددان a و b فرديين فإنّ gcd(a,b) = gcd(|a-b|/2, b)‎. لاحظ أنّ الفرق بين عددين فرديين هو عدد زوجي.

تكرّر الخطوات 3-5 إلى أن يتساوى العددان، أو إلى أن تصبح قيمة a صفرًا. وفي كل الحالتين فإنّ القاسم المشترك الأكبر هو power(2, k)‎ * b وتعني رفع العدد 2 إلى الأس k وk هي عدد العوامل المشتركة للعدد 2 والتي تم االعثور عليها في الخطوة الثانية.

تنفيذ الخوارزمية

يمكن تنفيذ خوارزمية شتاين بالطريقتين التكرارية والتعاودية.

الطريقة التكرارية

  • C++‎:
#include <bits/stdc++.h> 
using namespace std; 

int gcd(int a, int b) 
{ 
	/* GCD(0, b) == b; GCD(a, 0) == a, 
	GCD(0, 0) == 0 */
	if (a == 0) 
		return b; 
	if (b == 0) 
		return a; 

	/* k حساب قيمة
	والتي تمثل أكبر أس للعدد 2 والذي يقبل العددان المعطيان القسمة عليه */
	int k; 
	for (k = 0; ((a | b) && 1) == 0; ++k) 
	{ 
		a >>= 1; 
		b >>= 1; 
	} 

	/* الاستمرار في القسمة على 2 إلى أن يصبح العدد الأول فرديًا */
	while ((a > 1) == 0) 
		a >>= 1; 

	/* من هنا وصاعدًا العدد الأول فرديٌ دائمًا */
	/* From here on, 'a' is always odd. */
	do { 
		/* إن كان العدد الثاني زوجيًا، تحذف جميع عوامل العدد 2 من العدد الثاني */
		while ((b > 1) == 0) 
			b >>= 1; 

		/* أصبح العددان فرديين. يجب أن يكون العدد الأول أصغر من الثاني أو يساويه
		لذا يجب التبديل بينهما إن دعت الحاجة إلى ذلك
		بعدها يعطى العدد الثاني قيمة جديدة (وهي قيمة زوجية)
		b = b - a  */
		if (a > b) 
			swap(a, b); // Swap u and v. 

		b = (b - a); 
	} while (b != 0); 

	/* استعادة العوامل المشتركة للعدد 2 */
	return a << k; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int a = 34, b = 17; 
	printf("Gcd of given numbers is %d\n", gcd(a, b)); 
	return 0; 
}
  • بايثون:
def gcd(a, b) : 

	# GCD(0, b) == b; GCD(a, 0) == a, 
	# GCD(0, 0) == 0 
	if (a == 0) : 
		return b 
	
	if (b == 0) : 
		return a 

	# k حساب قيمة
	# والتي تمثل أكبر أس للعدد 2 والذي يقبل العددان المعطيان القسمة عليه
	k = 0
	
	while(((a | b) & 1) == 0) : 
		a = a >> 1
		b = b >> 1
		k = k + 1
		
	# الاستمرار في القسمة على 2 إلى أن يصبح العدد الأول فرديًا
	while ((a & 1) == 0) : 
		a = a >> 1

	# من هنا وصاعدًا العدد الأول فرديٌ دائمًا 
	while(b != 0) : 
		
		# إن كان العدد الثاني زوجيًا، تحذف جميع عوامل العدد 2 من العدد الثاني
		while ((b & 1) == 0) : 
			b = b >> 1

		# أصبح العددان فرديين. يجب أن يكون العدد الأول أصغر من الثاني أو يساويه
		# لذا يجب التبديل بينهما إن دعت الحاجة إلى ذلك
		# بعدها يعطى العدد الثاني قيمة جديدة (وهي قيمة زوجية)
		# b = b - a 
		if (a > b) : 
		
			# تبديل قيم المتغيرين 
			temp = a 
			a = b 
			b = temp 

		b = (b - a) 
	
	# استعادة العوامل المشتركة للعدد 2
	return (a << k) 

# اختبار الدالة السابقة
a = 34
b = 17

print("Gcd of given numbers is ", gcd(a, b))
  • جافا:
import java.io.*; 

class GFG 
{ 

	static int gcd(int a, int b) 
	{ 
		// GCD(0, b) == b; GCD(a, 0) == a, 
		// GCD(0, 0) == 0 
		if (a == 0) 
			return b; 
		if (b == 0) 
			return a; 

		/* k حساب قيمة
		والتي تمثل أكبر أس للعدد 2 والذي يقبل العددان المعطيان القسمة عليه */ 
		int k; 
		for (k = 0; ((a | b) & 1) == 0; ++k) 
		{ 
			a >>= 1; 
			b >>= 1; 
		} 

		// الاستمرار في القسمة على 2 إلى أن يصبح العدد الأول فرديًا
		while ((a & 1) == 0) 
			a >>= 1; 

		// من هنا وصاعدًا العدد الأول فرديٌ دائمًا 
		do { 
			// إن كان العدد الثاني زوجيًا، تحذف جميع عوامل العدد 2 من العدد الثاني
			while ((b & 1) == 0) 
				b >>= 1; 

			/* أصبح العددان فرديين. يجب أن يكون العدد الأول أصغر من الثاني أو يساويه
			لذا يجب التبديل بينهما إن دعت الحاجة إلى ذلك
			بعدها يعطى العدد الثاني قيمة جديدة (وهي قيمة زوجية)
		b = b - a  */
			if (a > b) 
			{ 

				// التبديل بين قيم المتغيرين 
				int temp = a; 
				a = b; 
				b = temp; 
			} 

			b = (b - a); 
		} while (b != 0); 

		// استعادة العوامل المشتركة للعدد 2
		return a << k; 
	} 

	// اختبار الدالة السابقة
	public static void main(String args[]) 
	{ 
		int a = 34, b = 17; 

		System.out.println("Gcd of given " + 
							"numbers is " + 
								gcd(a, b)); 
	} 
}

الطريقة التعاودية

  • C++‎:
#include <bits/stdc++.h> 
using namespace std; 

int gcd(int a, int b) 
{ 
	if (a == b) 
		return a; 

	// GCD(0, b) == b; GCD(a, 0) == a, 
	// GCD(0, 0) == 0 
	if (a == 0) 
		return b; 
	if (b == 0) 
		return a; 

	// البحث عن عوامل العدد 2
	if (~a & 1) // العدد الأول زوجي 
	{ 
		if (b & 1) // العدد الثاني فردي 
			return gcd(a >> 1, b); 
		else // كلا العددين زوجي
			return gcd(a >> 1, b >> 1) << 1; 
	} 

	if (~b & 1) // العدد الأول فردي والثاني زوجي
		return gcd(a, b >> 1); 

	// إنقاص قيمة العدد الأكبر
	if (a > b) 
		return gcd((a - b) >> 1, b); 

	return gcd((b - a) >> 1, a); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int a = 34, b = 17; 
	printf("Gcd of given numbers is %d\n", 
							gcd(a, b)); 
	return 0; 
}
  • بايثون:
def gcd(a, b) : 
	
	if (a == b) : 
		return a 

	# GCD(0, b) == b; GCD(a, 0) == a, 
	# GCD(0, 0) == 0 
	if (a == 0) : 
		return b 

	if (b == 0) : 
		return a 

	# البحث عن عوامل العدد 2
	# العدد الأول زوجي
	if ((~a & 1)== 1 ) :
		
		# العدد الثاني فردي
		if ((b & 1)== 1) :	 
			return gcd(a >> 1, b) 
		else : 
			# كلا العددين زوجي
			return (gcd(a >> 1, b >> 1) << 1) 
	
	# العدد الأول فردي والثاني زوجي
	if ((~b & 1)== 1) : 
		return gcd(a, b >> 1) 

	# إنقاص قيمة العدد الأكبر
	if (a > b) : 
		return gcd((a - b) >> 1, b) 

	return gcd((b - a) >> 1, a) 

# اختبار الدالة السابقة 
a, b = 34, 17
print("Gcd of given numbers is ", 
					gcd(a, b))
  • جافا:
import java.io.*; 

class GFG 
{ 

	static int gcd(int a, int b) 
	{ 
		if (a == b) 
			return a; 

		// GCD(0, b) == b; GCD(a, 0) == a, 
		// GCD(0, 0) == 0 
		if (a == 0) 
			return b; 
		if (b == 0) 
			return a; 

		// البحث عن عوامل العدد 2
		if ((~a & 1) == 1) // العدد الأول زوجي
		{ 
			if ((b & 1) == 1) // العدد الثاني فردي
				return gcd(a >> 1, b); 

			else // كلا العددين زوجي
				return gcd(a >> 1, b >> 1) << 1; 
		} 

		// العدد الأول فردي، والثاني زوجي
		if ((~b & 1) == 1) 
			return gcd(a, b >> 1); 

		// إنقاص قيمة العدد الأكبر 
		if (a > b) 
			return gcd((a - b) >> 1, b); 

		return gcd((b - a) >> 1, a); 
	} 

	// اختبار الدالة السابقة
	public static void main(String args[]) 
	{ 
		int a = 34, b = 17; 
		System.out.println("Gcd of given" + 
							"numbers is " + 
								gcd(a, b)); 
	} 
}

مصادر

تصنيفات: الخوارزميات

مجلوبة من «https://wiki.hsoub.com/index.php?title=Algorithms/GCD&oldid=29056»