Binary Iterated Powers

by Stanislav Sýkora, Extra Byte, Via R.Sanzio 22C, Castano Primo, Italy 20022
in Stan's Library, Ed.S.Sykora, Vol.I. Completed June 2004, first public release March 15, 2006.
Permalink via DOI:  10.3247/SL1Math06.001
Other math articles in Stan's Library | SCIENCE Links Stan's Courses | Stan's HUB

Abstract

Binary iterated powers (bips) are defined as functions of the type

f(x) = β^(e0β^(e1β^(e2β^(...β^(enx)...)))) ≡ {b0b1b2...bn|x} ≡ {b|x},
where β is a non-negative base, ek = 2bk-1, and b = {b0,b1,b2,... ,bn} 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 non-negative real numbers.

Among potential applications of bips is a qualitatively novel real numbers representation which is also briefly discussed.

MSC-2000 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 non-commercial 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 iterated-powers (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 {10110|x}.

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 non-negative 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 above-mentioned 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 C0 of values of the base β, the bips {Sn(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:RB* is explicitly defined.

While establishing these results, we have derived a number of explicit identities and inequalities for finite bips, exploiting an ad-hoc notation which simplifies their mathematical treatment. Incidentally, we have also seen that the bips and their derivatives are computationally easily manageable.

The BK-bijection 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 universal-convergence domain C0 . There are also categories of related functions which appear to merit further inquiry.

Some of the considerations on the use of the BK-bijection to represent real numbers might eventually lead to establishing a general real-numbers 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 L-progeny sequence (II.5) of x. The L-progeny 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 single-precision and double-precision values of Ln(2), the mismatch is total after about 30 steps. Even using the same double-precision IEEE-754 format but slightly different algorithms (such as the hard-wired 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 L-progeny 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 L-progeny 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, 235-252 (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, 297-305 (1989).
  • Borwein J.M., Corless R.M., Emerging tools for experimental mathematics,
    Amer.Math.Monthly 106, 889-909 (1999).
  • Goebel F., Nederpelt R.P., The number of numerical outcomes of iterated powers,
    Amer.Math.Monthly 78, 1097-1103 (1971).
  • IEEE Standards Committee, 754: IEEE Standard for Binary Floating-Point Arithmetic,
    ANSI/IEEE Standard 754-1985. 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, 5-48 (1991).
  • Muller J.M., Scherbyna A., Tisserand A., Semi-Logarithmic Number Systems,
    IEEE Trans. on Computers, (1998).
  • Clenshaw C.W., Olver F.W.J., Beyond floating point,
    J.Assoc.Comput.Mach. 31, 319-328 (1984).
  • Clenshaw C.W., Turner P.R., The symmetric level-index system,
    IMA J.Numer.Anal. 8, 517-526 (1988).
  • Boehm H.J., Cartwright R., Exact real arithmetic: Formulating real numbers as functions,
    in Research Topics in Functional Programming, Turner D., Editor,
    Addison-Wesley (1990).
  • Vuillemin J., Exact real computer arithmetic with continued fractions,
    IEEE Trans. on Computers 39, 1087-1105 (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, 74-79 (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

TOP | Other math articles in Stan's Library | SCIENCE Links Stan's Courses | Stan's HUB | TOP 
   
Copyright ©2006 Stanislav Sykora    DOI: 10.3247/SL1Math06.001 Designed by Stan Sýkora