Minimizing sums of addition chains

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)
    4 Downloads (Pure)


    The length of an addition chain for n measures the number of multiplications for computing xn from x. If the cost of the multiplications is taken into account, then the sum of the elements of an addition chain for n is a better measure for the cost of computing xn than the length. In this paper bounds on sums of addition chains are derived, and properties of optimal addition chains according to the sum cost criterion are studied. It turns out that the last step in an optimal addition chain for an even number is always a doubling, and the sum of an optimal addition chain for an odd number n is asymptotically very close to 5n/2.
    Original languageEnglish
    Pages (from-to)281-307
    Number of pages27
    JournalJournal of Algorithms
    Issue number2
    Publication statusPublished - 1991

    Fingerprint Dive into the research topics of 'Minimizing sums of addition chains'. Together they form a unique fingerprint.

    Cite this