Abstract
The interval data type is currently not supported in common programming languages. Therefore the implementation of algorithms using interval arithmetic requires special programming environments or at least special libraries. In this paper we present the C++ class library PROFIL which provides a user friendly environment for implementing interval algorithms. The main goals in the design of PROFIL were speed and portability. Therefore all interval operations in PROFIL use BIAS (Basic Interval Arithmetic Subroutines) [16]. BIAS defines a concise and portable interface for the basic scalar, vector, and matrix operations. The interface is independent of a specific interval representation or computation but permits machine specific and fast implementations. Based on this general specification we present an implementation in C using a lower/upper bound representation of intervals and directed roundings. By using few assembler instructions for switching the rounding modes and avoiding sign tests and rounding mode switches wherever possible, the computational costs of the interval operations were reduced significantly. This is especially important for RISC machines, where floating point instructions can be executed in few machine cycles. Comparisons with other interval arithmetic packages show an improvement in speed of about one order of magnitude.
Zusammenfassung
In den weit verbreiteten Programmiersprachen wird der Intervalldatentyp nicht unterstützt. Daher benötigt man für die Implementierung von Algorithmen, die auf Intervallarithmetik basieren, spezielle Programmierumgebungen oder zumindest spezielle Programmbibliotheken. In diesem Artikel stellen wir die C++-Klassenbibliothek PROFIL vor, die eine anwenderfreundliche Umgebung für die Implementierung von Intervallalgorithmen darstellt. Die Entwicklung von PROFIL wurde von den beiden Hauptzielen Geschwindigkeit und Portabilität geleitet. Daher basieren alle Intervalloperationen von PROFIL auf BIAS (Basic Interval Arithmetic Subroutines). BIAS definiert eine einheitliche und portable Schnittstelle für die grundlegenden Intervalloperationen von skalaren bis hin zu Matrixoperationen. Dabei ist die Schnittstelle unabhängig von einer speziellen Intervalldarstellung oder von speziellen Berechnungsmodi, erlaubt aber dennoch maschinenspezifische und schnelle Implementierungen. Basierend auf dieser allgemeinen Spezifikation stellen wir eine Implementierung in C vor, die eine Intervalldarstellung in der Form untere/obere Grenze sowie gerichtete Rundungen verwendet. Durch Verwendung eigener Assemblerroutinen (insgesamt nur ca. 10 Assemblerinstruktionen) zur Umschaltung der Rundung sowie durch weitestgehende Vermeidung überflüssiger Vorzeichentests und Rundungsumschaltungen wird der Aufwand für die Intervalloperationen drastisch reduziert. Dies ist insbesondere für RISC-Architekturen wichtig, auf denen Gleitkommaoperationen in wenigen Maschinentaktzyklen ausgeführt werden können. Vergleiche mit anderen Intervallpaketen zeigen eine Geschwindigkeitssteigerung um etwa eine Größenordnung.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alefeld, G., Herzberger, J.: Introduction to interval computations. New York: Academic Press 1983.
Corliss, G. F.: Comparing software packages for interval arithmetic. Preprint presented at SCAN '93, Vienna, 1993.
Daumas, M., Matula, D. W.: Rounding of floating point intervals (to appear).
Dongarra, J., Du Croz, J., Duff, I., Hammarling, S.: A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Softw.16, 1–17 (1990).
Dongarra, J., Du Croz, J., Hammarling, S., Hanson, R.: An extended set of Fortran basic linear algebra subroutines. ACM Trans. Math. Softw.14, 1–17 (1988).
Dongarra, J. J., Mayers, P., Radicati di Brozolo, G.: The IBM RISC System/6000 and linear algebra operations. Science Tech Report CS-90-122, University of Tennessee, 1991.
Hansen, G.: Global optimization interval analysis. New York Basel Hongkong: Marcel Dekker 1992.
Herzberger, J.: Topics validated computations. Studies in Computational Mathematics (to appear).
IEEE Standard for binary floating-point arithmetic, 1985. ANSI/IEEE Standard 754.
Jansson, C.: A global optimization method using interval arithmetic. In: Computer arithmetic and enclosure methods, pp. 259–268. Amsterdam: Elsevier 1992.
Jansson, C., Knüppel, O.: A global minimization method: The multi-dimensional case. Bericht 92.1, TU Hamburg-Harburg, Technische Informatik III, Jan. 1992.
Jansson, C., Knüppel, O.: Eine intervallanalytische Methode für globale Optimierungsprobleme. Z. Ang. Math. Mech.73, T741-T743 (1993).
Kearfott, R. B., Dawande, M., Du, K., Hu, C.: INTLIB: A portable Fortran-77 interval standard function library (to appear) in ACM Trans. Math. Software, 1994).
Kearfott, R. B., Novoa, M.: INTBIS, a portable interval newton/bisection package. ACM Trans. Math. Software16, 152–157 (1990).
Klatte, R., Kulisch, U., Neaga, M., Ratz, D., Ullrich, C.: Pascal-XSC: Languare reference with examples. Berlin Heidelberg New York Tokyo: Springer 1992.
Knüppel, O.: BIAS—Basic interval arithmetic subroutines. Bericht 93.3 des Forschungsschwerpunktes Informations- und Kommunikationstechnik der TU Hamburg-Harburg, TU Hamburg-Harburg, Technische Informatik III, July 1993.
Knüppel, O.: PROFIL—Programmer's runtime optimized fast interval library. Bericht 93.4 des Forschungsschwerpunktes Informations- und Kommunikationstechnik der TU Hamburg-Harburg, TU Hamburg-Harburg, Technische Informatik III, July 1993.
Knüppel, O., Simenec, T.: PROFIL/BIAS extensions. Bericht 93.5 des Forschungsschwerpunktes Informations- und Kommunikationstechnik der TU Hamburg-Harburg, TU Hamburg-Harburg, Technische Informatik III, Nov. 1993.
Lawo, C.: C-XSC, a programming environment for verifield scientific computing and numerical data processing. In: Adams, E., Kulisch, U. (eds.) Scientific computing with automatic result verification, pp. 71–86. Orlando: Academic Press 1992.
Lawson, C., Hanson, R., Kincaid, D., Krogh, F.: Basic linear algebra subprograms for Fortran usage. ACM Trans. Math. Software5, 308–323 (1979).
Moore, R. E.: Methods and applications of interval analysis. Philadelphia: SIAM 1979.
Rump, S. M.: Solving algebraic problems with high accuracy. In: Kulisch, U., Miranker, W. (eds.): A new approach to scientific computation, pp. 51–120. New York: Academic Press 1983.
Schulze, J.: Die schwache Rundung und ihr Rundungsfehlerverhalten (to appear).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Knüppel, O. PROFIL/BIAS—A fast interval library. Computing 53, 277–287 (1994). https://doi.org/10.1007/BF02307379
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02307379