المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية

اللبن Yoghurt
24-9-2016
عدم التأثير
23-7-2018
هارون الرشيد وبغداد.
2024-01-06
الهندسة الجينية والزراعة
2023-11-04
شعر المسلمين وواقع الحركة الشعرية
17-6-2017
Enzymes Involved in Oxygen Activation
25-6-2019

Euclidean Algorithm  
  
2124   03:43 مساءً   date: 18-7-2020
Author : Bach, E. and Shallit, J
Book or Source : Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, 1996.
Page and Part : ...


Read More
Date: 30-9-2020 778
Date: 18-10-2020 626
Date: 5-10-2020 561

Euclidean Algorithm

The Euclidean algorithm, also called Euclid's algorithm, is an algorithm for finding the greatest common divisor of two numbers a and b. The algorithm can also be defined for more general rings than just the integers Z. There are even principal rings which are not Euclidean but where the equivalent of the Euclidean algorithm can be defined. The algorithm for rational numbers was given in Book VII of Euclid's Elements. The algorithm for reals appeared in Book X, making it the earliest example of an integer relation algorithm (Ferguson et al. 1999).

The Euclidean algorithm is an example of a P-problem whose time complexity is bounded by a quadratic function of the length of the input values (Bach and Shallit 1996).

Let a=bq+r, then find a number u which divides both a and b (so that a=su and b=tu), then u also divides r since

 r=a-bq=su-qtu=(s-qt)u.

(1)

Similarly, find a number v which divides b and r (so that  and ), then v divides a since

(2)

Therefore, every common divisor of a and b is a common divisor of b and r, so the procedure can be iterated as follows:

 q_1=|_a/b_|  a=bq_1+r_1  r_1=a-bq_1 ; q_2=|_b/(r_1)_|  b=q_2r_1+r_2  r_2=b-q_2r_1 ; q_3=|_(r_1)/(r_2)_|  r_1=q_3r_2+r_3  r_3=r_1-q_3r_2 ; q_4=|_(r_2)/(r_3)_|  r_2=q_4r_3+r_4  r_4=r_2-q_4r_3 ; q_n=|_(r_(n-2))/(r_(n-1))_|  r_(n-2)=q_nr_(n-1)+r_n  r_n=r_(n-2) ;    -q_nr_(n-1); q_(n+1)=|_(r_(n-1))/(r_n)_|  r_(n-1)=q_(n+1)r_n+0  r_n=r_(n-1)/q_(n+1)

(3)

For integers, the algorithm terminates when q_(n+1) divides r_(n-1) exactly, at which point r_n corresponds to the greatest common divisor of a and bGCD(a,b)=r_n. For real numbers, the algorithm yields either an exact relation or an infinite sequence of approximate relations (Ferguson et al. 1999).

An important consequence of the Euclidean algorithm is finding integers x and y such that

 ax+by=GCD(a,b).

(4)

This can be done by starting with the equation for r_n, substituting for r_(n-1) from the previous equation, and working upward through the equations.

Note that the r_i are just remainders, so the algorithm can be easily applied by hand by repeatedly computing remainders of consecutive terms starting with the two numbers of interest (with the larger of the two written first). As an example, consider applying the algorithm to (a,b)=(42,30). This gives 42, 30, 12, 6, 0, so GCD(42,30)=6. Similarly, applying the algorithm to (144, 55) gives 144, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0, so GCD(144,55)=1 and 144 and 55 are relatively prime.

