Abstract
We review a class of addition chains that are suboptimal but close to optimal. Addition chains in this class are generated by a very efficient algorithm. We present evidence that traditional algorithms for exponentiation may in fact be slower than a method where an addition chain is first constructed, then applied and finally discarded. Experimental evidence definitely indicates this to be true for slightly more complex domains than the integers.
To achieve such a result, we define an interpretation of addition chains as sequences of function applications using continuation passing style which can be compiled by transformation into sequences of simple “combinators”. Finally, we propose optimization techniques for addition chains in this representation.
With partial support from NSERC-Canada and FCAR-Québec, e-mail: brlek@lacim.uqam.ca
With the support of PRC “GRECO de Programmation”, e-mail: casteran@geocub.greco-prog.fr
With the support of PRC “GRECO de Programmation”, e-mail: strandh@geocub.greco-prog.fr
Chapter PDF
Similar content being viewed by others
keywords
References
F. Bergeron, J. Berstel, S. Brlek, A Unifying Approach to the Generation of Addition Chains, Proceedings of the XV Latino-American Conference on Informatics, 10–14 July (1989) 29—38.
F. Bergeron, J. Berstel, S. Brlek, Efficient Computation of Addition Chains, Submitted.
F. Bergeron, J. Berstel, S. Brlek, C. Duboc, Addition Chains using Continued Fractions, Journal of Algorithms (1988) 403–412.
D. Bjørner, A.P. Ershov, N.D. Jones (eds.) Partial Evaluation and Mixed Computation, North Holland, (1988).
F. Bergeron, J. Olivos, Vectorial Addition Chains Using Euclid's Algorithm, (1989) Submitted.
A. Brauer, On Addition Chains, Bull.Amer.Math.Soc. 45, (1939) 736–739.
S. Brlek, P. Castéran, R. Strandh, Chaînes d'additions et structures de contrôle, Journées JFLA 91, Gresse-en-Vercors, France, January 28–29, (1991).
M. Castan, M.-H. Durand, M. Lemaître, A Set of Combinators for Abstraction in Linear Space, Information Processing Letter 24, (1987) 183–188
H.B. Curry, R. Feys, Combinatory Logic, North Holland (1974).
P. Downey, B. Leong, R. Sethi, Computing Sequences with Additions Chains, SIAM J.Computing 3, (1974) 1–10.
R.K. Dybvig, The Scheme Programming Language, Prentice Hall (1987).
P. Fradet, D. Le Metayer, Compilation of Functional Languages by Program Transformation, INRIA Research, Report 1040 (1989).
D.E. Knuth, The Art of Computer Programming, vol.2, Addison Wesley (1981).
D. Kranz, R. Kelsey, J.A. Rees, P. Hudak, J. Philbin, N.I. Adams, Orbit: An Optimizing Compiler for Scheme, Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, July 1986.
A. Scholz, Jahresbericht, Deutsche Math.-Verein. 47, (1937) 41.
J.E. Stoy, The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge (1977).
G.L. Steele, G.J. Sussman, Scheme: an Interpreter for the Extended Lambdacalculus, Memo 349, MIT Artificial Intelligence Laboratory (1975).
M. Wand, Continuation-Based Program Transformation Strategies, J. of Computer Languages, (1978) 241–263.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brlek, S., Castéran, P., Strandh, R. (1991). On addition schemes. In: Abramsky, S., Maibaum, T.S.E. (eds) TAPSOFT '91. TAPSOFT 1991. Lecture Notes in Computer Science, vol 494. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3540539816_77
Download citation
DOI: https://doi.org/10.1007/3540539816_77
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53981-0
Online ISBN: 978-3-540-46499-0
eBook Packages: Springer Book Archive