Small algorithms for small systems
James H. Davenport · ACM communications in computer algebra · 2012
Knuth is said to have described Computer Science as “that part of mathe-matics in which log log n = 3”. In this talk I will consider only some parts of Computer Algebra, and the even more special case when log n = 3, or even less, and where compactness of the algorithm itself, as well as the data structures, is important. g.c.d. This has been a bugbear of computer algebra for over forty years, and has given rise to many solutions, some of then truly heroic [CGG84, DP85]. Though difficult to prove, the subresultant algorithm [Col67] is quite short to program, and its intermediate expression swell does not manifest itself on small examples. It may well be worth considering the trial division variant of [Hea79]. Factoring (of univariate polynomials). This has been a challenge for almost as long as the g.c.d. problem, and is still far from being solved, as significant improvements keep on being made [vH02]. Nevertheless, if log n = 3, we can devise a relatively simple algorithm on the following lines.