Mercurial > hg > octave-nkf

annotate src/DLD-FUNCTIONS/gcd.cc @ 12575:d0b799dafede

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Grammarcheck files for 3.4.1 release.
author Rik <octave@nomad.inbox5.com>
date Mon, 04 Apr 2011 15:33:46 -0700
parents 01f703952eff
children 5fa482628bf6
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
1 /*
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
2
11523
fd0a3ac60b0e update copyright notices
John W. Eaton <jwe@octave.org>
parents: 11489
diff changeset
3 Copyright (C) 2004-2011 David Bateman
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
4 Copyright (C) 2010 Jaroslav Hajek, Jordi Gutiérrez Hermoso
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
5
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
6 This file is part of Octave.
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
7
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
8 Octave is free software; you can redistribute it and/or modify it
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
9 under the terms of the GNU General Public License as published by the
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
10 Free Software Foundation; either version 3 of the License, or (at your
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
11 option) any later version.
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
12
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
13 Octave is distributed in the hope that it will be useful, but WITHOUT
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
16 for more details.
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
17
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
18 You should have received a copy of the GNU General Public License
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
19 along with Octave; see the file COPYING. If not, see
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 7001
diff changeset
20 <http://www.gnu.org/licenses/>.
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
21
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
22 */
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
23
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
24 #ifdef HAVE_CONFIG_H
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
25 #include <config.h>
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
26 #endif
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
27
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
28 #include "dNDArray.h"
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
29 #include "CNDArray.h"
7815
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
30 #include "fNDArray.h"
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
31 #include "fCNDArray.h"
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
32 #include "lo-mappers.h"
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
33 #include "oct-binmap.h"
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
34
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
35 #include "defun-dld.h"
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
36 #include "error.h"
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
37 #include "oct-obj.h"
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
38
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
39 static double
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
40 simple_gcd (double a, double b)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
41 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
42 if (! xisinteger (a) || ! xisinteger (b))
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
43 (*current_liboctave_error_handler)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
44 ("gcd: all values must be integers");
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
45
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
46 double aa = fabs (a);
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
47 double bb = fabs (b);
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
48
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
49 while (bb != 0)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
50 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
51 double tt = fmod (aa, bb);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
52 aa = bb;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
53 bb = tt;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
54 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
55
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
56 return aa;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
57 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
58
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
59 // Don't use the Complex and FloatComplex typedefs because we need to
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
60 // refer to the actual float precision FP in the body (and when gcc
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
61 // implements template aliases from C++0x, can do a small fix here).
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
62 template <typename FP>
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
63 static void
11450
5eb10763069f substitute and use LAPACK_LIBS in mkoctfile script
John W. Eaton <jwe@octave.org>
parents: 11064
diff changeset
64 divide (const std::complex<FP>& a, const std::complex<FP>& b,
5eb10763069f substitute and use LAPACK_LIBS in mkoctfile script
John W. Eaton <jwe@octave.org>
parents: 11064
diff changeset
65 std::complex<FP>& q, std::complex<FP>& r)
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
66 {
11450
5eb10763069f substitute and use LAPACK_LIBS in mkoctfile script
John W. Eaton <jwe@octave.org>
parents: 11064
diff changeset
67 FP qr = gnulib::floor ((a/b).real () + 0.5);
5eb10763069f substitute and use LAPACK_LIBS in mkoctfile script
John W. Eaton <jwe@octave.org>
parents: 11064
diff changeset
68 FP qi = gnulib::floor ((a/b).imag () + 0.5);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
69
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
70 q = std::complex<FP> (qr, qi);
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
71
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
72 r = a - q*b;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
73 }
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
74
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
75 template <typename FP>
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
76 static std::complex<FP>
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
77 simple_gcd (const std::complex<FP>& a, const std::complex<FP>& b)
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
78 {
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
79 if (! xisinteger (a.real ()) || ! xisinteger(a.imag ())
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
80 || ! xisinteger (b.real ()) || ! xisinteger(b.imag ()))
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
81 (*current_liboctave_error_handler)
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
82 ("gcd: all complex parts must be integers");
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
83
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
84 std::complex<FP> aa = a;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
85 std::complex<FP> bb = b;
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
86
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
87 if (abs (aa) < abs (bb))
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
88 std::swap (aa, bb);
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
89
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
90 while (abs (bb) != 0)
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
91 {
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
92 std::complex<FP> qq, rr;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
93 divide (aa, bb, qq, rr);
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
94 aa = bb;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
95 bb = rr;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
96 }
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
97
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
98 return aa;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
99 }
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
100
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
101 template <class T>
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
102 static octave_int<T>
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
103 simple_gcd (const octave_int<T>& a, const octave_int<T>& b)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
104 {
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
105 T aa = a.abs ().value ();
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
106 T bb = b.abs ().value ();
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
107
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
108 while (bb != 0)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
109 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
110 T tt = aa % bb;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
111 aa = bb;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
112 bb = tt;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
113 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
114
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
115 return aa;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
116 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
117
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
118 static double
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
119 extended_gcd (double a, double b, double& x, double& y)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
120 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
121 if (! xisinteger (a) || ! xisinteger (b))
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
122 (*current_liboctave_error_handler)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
123 ("gcd: all values must be integers");
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
124
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
125 double aa = fabs (a);
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
126 double bb = fabs (b);
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
127
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
128 double xx = 0, yy = 1;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
129 double lx = 1, ly = 0;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
130
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
131 while (bb != 0)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
132 {
11489
978802964923 tag call to floor with gnulib::
John W. Eaton <jwe@octave.org>
parents: 11450
diff changeset
133 double qq = gnulib::floor (aa / bb);
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
134 double tt = fmod (aa, bb);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
135
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
136 aa = bb;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
137 bb = tt;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
138
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
139 double tx = lx - qq*xx;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
140 lx = xx;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
141 xx = tx;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
142
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
143 double ty = ly - qq*yy;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
144 ly = yy;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
145 yy = ty;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
146 }
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
147
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
148 x = a >= 0 ? lx : -lx;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
149 y = b >= 0 ? ly : -ly;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
150
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
151 return aa;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
152 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
153
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
154 template <typename FP>
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
155 static std::complex<FP>
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
156 extended_gcd (const std::complex<FP>& a, const std::complex<FP>& b,
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
157 std::complex<FP>& x, std::complex<FP>& y)
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
158 {
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
159 if (! xisinteger (a.real ()) || ! xisinteger(a.imag ())
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
160 || ! xisinteger (b.real ()) || ! xisinteger(b.imag ()))
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
161 (*current_liboctave_error_handler)
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
162 ("gcd: all complex parts must be integers");
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
163
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
164 std::complex<FP> aa = a, bb = b;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
165 bool swapped = false;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
166 if (abs (aa) < abs (bb))
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
167 {
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
168 std::swap (aa, bb);
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
169 swapped = true;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
170 }
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
171
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
172 std::complex<FP> xx = 0, lx = 1;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
173 std::complex<FP> yy = 1, ly = 0;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
174
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
175 while (abs(bb) != 0)
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
176 {
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
177 std::complex<FP> qq, rr;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
178 divide (aa, bb, qq, rr);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
179 aa = bb;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
180 bb = rr;
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
181
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
182 std::complex<FP> tx = lx - qq*xx;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
183 lx = xx;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
184 xx = tx;
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
185
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
186 std::complex<FP> ty = ly - qq*yy;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
187 ly = yy;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
188 yy = ty;
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
189 }
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
190
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
191 x = lx;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
192 y = ly;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
193
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
194 if (swapped)
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
195 std::swap (x, y);
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
196
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
197 return aa;
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
198 }
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
199
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
200 template <class T>
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
201 static octave_int<T>
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
202 extended_gcd (const octave_int<T>& a, const octave_int<T>& b,
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
203 octave_int<T>& x, octave_int<T>& y)
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
204 {
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
205 T aa = a.abs ().value ();
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
206 T bb = b.abs ().value ();
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
207 T xx = 0, lx = 1;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
208 T yy = 1, ly = 0;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
209
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
210 while (bb != 0)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
211 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
212 T qq = aa / bb;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
213 T tt = aa % bb;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
214 aa = bb;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
215 bb = tt;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
216
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
217 T tx = lx - qq*xx;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
218 lx = xx;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
219 xx = tx;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
220
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
221 T ty = ly - qq*yy;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
222 ly = yy;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
223 yy = ty;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
224 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
225
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
226 x = octave_int<T> (lx) * a.signum ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
227 y = octave_int<T> (ly) * b.signum ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
228
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
229 return aa;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
230 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
231
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
232 template<class NDA>
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
233 static octave_value
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
234 do_simple_gcd (const octave_value& a, const octave_value& b)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
235 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
236 typedef typename NDA::element_type T;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
237 octave_value retval;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
238
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
239 if (a.is_scalar_type () && b.is_scalar_type ())
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
240 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
241 // Optimize scalar case.
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
242 T aa = octave_value_extract<T> (a);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
243 T bb = octave_value_extract<T> (b);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
244 retval = simple_gcd (aa, bb);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
245 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
246 else
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
247 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
248 NDA aa = octave_value_extract<NDA> (a);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
249 NDA bb = octave_value_extract<NDA> (b);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
250 retval = binmap<T> (aa, bb, simple_gcd, "gcd");
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
251 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
252
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
253 return retval;
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
254 }
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
255
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
256 // Dispatcher
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
257 static octave_value
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
258 do_simple_gcd (const octave_value& a, const octave_value& b)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
259 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
260 octave_value retval;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
261 builtin_type_t btyp = btyp_mixed_numeric (a.builtin_type (),
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
262 b.builtin_type ());
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
263 switch (btyp)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
264 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
265 case btyp_double:
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
266 if (a.is_sparse_type () && b.is_sparse_type ())
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
267 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
268 retval = do_simple_gcd<SparseMatrix> (a, b);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
269 break;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
270 }
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
271 // fall through!
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
272
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
273 case btyp_float:
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
274 retval = do_simple_gcd<NDArray> (a, b);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
275 break;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
276
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
277 #define MAKE_INT_BRANCH(X) \
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
278 case btyp_ ## X: \
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
279 retval = do_simple_gcd<X ## NDArray> (a, b); \
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
280 break
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
281
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
282 MAKE_INT_BRANCH (int8);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
283 MAKE_INT_BRANCH (int16);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
284 MAKE_INT_BRANCH (int32);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
285 MAKE_INT_BRANCH (int64);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
286 MAKE_INT_BRANCH (uint8);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
287 MAKE_INT_BRANCH (uint16);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
288 MAKE_INT_BRANCH (uint32);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
289 MAKE_INT_BRANCH (uint64);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
290
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
291 #undef MAKE_INT_BRANCH
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
292
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
293 case btyp_complex:
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
294 retval = do_simple_gcd<ComplexNDArray> (a, b);
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
295 break;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
296
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
297 case btyp_float_complex:
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
298 retval = do_simple_gcd<FloatComplexNDArray> (a, b);
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
299 break;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
300
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
301 default:
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
302 error ("gcd: invalid class combination for gcd: %s and %s\n",
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
303 a.class_name ().c_str (), b.class_name ().c_str ());
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
304 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
305
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
306 if (btyp == btyp_float)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
307 retval = retval.float_array_value ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
308
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
309 return retval;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
310 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
311
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
312 template<class NDA>
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
313 static octave_value
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
314 do_extended_gcd (const octave_value& a, const octave_value& b,
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
315 octave_value& x, octave_value& y)
7815
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
316 {
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
317 typedef typename NDA::element_type T;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
318 octave_value retval;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
319
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
320 if (a.is_scalar_type () && b.is_scalar_type ())
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
321 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
322 // Optimize scalar case.
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
323 T aa = octave_value_extract<T> (a);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
324 T bb = octave_value_extract<T> (b);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
325 T xx, yy;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
326 retval = extended_gcd (aa, bb, xx, yy);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
327 x = xx;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
328 y = yy;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
329 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
330 else
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
331 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
332 NDA aa = octave_value_extract<NDA> (a);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
333 NDA bb = octave_value_extract<NDA> (b);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
334
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
335 dim_vector dv = aa.dims ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
336 if (aa.numel () == 1)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
337 dv = bb.dims ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
338 else if (bb.numel () != 1 && bb.dims () != dv)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
339 gripe_nonconformant ("gcd", a.dims (), b.dims ());
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
340
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
341 NDA gg (dv), xx (dv), yy (dv);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
342
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
343 const T *aptr = aa.fortran_vec ();
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
344 const T *bptr = bb.fortran_vec ();
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
345
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
346 bool inca = aa.numel () != 1;
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
347 bool incb = bb.numel () != 1;
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
348
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
349 T *gptr = gg.fortran_vec ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
350 T *xptr = xx.fortran_vec (), *yptr = yy.fortran_vec ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
351
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
352 octave_idx_type n = gg.numel ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
353 for (octave_idx_type i = 0; i < n; i++)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
354 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
355 octave_quit ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
356
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
357 *gptr++ = extended_gcd (*aptr, *bptr, *xptr++, *yptr++);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
358
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
359 aptr += inca;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
360 bptr += incb;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
361 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
362
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
363 x = xx;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
364 y = yy;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
365
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
366 retval = gg;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
367 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
368
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
369 return retval;
7815
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
370 }
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
371
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
372 // Dispatcher
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
373 static octave_value
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
374 do_extended_gcd (const octave_value& a, const octave_value& b,
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
375 octave_value& x, octave_value& y)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
376 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
377 octave_value retval;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
378
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
379 builtin_type_t btyp = btyp_mixed_numeric (a.builtin_type (),
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
380 b.builtin_type ());
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
381 switch (btyp)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
382 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
383 case btyp_double:
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
384 case btyp_float:
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
385 retval = do_extended_gcd<NDArray> (a, b, x, y);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
386 break;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
387
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
388 #define MAKE_INT_BRANCH(X) \
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
389 case btyp_ ## X: \
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
390 retval = do_extended_gcd<X ## NDArray> (a, b, x, y); \
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
391 break
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
392
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
393 MAKE_INT_BRANCH (int8);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
394 MAKE_INT_BRANCH (int16);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
395 MAKE_INT_BRANCH (int32);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
396 MAKE_INT_BRANCH (int64);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
397 MAKE_INT_BRANCH (uint8);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
398 MAKE_INT_BRANCH (uint16);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
399 MAKE_INT_BRANCH (uint32);
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
400 MAKE_INT_BRANCH (uint64);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
401
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
402 #undef MAKE_INT_BRANCH
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
403
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
404 case btyp_complex:
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
405 retval = do_extended_gcd<ComplexNDArray> (a, b, x, y);
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
406 break;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
407
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
408 case btyp_float_complex:
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
409 retval = do_extended_gcd<FloatComplexNDArray> (a, b, x, y);
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
410 break;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
411
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
412 default:
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
413 error ("gcd: invalid class combination for gcd: %s and %s\n",
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
414 a.class_name ().c_str (), b.class_name ().c_str ());
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
415 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
416
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
417 // For consistency.
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
418 if (! error_state && a.is_sparse_type () && b.is_sparse_type ())
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
419 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
420 retval = retval.sparse_matrix_value ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
421 x = x.sparse_matrix_value ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
422 y = y.sparse_matrix_value ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
423 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
424
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
425 if (btyp == btyp_float)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
426 {
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
427 retval = retval.float_array_value ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
428 x = x.float_array_value ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
429 y = y.float_array_value ();
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
430 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
431
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
432 return retval;
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
433 }
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
434
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
435 DEFUN_DLD (gcd, args, nargout,
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
436 "-*- texinfo -*-\n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
437 @deftypefn {Loadable Function} {@var{g} =} gcd (@var{a1}, @var{a2}, @dots{})\n\
9141
c1fff751b5a8 Update section 17.1 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9064
diff changeset
438 @deftypefnx {Loadable Function} {[@var{g}, @var{v1}, @dots{}] =} gcd (@var{a1}, @var{a2}, @dots{})\n\
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
439 \n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
440 Compute the greatest common divisor of @var{a1}, @var{a2}, @dots{}. If more\n\
9141
c1fff751b5a8 Update section 17.1 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9064
diff changeset
441 than one argument is given all arguments must be the same size or scalar.\n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
442 In this case the greatest common divisor is calculated for each element\n\
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
443 individually. All elements must be ordinary or Gaussian (complex)\n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
444 integers. Note that for Gaussian integers, the gcd is not unique up to\n\
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
445 units (multiplication by 1, -1, @var{i} or -@var{i}), so an arbitrary\n\
11553
01f703952eff Improve docstrings for functions in DLD-FUNCTIONS directory.
Rik <octave@nomad.inbox5.com>
parents: 11523
diff changeset
446 greatest common divisor amongst four possible is returned. For example,\n\
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
447 \n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
448 @noindent\n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
449 and\n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
450 \n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
451 @example\n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
452 @group\n\
9141
c1fff751b5a8 Update section 17.1 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9064
diff changeset
453 gcd ([15, 9], [20, 18])\n\
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
454 @result{} 5 9\n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
455 @end group\n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
456 @end example\n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
457 \n\
9141
c1fff751b5a8 Update section 17.1 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9064
diff changeset
458 Optional return arguments @var{v1}, etc., contain integer vectors such\n\
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
459 that,\n\
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
460 \n\
9167
1231b1762a9a Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9141
diff changeset
461 @tex\n\
1231b1762a9a Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9141
diff changeset
462 $g = v_1 a_1 + v_2 a_2 + \\cdots$\n\
1231b1762a9a Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9141
diff changeset
463 @end tex\n\
8517
81d6ab3ac93c Allow documentation tobe built for other formats than tex and info
sh@sh-laptop
parents: 8377
diff changeset
464 @ifnottex\n\
10840
89f4d7e294cc Grammarcheck .cc files
Rik <octave@nomad.inbox5.com>
parents: 10552
diff changeset
465 \n\
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
466 @example\n\
6547
4fb053f24fd6 [project @ 2007-04-19 21:47:40 by jwe]
jwe
parents: 5985
diff changeset
467 @var{g} = @var{v1} .* @var{a1} + @var{v2} .* @var{a2} + @dots{}\n\
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
468 @end example\n\
10840
89f4d7e294cc Grammarcheck .cc files
Rik <octave@nomad.inbox5.com>
parents: 10552
diff changeset
469 \n\
8517
81d6ab3ac93c Allow documentation tobe built for other formats than tex and info
sh@sh-laptop
parents: 8377
diff changeset
470 @end ifnottex\n\
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
471 \n\
9141
c1fff751b5a8 Update section 17.1 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 9064
diff changeset
472 @seealso{lcm, factor}\n\
5642
2618a0750ae6 [project @ 2006-03-06 21:26:48 by jwe]
jwe
parents: 5307
diff changeset
473 @end deftypefn")
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
474 {
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
475 octave_value_list retval;
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
476
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
477 int nargin = args.length ();
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
478
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
479 if (nargin > 1)
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
480 {
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
481 if (nargout > 1)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
482 {
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
483 retval.resize (nargin + 1);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
484
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
485 retval(0) = do_extended_gcd (args(0), args(1), retval(1), retval(2));
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
486
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
487 for (int j = 2; j < nargin; j++)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
488 {
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
489 octave_value x;
11061
604dfbaf5010 Fix off-by-one and typo bugs in gcd
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11021
diff changeset
490 retval(0) = do_extended_gcd (retval(0), args(j),
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
491 x, retval(j+1));
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
492 for (int i = 0; i < j; i++)
11061
604dfbaf5010 Fix off-by-one and typo bugs in gcd
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11021
diff changeset
493 retval(i+1).assign (octave_value::op_el_mul_eq, x);
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
494
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
495 if (error_state)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
496 break;
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
497 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
498 }
7815
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
499 else
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
500 {
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
501 retval(0) = do_simple_gcd (args(0), args(1));
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
502
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
503 for (int j = 2; j < nargin; j++)
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
504 {
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
505 retval(0) = do_simple_gcd (retval(0), args(j));
11064
61a6c99d8ff7 gcd.cc: style fixes
John W. Eaton <jwe@octave.org>
parents: 11062
diff changeset
506
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
507 if (error_state)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
508 break;
10154
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
509 }
40dfc0c99116 DLD-FUNCTIONS/*.cc: untabify
John W. Eaton <jwe@octave.org>
parents: 9167
diff changeset
510 }
7815
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
511 }
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
512 else
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
513 print_usage ();
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
514
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
515 return retval;
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
516 }
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
517
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
518 /*
7815
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
519
11021
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
520 %!assert(gcd (200, 300, 50, 35), 5)
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
521 %!assert(gcd (int16(200), int16(300), int16(50), int16(35)), int16(5))
0ee74d581c00 optimize & rewrite gcd
Jaroslav Hajek <highegg@gmail.com>
parents: 10840
diff changeset
522 %!assert(gcd (uint64(200), uint64(300), uint64(50), uint64(35)), uint64(5))
11062
88d78ee12ee8 Implement gcd for Gaussian (complex) integers
Jordi Gutiérrez Hermoso <jordigh@gmail.com>
parents: 11061
diff changeset
523 %!assert(gcd (18-i, -29+3i), -3-4i)
7815
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
524
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
525 %!error <Invalid call to gcd.*> gcd ();
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
526
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
527 %!test
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
528 %! s.a = 1;
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
529 %! fail("gcd (s)");
a41df65f3f00 Add some single precision test code and fix resulting bugs
David Bateman <dbateman@free.fr>
parents: 7017
diff changeset
530
4864
d49d761c8c93 [project @ 2004-04-16 16:01:11 by jwe]
jwe
parents:
diff changeset
531 */