Hex Artifact Content
Not logged in

Artifact 2fd0ac98d3a9329ac4b0eee8e17706c673b728c6:


0000: 2f 2a 20 6d 70 7a 5f 6c 63 6d 20 2d 2d 20 6d 70  /* mpz_lcm -- mp
0010: 7a 2f 6d 70 7a 20 6c 65 61 73 74 20 63 6f 6d 6d  z/mpz least comm
0020: 6f 6e 20 6d 75 6c 74 69 70 6c 65 2e 0a 0a 43 6f  on multiple...Co
0030: 70 79 72 69 67 68 74 20 31 39 39 36 2c 20 32 30  pyright 1996, 20
0040: 30 30 2c 20 32 30 30 31 20 46 72 65 65 20 53 6f  00, 2001 Free So
0050: 66 74 77 61 72 65 20 46 6f 75 6e 64 61 74 69 6f  ftware Foundatio
0060: 6e 2c 20 49 6e 63 2e 0a 0a 54 68 69 73 20 66 69  n, Inc...This fi
0070: 6c 65 20 69 73 20 70 61 72 74 20 6f 66 20 74 68  le is part of th
0080: 65 20 47 4e 55 20 4d 50 20 4c 69 62 72 61 72 79  e GNU MP Library
0090: 2e 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 4c 69  ...The GNU MP Li
00a0: 62 72 61 72 79 20 69 73 20 66 72 65 65 20 73 6f  brary is free so
00b0: 66 74 77 61 72 65 3b 20 79 6f 75 20 63 61 6e 20  ftware; you can 
00c0: 72 65 64 69 73 74 72 69 62 75 74 65 20 69 74 20  redistribute it 
00d0: 61 6e 64 2f 6f 72 20 6d 6f 64 69 66 79 0a 69 74  and/or modify.it
00e0: 20 75 6e 64 65 72 20 74 68 65 20 74 65 72 6d 73   under the terms
00f0: 20 6f 66 20 74 68 65 20 47 4e 55 20 4c 65 73 73   of the GNU Less
0100: 65 72 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69  er General Publi
0110: 63 20 4c 69 63 65 6e 73 65 20 61 73 20 70 75 62  c License as pub
0120: 6c 69 73 68 65 64 20 62 79 0a 74 68 65 20 46 72  lished by.the Fr
0130: 65 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e  ee Software Foun
0140: 64 61 74 69 6f 6e 3b 20 65 69 74 68 65 72 20 76  dation; either v
0150: 65 72 73 69 6f 6e 20 32 2e 31 20 6f 66 20 74 68  ersion 2.1 of th
0160: 65 20 4c 69 63 65 6e 73 65 2c 20 6f 72 20 28 61  e License, or (a
0170: 74 20 79 6f 75 72 0a 6f 70 74 69 6f 6e 29 20 61  t your.option) a
0180: 6e 79 20 6c 61 74 65 72 20 76 65 72 73 69 6f 6e  ny later version
0190: 2e 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 4c 69  ...The GNU MP Li
01a0: 62 72 61 72 79 20 69 73 20 64 69 73 74 72 69 62  brary is distrib
01b0: 75 74 65 64 20 69 6e 20 74 68 65 20 68 6f 70 65  uted in the hope
01c0: 20 74 68 61 74 20 69 74 20 77 69 6c 6c 20 62 65   that it will be
01d0: 20 75 73 65 66 75 6c 2c 20 62 75 74 0a 57 49 54   useful, but.WIT
01e0: 48 4f 55 54 20 41 4e 59 20 57 41 52 52 41 4e 54  HOUT ANY WARRANT
01f0: 59 3b 20 77 69 74 68 6f 75 74 20 65 76 65 6e 20  Y; without even 
0200: 74 68 65 20 69 6d 70 6c 69 65 64 20 77 61 72 72  the implied warr
0210: 61 6e 74 79 20 6f 66 20 4d 45 52 43 48 41 4e 54  anty of MERCHANT
0220: 41 42 49 4c 49 54 59 0a 6f 72 20 46 49 54 4e 45  ABILITY.or FITNE
0230: 53 53 20 46 4f 52 20 41 20 50 41 52 54 49 43 55  SS FOR A PARTICU
0240: 4c 41 52 20 50 55 52 50 4f 53 45 2e 20 20 53 65  LAR PURPOSE.  Se
0250: 65 20 74 68 65 20 47 4e 55 20 4c 65 73 73 65 72  e the GNU Lesser
0260: 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 0a   General Public.
0270: 4c 69 63 65 6e 73 65 20 66 6f 72 20 6d 6f 72 65  License for more
0280: 20 64 65 74 61 69 6c 73 2e 0a 0a 59 6f 75 20 73   details...You s
0290: 68 6f 75 6c 64 20 68 61 76 65 20 72 65 63 65 69  hould have recei
02a0: 76 65 64 20 61 20 63 6f 70 79 20 6f 66 20 74 68  ved a copy of th
02b0: 65 20 47 4e 55 20 4c 65 73 73 65 72 20 47 65 6e  e GNU Lesser Gen
02c0: 65 72 61 6c 20 50 75 62 6c 69 63 20 4c 69 63 65  eral Public Lice
02d0: 6e 73 65 0a 61 6c 6f 6e 67 20 77 69 74 68 20 74  nse.along with t
02e0: 68 65 20 47 4e 55 20 4d 50 20 4c 69 62 72 61 72  he GNU MP Librar
02f0: 79 3b 20 73 65 65 20 74 68 65 20 66 69 6c 65 20  y; see the file 
0300: 43 4f 50 59 49 4e 47 2e 4c 49 42 2e 20 20 49 66  COPYING.LIB.  If
0310: 20 6e 6f 74 2c 20 77 72 69 74 65 20 74 6f 0a 74   not, write to.t
0320: 68 65 20 46 72 65 65 20 53 6f 66 74 77 61 72 65  he Free Software
0330: 20 46 6f 75 6e 64 61 74 69 6f 6e 2c 20 49 6e 63   Foundation, Inc
0340: 2e 2c 20 35 39 20 54 65 6d 70 6c 65 20 50 6c 61  ., 59 Temple Pla
0350: 63 65 20 2d 20 53 75 69 74 65 20 33 33 30 2c 20  ce - Suite 330, 
0360: 42 6f 73 74 6f 6e 2c 0a 4d 41 20 30 32 31 31 31  Boston,.MA 02111
0370: 2d 31 33 30 37 2c 20 55 53 41 2e 20 2a 2f 0a 0a  -1307, USA. */..
0380: 23 69 6e 63 6c 75 64 65 20 22 67 6d 70 2e 68 22  #include "gmp.h"
0390: 0a 23 69 6e 63 6c 75 64 65 20 22 67 6d 70 2d 69  .#include "gmp-i
03a0: 6d 70 6c 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20  mpl.h".#include 
03b0: 22 6c 6f 6e 67 6c 6f 6e 67 2e 68 22 0a 0a 0a 76  "longlong.h"...v
03c0: 6f 69 64 0a 6d 70 7a 5f 6c 63 6d 20 28 6d 70 7a  oid.mpz_lcm (mpz
03d0: 5f 70 74 72 20 72 2c 20 6d 70 7a 5f 73 72 63 70  _ptr r, mpz_srcp
03e0: 74 72 20 75 2c 20 6d 70 7a 5f 73 72 63 70 74 72  tr u, mpz_srcptr
03f0: 20 76 29 0a 7b 0a 20 20 6d 70 7a 5f 74 20 67 3b   v).{.  mpz_t g;
0400: 0a 20 20 6d 70 5f 73 69 7a 65 5f 74 20 75 73 69  .  mp_size_t usi
0410: 7a 65 2c 20 76 73 69 7a 65 2c 20 73 69 7a 65 3b  ze, vsize, size;
0420: 0a 20 20 54 4d 50 5f 44 45 43 4c 20 28 6d 61 72  .  TMP_DECL (mar
0430: 6b 65 72 29 3b 0a 0a 20 20 75 73 69 7a 65 20 3d  ker);..  usize =
0440: 20 53 49 5a 20 28 75 29 3b 0a 20 20 76 73 69 7a   SIZ (u);.  vsiz
0450: 65 20 3d 20 53 49 5a 20 28 76 29 3b 0a 20 20 69  e = SIZ (v);.  i
0460: 66 20 28 75 73 69 7a 65 20 3d 3d 20 30 20 7c 7c  f (usize == 0 ||
0470: 20 76 73 69 7a 65 20 3d 3d 20 30 29 0a 20 20 20   vsize == 0).   
0480: 20 7b 0a 20 20 20 20 20 20 53 49 5a 20 28 72 29   {.      SIZ (r)
0490: 20 3d 20 30 3b 0a 20 20 20 20 20 20 72 65 74 75   = 0;.      retu
04a0: 72 6e 3b 0a 20 20 20 20 7d 0a 20 20 75 73 69 7a  rn;.    }.  usiz
04b0: 65 20 3d 20 41 42 53 20 28 75 73 69 7a 65 29 3b  e = ABS (usize);
04c0: 0a 20 20 76 73 69 7a 65 20 3d 20 41 42 53 20 28  .  vsize = ABS (
04d0: 76 73 69 7a 65 29 3b 0a 0a 20 20 69 66 20 28 76  vsize);..  if (v
04e0: 73 69 7a 65 20 3d 3d 20 31 29 0a 20 20 20 20 7b  size == 1).    {
04f0: 0a 20 20 20 20 20 20 6d 70 5f 6c 69 6d 62 5f 74  .      mp_limb_t
0500: 20 20 76 6c 2c 20 67 6c 2c 20 63 3b 0a 20 20 20    vl, gl, c;.   
0510: 20 20 20 6d 70 5f 73 72 63 70 74 72 20 20 75 70     mp_srcptr  up
0520: 3b 0a 20 20 20 20 20 20 6d 70 5f 70 74 72 20 20  ;.      mp_ptr  
0530: 20 20 20 72 70 3b 0a 0a 20 20 20 20 6f 6e 65 3a     rp;..    one:
0540: 0a 20 20 20 20 20 20 4d 50 5a 5f 52 45 41 4c 4c  .      MPZ_REALL
0550: 4f 43 20 28 72 2c 20 75 73 69 7a 65 2b 31 29 3b  OC (r, usize+1);
0560: 0a 0a 20 20 20 20 20 20 75 70 20 3d 20 50 54 52  ..      up = PTR
0570: 28 75 29 3b 0a 20 20 20 20 20 20 76 6c 20 3d 20  (u);.      vl = 
0580: 50 54 52 28 76 29 5b 30 5d 3b 0a 20 20 20 20 20  PTR(v)[0];.     
0590: 20 67 6c 20 3d 20 6d 70 6e 5f 67 63 64 5f 31 20   gl = mpn_gcd_1 
05a0: 28 75 70 2c 20 75 73 69 7a 65 2c 20 76 6c 29 3b  (up, usize, vl);
05b0: 0a 20 20 20 20 20 20 76 6c 20 2f 3d 20 67 6c 3b  .      vl /= gl;
05c0: 0a 0a 20 20 20 20 20 20 72 70 20 3d 20 50 54 52  ..      rp = PTR
05d0: 28 72 29 3b 0a 20 20 20 20 20 20 63 20 3d 20 6d  (r);.      c = m
05e0: 70 6e 5f 6d 75 6c 5f 31 20 28 72 70 2c 20 75 70  pn_mul_1 (rp, up
05f0: 2c 20 75 73 69 7a 65 2c 20 76 6c 29 3b 0a 20 20  , usize, vl);.  
0600: 20 20 20 20 72 70 5b 75 73 69 7a 65 5d 20 3d 20      rp[usize] = 
0610: 63 3b 0a 20 20 20 20 20 20 75 73 69 7a 65 20 2b  c;.      usize +
0620: 3d 20 28 63 20 21 3d 20 30 29 3b 0a 20 20 20 20  = (c != 0);.    
0630: 20 20 53 49 5a 28 72 29 20 3d 20 75 73 69 7a 65    SIZ(r) = usize
0640: 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 3b 0a  ;.      return;.
0650: 20 20 20 20 7d 0a 0a 20 20 69 66 20 28 75 73 69      }..  if (usi
0660: 7a 65 20 3d 3d 20 31 29 0a 20 20 20 20 7b 0a 20  ze == 1).    {. 
0670: 20 20 20 20 20 75 73 69 7a 65 20 3d 20 76 73 69       usize = vsi
0680: 7a 65 3b 0a 20 20 20 20 20 20 4d 50 5a 5f 53 52  ze;.      MPZ_SR
0690: 43 50 54 52 5f 53 57 41 50 20 28 75 2c 20 76 29  CPTR_SWAP (u, v)
06a0: 3b 0a 20 20 20 20 20 20 67 6f 74 6f 20 6f 6e 65  ;.      goto one
06b0: 3b 0a 20 20 20 20 7d 0a 0a 20 20 54 4d 50 5f 4d  ;.    }..  TMP_M
06c0: 41 52 4b 20 28 6d 61 72 6b 65 72 29 3b 0a 20 20  ARK (marker);.  
06d0: 73 69 7a 65 20 3d 20 4d 41 58 20 28 75 73 69 7a  size = MAX (usiz
06e0: 65 2c 20 76 73 69 7a 65 29 3b 0a 20 20 4d 50 5a  e, vsize);.  MPZ
06f0: 5f 54 4d 50 5f 49 4e 49 54 20 28 67 2c 20 73 69  _TMP_INIT (g, si
0700: 7a 65 29 3b 0a 0a 20 20 6d 70 7a 5f 67 63 64 20  ze);..  mpz_gcd 
0710: 28 67 2c 20 75 2c 20 76 29 3b 0a 20 20 6d 70 7a  (g, u, v);.  mpz
0720: 5f 64 69 76 65 78 61 63 74 20 28 67 2c 20 75 2c  _divexact (g, u,
0730: 20 67 29 3b 0a 20 20 6d 70 7a 5f 6d 75 6c 20 28   g);.  mpz_mul (
0740: 72 2c 20 67 2c 20 76 29 3b 0a 0a 20 20 53 49 5a  r, g, v);..  SIZ
0750: 20 28 72 29 20 3d 20 41 42 53 20 28 53 49 5a 20   (r) = ABS (SIZ 
0760: 28 72 29 29 3b 09 2f 2a 20 72 65 73 75 6c 74 20  (r));./* result 
0770: 61 6c 77 61 79 73 20 70 6f 73 69 74 69 76 65 20  always positive 
0780: 2a 2f 0a 0a 20 20 54 4d 50 5f 46 52 45 45 20 28  */..  TMP_FREE (
0790: 6d 61 72 6b 65 72 29 3b 0a 7d 0a                 marker);.}.