613bec3b803e917ffacd45826b3aecaef6a1d50c
[scilab.git] / scilab / modules / elementary_functions / help / en_US / discrete / gcd.xml
1 <?xml version="1.0" encoding="UTF-8"?>
2 <!--
3  * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
4  * Copyright (C) 2006-2008 - INRIA
5  * Copyright (C) 2012 - 2016 - Scilab Enterprises
6  * Copyright (C) 2017 - Samuel GOUGEON
7  *
8  * This file is hereby licensed under the terms of the GNU GPL v2.0,
9  * pursuant to article 5.3.4 of the CeCILL v.2.1.
10  * This file was originally licensed under the terms of the CeCILL v2.1,
11  * and continues to be available under such terms.
12  * For more information, see the COPYING file which you should have received
13  * along with this program.
14  *
15  -->
16 <refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink"
17         xmlns:svg="http://www.w3.org/2000/svg" xmlns:mml="http://www.w3.org/1998/Math/MathML"
18         xmlns:db="http://docbook.org/ns/docbook" xmlns:scilab="http://www.scilab.org"
19         xml:lang="en" xml:id="gcd">
20     <refnamediv>
21         <refname>gcd</refname>
22         <refpurpose>Greatest Common Divisor</refpurpose>
23     </refnamediv>
24     <refsynopsisdiv>
25         <title>Syntax</title>
26         <synopsis>
27             gpcd = gcd(P)
28             [gpcd, U] = gcd(P)
29         </synopsis>
30     </refsynopsisdiv>
31     <refsection>
32         <title>Arguments</title>
33         <variablelist>
34             <varlistentry>
35                 <term>P</term>
36                 <listitem>
37                     <para>
38                         array of decimal integers, encoded integers, or of polynomials.
39                     </para>
40                 </listitem>
41             </varlistentry>
42             <varlistentry>
43                 <term>gpcd</term>
44                 <listitem>
45                     <para>
46                         single element of <literal>P</literal> type: the greatest
47                         common divisor of all <literal>P</literal> components.
48                     </para>
49                 </listitem>
50             </varlistentry>
51             <varlistentry>
52                 <term>U</term>
53                 <listitem>
54                     <para>
55                         Square matrix of the <literal>P</literal> type, with integer components or
56                         of minimal degrees. Its last column <literal>B = U(:,$)</literal> holds
57                         Bezout coefficients, such that
58                         <literal>B(1)*P(1) + B(2)*P(2) + .... + B($)*P($) == gpcd</literal>.
59                     </para>
60                 </listitem>
61             </varlistentry>
62         </variablelist>
63     </refsection>
64     <refsection>
65         <title>Description</title>
66         <para>
67             <code>[gpcd, U] = gcd(P)</code> computes the greatest common divisor
68             <varname>gpcd</varname> of components of <varname>P</varname>, and an unimodular matrix
69             <varname>U</varname>.
70         </para>
71         <para>
72             If <literal>P</literal> components are decimal or encoded integers, they are priorly
73             converted into <literal>int64</literal> signed integers.
74         </para>
75         <para>
76             If <varname>P</varname> has an unsigned inttype <literal>uint8</literal>,
77             <literal>uint16</literal>, <literal>uint32</literal> or <literal>uint64</literal>,
78             <varname>U</varname> gets the corresponding signed inttype.
79         </para>
80         <para>
81             When a second output is expected, an unimodular matrix <literal>U</literal> of the
82             <literal>P</literal> type is returned, such that
83             <itemizedlist>
84                 <listitem>
85                     <literal>size(U) == [length(P) length(P)]</literal>
86                 </listitem>
87                 <listitem>
88                     <literal>matrix(P,1,-1)*U = [0...0 gpcd]</literal> with
89                     <literal>length(P)-1</literal> leading zeros
90                 </listitem>
91                 <listitem>
92                     <literal>det(U)</literal> is <literal>1</literal> or
93                     <literal>-1</literal>.
94                 </listitem>
95             </itemizedlist>
96         </para>
97         <para>
98             Its last column provides Bezout coefficients.
99         </para>
100         <note>
101             <literal>gcd([0 0])</literal> returns <literal>0</literal>.
102         </note>
103         <warning>
104             For big <varname>P</varname> values (smaller but of the order of 2^63, depending also
105             on the number of input values), results may be corrupted by integer overflow and
106             wrapping (int8(127)+1 == -128).
107         </warning>
108     </refsection>
109     <refsection>
110         <title>Examples</title>
111         <programlisting role="example"><![CDATA[
112 // With polynomials
113 s = %s;
114 p = [s  s*(s+1)^2  2*s^2+s^3];
115 [GCD, U] = gcd(p)
116 p*u
117
118 // With encoded integers
119 V = uint16([2^2*3^5 2^3*3^2 2^2*3^4*5])
120 [GCD, U] = gcd(V)
121 typeof(GCD)
122 typeof(U)
123 V*U
124
125 // With decimal integers
126 V = [2^2*3^5 2^3*3^2 2^2*3^4*5];
127 [GCD, U] = gcd(V)
128 type(GCD)
129 type(U)
130 V*U
131
132 gcd([0 60])
133 gcd([0 0])
134  ]]></programlisting>
135     </refsection>
136     <refsection role="see also">
137         <title>See also</title>
138         <simplelist type="inline">
139             <member>
140                 <link linkend="bezout">bezout</link>
141             </member>
142             <member>
143                 <link linkend="lcm">lcm</link>
144             </member>
145             <member>
146                 <link linkend="factor">factor</link>
147             </member>
148             <member>
149                 <link linkend="prod">prod</link>
150             </member>
151             <member>
152                 <link linkend="hermit">hermit</link>
153             </member>
154         </simplelist>
155     </refsection>
156     <refsection role="history">
157         <title>History</title>
158         <revhistory>
159             <revision>
160                 <revnumber>6.0.1</revnumber>
161                 <revdescription>
162                     <itemizedlist>
163                         <listitem>
164                             <literal>int64</literal> and <literal>uint64</literal> input integers
165                             are now supported.
166                         </listitem>
167                         <listitem>
168                             The input <literal>P</literal> may be any array instead of a row vector.
169                         </listitem>
170                     </itemizedlist>
171                 </revdescription>
172             </revision>
173         </revhistory>
174     </refsection></refentry>