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.
- gcd(4,6,9) (20th July 1997) (lllgcd step by step)
- gcd(113192, 763836, 1066557, 1785102) (algorithm 2 of HMM, step by step)
- gcd(116085838, 181081878, 314252913, 10346840) (lllgcd step by step)
- gcd of five numbers (14th December 1998)
- gcd of ten numbers (17th December 1998)
- gcd of twenty numbers (17th December 1998)
- gcd of thirty, forty, fifty, sixty integers (9th December 1998)
Last modified 28th January 2014