BWAPI: SPAR/AIModule/BWTA/vendors/CGAL/CGAL/extended_euclidean

Go to the documentation of this file.
00001 // Copyright (c) 2006-2007 Max-Planck-Institute Saarbruecken (Germany).
00002 // All rights reserved.
00003 //
00004 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or
00005 // modify it under the terms of the GNU Lesser General Public License as
00006 // published by the Free Software Foundation; version 2.1 of the License.
00007 // See the file LICENSE.LGPL distributed with CGAL.
00008 //
00009 // Licensees holding a valid commercial license may use this file in
00010 // accordance with the commercial license agreement provided with the software.
00011 //
00012 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00013 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00014 //
00015 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Algebraic_foundations/include/CGAL/extended_euclidean_algorithm.h $
00016 // $Id: extended_euclidean_algorithm.h 42664 2008-03-31 12:43:38Z hemmer $
00017 //
00018 // Author(s)     : Michael Hemmer, Dominik H�lse
00019 //
00020 // ============================================================================
00021 
00022 #ifndef CGAL_EXTENDED_EUCLIDEAN_ALGORITHM_H
00023 #define CGAL_EXTENDED_EUCLIDEAN_ALGORITHM_H 1
00024 
00025 #include <CGAL/basic.h>
00026 #include <vector>
00027 
00028 CGAL_BEGIN_NAMESPACE
00029 
00030 // EEA computing the normalized gcd
00031 // Modern Computer Algebra (Hardcover)
00032 // by Joachim von zur Gathen (Author), J�rgen Gerhard (Author) 
00033 // Publisher: Cambridge University Press; 2 edition (September 1, 2003)
00034 //  Language: English
00035 // ISBN-10: 0521826462
00036 // ISBN-13: 978-0521826464
00037 // pp.: 55
00038  
00039 template< class AS > 
00040 AS extended_euclidean_algorithm(const AS& f, const AS& g, AS& s_, AS& t_){
00041     typename Algebraic_structure_traits<AS>::Integral_division idiv;
00042     typename Algebraic_structure_traits<AS>::Div div;
00043     typename Algebraic_structure_traits<AS>::Unit_part unit_part; 
00044 
00045     std::vector<AS> p,r,s,t,q; 
00046     p.push_back(unit_part(f));   
00047     r.push_back(idiv(f,p[0]));   
00048     s.push_back(idiv(AS(1),p[0])); 
00049     t.push_back(AS(0));  
00050     q.push_back(AS(0));
00051     
00052     p.push_back(unit_part(g));
00053     r.push_back(idiv(g,p[1]));
00054     s.push_back(AS(0));
00055     t.push_back(idiv(AS(1),p[1]));  
00056     
00057     int i = 1; 
00058     while(!is_zero(r[i])){
00059         q.push_back(div(r[i-1],r[i]));
00060         r.push_back(r[i-1]-q[i]*r[i]);
00061         p.push_back(unit_part(r[i+1]));
00062         r[i+1] = idiv(r[i+1],p[i+1]);
00063         s.push_back(idiv(s[i-1]-q[i]*s[i],p[i+1]));
00064         t.push_back(idiv(t[i-1]-q[i]*t[i],p[i+1])); 
00065         i++;
00066     }
00067     
00068     s_=s[i-1];
00069     t_=t[i-1];
00070     AS h = r[i-1];
00071     CGAL_precondition( h == f*s_ + g*t_);
00072     return h; 
00073 }
00074 
00075 CGAL_END_NAMESPACE
00076 
00077 #endif // NiX_EXTENDED_EUCLIDEAN_ALGORITHM_H //