Abstract
Binary iterated powers (bips) are defined as functions of the type
f(x) = β^(e_{0}β^(e_{1}β^(e_{2}β^(...β^(e_{n}x)...)))) ≡ {b_{0}b_{1}b_{2}...b_{n}x} ≡ {bx},
where β is a nonnegative base, e_{k} = 2b_{k}1, and b = {b_{0},b_{1},b_{2},... ,b_{n}} is a binary sequence of 0's and 1's.
This paper explores the properties of both finite and infinite binary iterated powers in the real domain. In particular, it analyses the convergence behavior of infinite bips and shows that, for a range of bases and any infinite binary sequence b, they converge to a real value which depends upon b but not upon the starting value of x. This establishes an interesting bijection between a subset of infinite bips and the set of nonnegative real numbers.
Among potential applications of bips is a qualitatively novel real numbers representation which is also briefly discussed.
MSC2000 keys: 08A70, 26A12, 26A18, 26A99, 26D07, 33E99, 33F99, 40A30, 58K05, 58K20, 68M07
Editor's Note: The original paper has been completed in June 2004 but made public only now. This HTML document includes only the following parts: Abstract, Introduction, Conclusions and References. You may download the complete PDF version and use it in whatever noncommercial way, as long as you maintain its integrity. You can also download the Matlab programs used to produce the article Figures. To cite this article, use the form: Sykora S., Binary Iterated Powers, Stan's Library, Volume I, 2006, www.ebyte.it/library.

 Introduction_{ }
The following Sections are not available in HTML format; please, see the complete PDF document.
 Definitions and notation
 Some properties of finite bips and of their derivatives
 The convergence theorem
 The BK bijection and its properties
 Representation of real numbers by means of bips
 Conclusions
 References and links

Introduction
Given a positive real number b and a real number x, one can form expressions such as
(I.1) β^+β^β^+β^+β^x ≡ β^(+β^(β^(+β^(+β^(x)))),
where ^ stands for the power operator (β^x ≡ β^{x }) and, as indicated, the order of evaluation is from right to left.
Expressions of this kind shall be called binary iteratedpowers (or bips) in base β. The distribution of the "+" and "" signs within a bip can be encoded by means of binary sequences having "0" and "1" as their elements. If we let "1" correspond to the "+" sign and "0" to the "" sign, the above example can be associated with the binary sequence b ≡ {10110} and the value of the expression, intended as a function of x, can be written as {10110x}.
In this paper we investigate the behavior of bips and show that when e^{1} < abs(ln(β)) ≤ e and the length of the binary sequence extends to infinity, then every infinite bip converges to a value which is independent of x. This, among other things, leads to a mapping of the set B of infinite binary sequences into the set R of nonnegative real numbers, extended by the addition of infinity element. We also show that for a subset B* of B, this mapping is a bijection and thus gives rise to a representation of real numbers by infinite bips, encoded by the corresponding binary sequences.
There is a relationship between bips and the functions known as iterated exponentials or hyperpowers [1], [2], which can be viewed as very special cases of bips. It turns out, however, that the abovementioned bijection holds only for β values for which the hyperpowers do not converge to a finite limit. In order to underline this diversity and avoid misunderstandings, we will use preferentially the short term bip rather than the expanded form binary iterated power.
... Intermediate Sections: please, view the complete PDF document ...
Conclusions
We have proved that, within a range C_{0} of values of the base β, the bips {S_{n}(b)x} converge for every infinite binary sequence b to a limit which depends only on the sequence b and not on the value of its starting argument x. Moreover, for a subset B* of infinite binary sequences, the resulting mapping K:B*→R turns out to be a bijection whose inverse B:R→B* is explicitly defined.
While establishing these results, we have derived a number of explicit identities and inequalities for finite bips, exploiting an adhoc notation which simplifies their mathematical treatment. Incidentally, we have also seen that the bips and their derivatives are computationally easily manageable.
The BKbijection has a number of interesting properties, some of which have been analyzed. As usual, the topic opens many more problems than those which it settles. This regards, in particular, the behavior of the K mapping for various binary sequences b and for base values which lie outside the universalconvergence domain C_{0} . There are also categories of related functions which appear to merit further inquiry.
Some of the considerations on the use of the BKbijection to represent real numbers might eventually lead to establishing a general realnumbers representation theory. This topic shall be tackled in more detail in a forthcoming paper.
This study actually started from the observation that it is impossible to reliably compute the result of iterated applications of the function abs(ln(x)) when the number of required iterations exceeds a certain limit. Computing the iterated values amounts to estimating the Lprogeny sequence (II.5) of x. The Lprogeny sequences which one obtains in practice when using various floating point (FP) implementations start grossly mismatching each other after a relatively modest number of steps. Thus, for example, comparing standard singleprecision and doubleprecision values of L^{n}(2), the mismatch is total after about 30 steps. Even using the same doubleprecision IEEE754 format but slightly different algorithms (such as the hardwired Intel FP processor versus an FP emulator), the mismatch becomes total after about 62 steps.
The logic behind this behavior is now quite clear. Since the Lprogeny sequence defines the binary sequence B(x), pretending correct results for an ever increasing number of steps amounts to determining the value of x with a precision which would eventually exceed the precision we have started with. This being impossible, the Lprogeny sequence members xn and the elements of B(x) must at some point become meaningless. Due to the fact that the convergence rate of BIPR is only slightly inferior to that of BPSR, this happens after a number of steps comparable to the number of BPSR bits used to represent the number.

References
 Knoebel R.A.,
Exponential reiterated,
Amer.Math.Monthly 88, 235252 (1981).
The hyperpower functions have been discussed already by Bernoulli and Goldbach, followed by Cantor, Cayley, Euler, Carmichael, Knuth and many others. The treatise of Knoebel contains 125 references!
 MacDonnell J.F.,
Some Critical Points of the Hyperpower Function x^x^x,
International Journal of Mathematical Education in Science and Technology 20, 297305 (1989).
 Borwein J.M., Corless R.M.,
Emerging tools for experimental mathematics,
Amer.Math.Monthly 106, 889909 (1999).
 Goebel F., Nederpelt R.P.,
The number of numerical outcomes of iterated powers,
Amer.Math.Monthly 78, 10971103 (1971).
 IEEE Standards Committee,
754: IEEE Standard for Binary FloatingPoint Arithmetic,
ANSI/IEEE Standard 7541985. Institute of Electrical and Electronics Engineers, New York, 1985.
 Goldberg D.,
What Every Computer Scientist Should Know About Floating Point Arithmetic,
ACM Computing Surveys 23, 548 (1991).
 Muller J.M., Scherbyna A., Tisserand A.,
SemiLogarithmic Number Systems,
IEEE Trans. on Computers, (1998).
 Clenshaw C.W., Olver F.W.J.,
Beyond floating point,
J.Assoc.Comput.Mach. 31, 319328 (1984).
 Clenshaw C.W., Turner P.R.,
The symmetric levelindex system,
IMA J.Numer.Anal. 8, 517526 (1988).
 Boehm H.J., Cartwright R.,
Exact real arithmetic: Formulating real numbers as functions,
in Research Topics in Functional Programming, Turner D., Editor,
AddisonWesley (1990).
 Vuillemin J.,
Exact real computer arithmetic with continued fractions,
IEEE Trans. on Computers 39, 10871105 (1990).
 Edalat A., Potts P.J.,
A New Representation for Exact Real Numbers,
E.N.T.C.S., Vol.6, Elsevier Science B.V., 1997.
 Potts P.J., A.Edalat A.,
Exact Real Computer Arithmetic, Departmental Technical Report DOC 97/9,
Imperial College, 180 Queen's Gate, London SW7 2BZ, United Kingdom, 1997.
 Crandall R.E.,
The challenge of large numbers,
Scientific American 276, 7479 (1997).
 Davis P.J.,
The Lore of Large Numbers, in New Mathematical Library,
The Mathematical Association of America, 1961.
 Wan Y., Wey C.L.,
Efficient algorithms for binary logarithmic conversion and addition,
IEEE Trans. on Computers and Digital Techniques, p.168, May 1999.
Web links

