Sparse polynomials and linear logic

Publisher Website
Google Scholar
Abstract
The Gabriel FRPOLY benchmark was rewritten in a "linear" fragment of Common Lisp and is competitive with the standard FRPOLY benchmark code. This linear FRPOLY is considerably more perspicuous than the standard code, while its running time is only 6% longer than that of the standard FRPOLY code. Linear FRPOLY recovers all of its garbage, and its "high water mark" space requirement is very probably smaller than that of the standard code. In the expansion of (x+y+z+1) 15 , the standard FRPOLY does 48,892 new conses, while the linear FRPOLY does only 4821 new conses---i.e., it does only about 10% of the consing of the standard FRPOLY code.We also tested versions of FRPOLY in which squarings were not used for exponentiation. This non-linear FRPOLY does 38,780 conses, and takes only 59% of the time of the non-linear squaring FRPOLY. The linear non-squaring FRPOLY takes only 62% of the time of the linear squaring FRPOLY, and cuts the new consing to 3988 cells. A slightly slower version cuts the new consing to 2590 cells---only 567 cells (28%) more than are used in the result.

This publication has 10 references indexed in Scilit: