Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0838.68044
Brlek, Srećko; Castéran, Pierre; Habsieger, Laurent; Mallette, Richard
On-line evaluation of powers using Euclid's algorithm. (English)
[J] RAIRO, Inform. Théor. Appl. 29, No.5, 431-450 (1995). ISSN 0988-3754

Summary: The aim of this paper is to present an efficient algorithm to compute powers of an element in a semigroup. The problem to compute $x^n$ using a minimal number of semigroup operations is equivalent to the problem of computing an optimal addition chain for $n$. The algorithm presented here is based upon a suitable continued fraction expansion for $n$ and is remarkably stable: the asymptotic length of the addition chain produced is bounded by $1,5\log_2(n)$ for the worst case, and the average length is asymptotically $\approx 1,2946\log_2(n)$.

MSC 2000:: *68W10 Parallel algorithms

Keywords: addition chain

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]