LLLGCD examples

In our paper Extended gcd and Hermite normal form algorithms via lattice basis reduction, G. Havas, B.S. Majewski, K.R. Matthews, Experimental Mathematics, Vol 7 (1998) 125-136, we show that if 1 ≥ α ≥ 3/8, our LLLGCD algorithm delivers a multiplier vector b[3] for three numbers such that one of b[3]+e[1]b[1]+e[2]b[2] is a shortest multiplier, where e[i]=0,-1, or 1. A similar result also holds for four integers with 1 ≥ α > (5 + √33)/16 = ·671···, (proved by Sean Byrnes), but not for five integers - see below.
  1. gcd(4,6,9) (20th July 1997) (lllgcd step by step)
  2. gcd(113192, 763836, 1066557, 1785102) (algorithm 2 of HMM, step by step)
  3. gcd(116085838, 181081878, 314252913, 10346840) (lllgcd step by step)
  4. gcd of five numbers (14th December 1998)
  5. gcd of ten numbers (17th December 1998)
  6. gcd of twenty numbers (17th December 1998)
  7. gcd of thirty, forty, fifty, sixty integers (9th December 1998)

Last modified 28th January 2014