[18190] | 1 | /* mpz_lcm -- mpz/mpz least common multiple. |
---|

[15293] | 2 | |
---|

[18190] | 3 | Copyright 1996, 2000, 2001 Free Software Foundation, Inc. |
---|

[15293] | 4 | |
---|

| 5 | This file is part of the GNU MP Library. |
---|

| 6 | |
---|

| 7 | The GNU MP Library is free software; you can redistribute it and/or modify |
---|

| 8 | it under the terms of the GNU Lesser General Public License as published by |
---|

| 9 | the Free Software Foundation; either version 2.1 of the License, or (at your |
---|

| 10 | option) any later version. |
---|

| 11 | |
---|

| 12 | The GNU MP Library is distributed in the hope that it will be useful, but |
---|

| 13 | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
---|

| 14 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public |
---|

| 15 | License for more details. |
---|

| 16 | |
---|

| 17 | You should have received a copy of the GNU Lesser General Public License |
---|

| 18 | along with the GNU MP Library; see the file COPYING.LIB. If not, write to |
---|

| 19 | the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
---|

| 20 | MA 02111-1307, USA. */ |
---|

| 21 | |
---|

| 22 | #include "gmp.h" |
---|

| 23 | #include "gmp-impl.h" |
---|

| 24 | #include "longlong.h" |
---|

| 25 | |
---|

| 26 | |
---|

| 27 | void |
---|

| 28 | mpz_lcm (mpz_ptr r, mpz_srcptr u, mpz_srcptr v) |
---|

| 29 | { |
---|

| 30 | mpz_t g; |
---|

| 31 | mp_size_t usize, vsize, size; |
---|

| 32 | TMP_DECL (marker); |
---|

| 33 | |
---|

[18190] | 34 | usize = SIZ (u); |
---|

| 35 | vsize = SIZ (v); |
---|

[15293] | 36 | if (usize == 0 || vsize == 0) |
---|

| 37 | { |
---|

| 38 | SIZ (r) = 0; |
---|

| 39 | return; |
---|

| 40 | } |
---|

[18190] | 41 | usize = ABS (usize); |
---|

| 42 | vsize = ABS (vsize); |
---|

[15293] | 43 | |
---|

[18190] | 44 | if (vsize == 1) |
---|

| 45 | { |
---|

| 46 | mp_limb_t vl, gl, c; |
---|

| 47 | mp_srcptr up; |
---|

| 48 | mp_ptr rp; |
---|

| 49 | |
---|

| 50 | one: |
---|

| 51 | MPZ_REALLOC (r, usize+1); |
---|

| 52 | |
---|

| 53 | up = PTR(u); |
---|

| 54 | vl = PTR(v)[0]; |
---|

| 55 | gl = mpn_gcd_1 (up, usize, vl); |
---|

| 56 | vl /= gl; |
---|

| 57 | |
---|

| 58 | rp = PTR(r); |
---|

| 59 | c = mpn_mul_1 (rp, up, usize, vl); |
---|

| 60 | rp[usize] = c; |
---|

| 61 | usize += (c != 0); |
---|

| 62 | SIZ(r) = usize; |
---|

| 63 | return; |
---|

| 64 | } |
---|

| 65 | |
---|

| 66 | if (usize == 1) |
---|

| 67 | { |
---|

| 68 | usize = vsize; |
---|

| 69 | MPZ_SRCPTR_SWAP (u, v); |
---|

| 70 | goto one; |
---|

| 71 | } |
---|

| 72 | |
---|

| 73 | TMP_MARK (marker); |
---|

[15293] | 74 | size = MAX (usize, vsize); |
---|

| 75 | MPZ_TMP_INIT (g, size); |
---|

| 76 | |
---|

| 77 | mpz_gcd (g, u, v); |
---|

| 78 | mpz_divexact (g, u, g); |
---|

| 79 | mpz_mul (r, g, v); |
---|

| 80 | |
---|

[18190] | 81 | SIZ (r) = ABS (SIZ (r)); /* result always positive */ |
---|

| 82 | |
---|

[15293] | 83 | TMP_FREE (marker); |
---|

| 84 | } |
---|