Mitchell A. Harris
Abstract
Bresenham's algorithm minimizes error in drawing lines on integer grid points; leap year calculations, surprisingly, are a generalization. We compare the two calculations, explicate the pattern, and discuss the connection of the leap year/line pattern with integer division and Euclid's algorithm for computing the greatest common divisor.
- Allouche, J.-P. and Shallit, J. 2003. Automatic Sequences. Cambridge University Press, Cambridge, U.K.Google Scholar
- Berstel, J. 1990. Tracé de droites, fractions continues et morphismes itérés. In Mots: Mélanges Offerts à M.-P. Schützenberger, M. Lothaire, Ed. Editions Hermès, Paris, France, 298--309.Google Scholar
- Bresenham, J. E. 1965. Algorithm for computer control of a digital plotter. IBM Syst. J. 4, 1, 25--30.Google Scholar
- Brons, R. 1974. Linguistic methods for the description of a straight line on a grid. Comput. Graph. Image Process. 3, 1, 48--62.Google Scholar
- Castle, C. M. A. and Pitteway, M. L. V. 1987. An efficient structural technique for encoding 'best-fit' straight lines. Comput. J. 30, 2, 168--175. Google Scholar
- Fraenkel, A. S., Mushkin, M., and Tassa, U. 1978. Determination of {n θ} by its sequence of differences. Can. Math. Bull. 21, 441--446.Google Scholar
- Graham, R. L., Knuth, D. E., and Patashnik, O. 1994. Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA. Google Scholar
- Knuth, D. E. 1998. The Art of Computer Programming (Volume 2: Seminumerical Algorithms), 3rd ed. Addison-Wesley, Reading, MA. Google Scholar
- Pitteway, M. L. V. 1985. The relationship between Euclid's algorithm and run-length encoding. In Fundamental Algorithms for Computer Graphics, R. A. Earnshaw, Ed. Springer, Berlin, Germany, 105--111.Google Scholar
- Reingold, E. M. and Dershowitz, N. 2001. Calendrical Calculations: The Millennium Edition. Cambridge University Press, Cambridge, U.K. Google Scholar
- Rockett, A. M. and Szüsz, P. 1992. Continued Fractions. World Scientific, Singapore.Google Scholar
- Shallit, J. 1994. Pierce expansions and rules for the determination of leap years. Fibonacci Quart. 32, 5, 416--423.Google Scholar
- Sproull, R. F. 1982. Using program transformations to derive line-drawing algorithms. ACM Trans. Graph. 1, 4, 259--273. Google Scholar
- Troesch, A. 1998. Droites discrètes et calendriers. Math. Inform. et Sci. Humaines 141, 36, 11--41.Google Scholar
Index Terms
- Line drawing, leap years, and Euclid
Recommendations
On Euclid's algorithm and elementary number theory
Algorithms can be used to prove and to discover new theorems. This paper shows how algorithmic skills in general, and the notion of invariance in particular, can be used to derive many results from Euclid's algorithm. We illustrate how to use the ...
Identities and inequalities derived from Euclid's algorithm with applications in cutting-covering receipts
MAMECTIS'10: Proceedings of the 12th WSEAS international conference on Mathematical methods, computational techniques and intelligent systemsStarting from the original demonstration of the Euclid's Algorithm (Elements, Book VII,2) we deduce one using rectangles. From this proof we deduce after some calculus some identities and inequalities that we use in Cutting-Covering Receipts. Giving two ...
Total Positivity from the Exponential Riordan Arrays
Log-concavity and almost log-convexity of the cycle index polynomials were proved by Bender and Canfield [J. Combin. Theory Ser. A, 74 (1996), pp. 57--70]. Schirmacher [J. Combin. Theory Ser. A, 85 (1999), pp. 127--134] extended them to $q$-log-concavity ...
Comments