00001 /* 00002 * Copyright 2007 Martin von Gagern 00003 * 00004 * 00005 * This file is part of mqn2mps. 00006 * 00007 * mqn2mps is free software; you can redistribute it and/or modify 00008 * it under the terms of the GNU General Public License as published by 00009 * the Free Software Foundation; either version 3 of the License, or 00010 * (at your option) any later version. 00011 * 00012 * mqn2mps is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00019 */ 00020 00021 00022 #ifndef EUCLID_HH 00023 #define EUCLID_HH 00024 00025 /** 00026 * @file 00027 * Euclidean algorithm to compute gcd() and lcm(). 00028 */ 00029 00030 /** 00031 * Computes the greates common divisor. 00032 * 00033 * The implementation can handle negative numbers and an arbitrary 00034 * order of arguments. The implementation as a template allows its use 00035 * for different types. 00036 * 00037 * @param a the first number. 00038 * @param b the second number. 00039 * @return the greatest common divisor of @e a and @e b. 00040 */ 00041 template<typename T> inline T gcd(T a, T b) { 00042 T d; 00043 if (a<0) a = -a; 00044 if (b<0) b = -b; 00045 if (a<b) { d = a; a = b; b = d; } 00046 if (b==0) return a; 00047 do { d=a%b; a=b; b=d; } while(d!=0); 00048 return a; 00049 } 00050 00051 /** 00052 * Computes the least common multiple. 00053 * 00054 * The implementation can handle negative numbers and an arbitrary 00055 * order of arguments. The implementation as a template allows its use 00056 * for different types. 00057 * 00058 * @param a the first number. 00059 * @param b the second number. 00060 * @return the least common multiple of @e a and @e b. 00061 */ 00062 template<typename T> inline T lcm(T a, T b) { 00063 return a*b/gcd(a,b); 00064 } 00065 00066 #endif // ifndef EUCLID_HH
1.6.0