A concise Wolfram Language implementation can be given as follows.

  Remainder[a_, b_] := Mod[a, b]
  Remainder[a_, 0] := 0
  EuclideanAlgorithmGCD[a_, b_] := FixedPointList[
    {Last[#], Remainder @@ #}&, {a, b}][[-3, 1]]

Lamé showed that the number of steps needed to arrive at the greatest common divisor for two numbers less than n is

 steps<=(lnn)/(lnphi)+(lnsqrt(5))/(lnphi)

(5)

where phi is the golden ratio. Numerically, Lamé's expression evaluates to

 steps<=4.785log_(10)n+1.6723,

(6)

which, for n>=1, is always <=5 times the number of digits in the smaller number (Wells 1986, p. 59). As shown by Lamé's theorem, the worst case occurs when the algorithm is applied to two consecutive Fibonacci numbers. Heilbronn showed that the average number of steps is 12ln2/pi^2lnn=0.843lnn for all pairs (n,b) with b<n. Kronecker showed that the shortest application of the algorithm uses least absolute remainders. The quotients obtained are distributed as shown in the following table (Wagon 1991).

quotient %
1 41.5
2 17.0
3 9.3

Let T(m,n) be the number of divisions required to compute GCD(m,n) using the Euclidean algorithm, and define T(m,0)=0 if m>=0. Then the function T(m,n) is given by the recurrence relation

 T(m,n)={1+T(n,m mod n)   for m>=n; 1+T(n,m)   for m<n.

(7)

Tabulating this function for 0<=m<n gives

 0     ; 0 1    ; 0 1 2   ; 0 1 1 2  ; 0 1 2 3 2 ; 0 1 1 1 2 2

(8)

(OEIS A051010). The maximum numbers of steps for a given n=1, 2, 3, ... are 1, 2, 2, 3, 2, 3, 4, 3, 3, 4, 4, 5, ... (OEIS A034883).

EuclideanAlgorithmT

Consider the function

 T(n)=1/nsum_(0<=m<n)T(m,n)

(9)

giving the average number of steps when n is fixed and m chosen at random (Knuth 1998, pp. 344 and 353-357). The first few values of T(n) are 0, 1/2, 1, 1, 8/5, 7/6, 13/7, 7/4, ... (OEIS A051011 and A051012). Norton (1990) showed that

 T(n)=(12ln2)/(pi^2)[lnn-sum_(d|n)(Lambda(d))/d]+C+1/nsum_(d|n)phi(d)O(d^(-1/6+epsilon)),

(10)

where Lambda(d) is the Mangoldt function and C is Porter's constant (Knuth 1998, pp. 355-356).

EuclideanAlgorithmTau

The related function

 tau(n)=1/(phi(n))sum_(0<=m<n; GCD(m,n)=1)T(m,n)

(11)

where phi(n) is the totient function, gives the average number of divisions when n is fixed and m is a random number coprime to n. Porter (1975) showed that

 tau(n)=(12ln2)/(pi^2)lnn+C+O(n^(-1/6)+epsilon)

(12)

(Knuth 1998, pp. 354-355).

Finally, define

 A(N)=1/(N^2)sum_(1<=m<=N; 1<=n<=N)T(m,n),

(13)

as the average number of divisions when m and n are both chosen at random in [1,N] Norton (1990) proved that

(14)

where  is the derivative of the Riemann zeta function.

There exist 21 quadratic fields in which there is a Euclidean algorithm (Inkeri 1947, Barnes and Swinnerton-Dyer 1952).

For additional details, see Uspensky and Heaslet (1939) and Knuth (1998).

Although various attempts were made to generalize the algorithm to find integer relations between n>=3 variables, none were successful until the discovery of the Ferguson-Forcade algorithm (Ferguson et al. 1999). Several other integer relation algorithms have now been discovered.


REFERENCES:

Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, 1996.

Barnes, E. S. and Swinnerton-Dyer, H. P. F. "The Inhomogeneous Minima of Binary Quadratic Forms. I." Acta Math 87, 259-323, 1952.

Chabert, J.-L. (Ed.). "Euclid's Algorithm." Ch. 4 in A History of Algorithms: From the Pebble to the Microchip. New York: Springer-Verlag, pp. 113-138, 1999.

Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.

Courant, R. and Robbins, H. "The Euclidean Algorithm." §2.4 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 42-51, 1996.

Dunham, W. Journey through Genius: The Great Theorems of Mathematics. New York: Wiley, pp. 69-70, 1990.

Ferguson, H. R. P.; Bailey, D. H.; and Arno, S. "Analysis of PSLQ, An Integer Relation Finding Algorithm." Math. Comput. 68, 351-369, 1999.

Finch, S. R. "Porter-Hansley Constants." §2.18 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 156-160, 2003.

Inkeri, K. "Über den Euklidischen Algorithmus in quadratischen Zahlkörpern." Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1947, 1-35, 1947.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.

Motzkin, T. "The Euclidean Algorithm." Bull. Amer. Math. Soc. 55, 1142-1146, 1949.

Nagell, T. "Euclid's Algorithm." §7 in Introduction to Number Theory. New York: Wiley, pp. 21-23, 1951.

Norton, G. H. "On the Asymptotic Analysis of the Euclidean Algorithm." J. Symb. Comput. 10, 53-58, 1990.

Porter, J. W. "On a Theorem of Heilbronn." Mathematika 22, 20-28, 1975.

Séroul, R. "Euclidean Division" and "The Euclidean Algorithm." §2.1 and 8.1 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 5 and 169-161, 2000.

Sloane, N. J. A. Sequences A034883, A051010, A051011, and A051012 in "The On-Line Encyclopedia of Integer Sequences."

Uspensky, J. V. and Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, 1939.

Wagon, S. "The Ancient and Modern Euclidean Algorithm" and "The Extended Euclidean Algorithm." §8.1 and 8.2 in Mathematica in Action. New York: W. H. Freeman, pp. 247-252 and 252-256, 1991.

Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 59, 1986.




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.