Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Automated Reasoning for Knot Semigroups and -orbifold Groups of Knots Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Balancing Expression Dags for More Efficient Lazy Adaptive Evaluation

Author : Martin Wilhelm

Published in: Mathematical Aspects of Computer and Information Sciences

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Arithmetic expression dags are widely applied in robust geometric computing. In this paper we restructure expression dags by balancing consecutive additions or multiplications. We predict an asymptotic improvement in running time and experimentally confirm the theoretical results. Finally, we discuss some pitfalls of the approach resulting from changes in evaluation order.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Automated Reasoning for Knot Semigroups and -orbifold Groups of Knots
next chapter Certification Using Newton-Invariant Subspaces
Footnotes
1
This should more correctly be called “accuracy-driven”, but we use the term “precision-driven” throughout this paper for historical reasons.
 
2
Real_algebraic usually overestimates the exponent by one, therefore in our tests r is chosen to be smaller than 0.5.
 
3
This is implemented by inserting dummy nodes up to the next power of two.
 
4
Or integers divided by a power of two.
 
5
This behavior was confirmed with both mpfr and leda bigfloats.
 
Literature
1.
Benouamer, M.O., Jaillon, P., Michelucci, D., Moreau, J.: A lazy exact arithmetic. In: Proceedings of the 11th Symposium on Computer Arithmetic, pp. 242–249 (1993)
2.
Burnikel, C., Mehlhorn, K., Schirra, S.: The leda class real number (1996)
3.
Dubé, T., Yap, C.: A basis for implementing exact geometric algorithms (extended abstract) (1993)
4.
Fortune, S., van Wyk, C.J.: Efficient exact arithmetic for computational geometry. In: Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 163–172 (1993)
5.
Karamcheti, V., Li, C., Pechtchanski, I., Yap, C.: A core library for robust numeric and geometric computation. In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry, SoCG, pp. 351–359 (1999)
6.
Mörig, M., Rössling, I., Schirra, S.: On design and implementation of a generic number type for real algebraic number computations based on expression dags. Math. Comput. Sci. 4(4), 539–556 (2010)MathSciNetCrossRefMATH
7.
8.
Pion, S., Fabri, A.: A generic lazy evaluation scheme for exact geometric computations. Sci. Comput. Program. 76(4), 307–323 (2011)CrossRef
9.
Schirra, S.: Robustness and precision issues in geometric computation. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 597–632. Elsevier, Amsterdam (2000)CrossRef
10.
11.
Metadata
Title
Balancing Expression Dags for More Efficient Lazy Adaptive Evaluation
Author
Martin Wilhelm
Copyright Year
2017
Book
Mathematical Aspects of Computer and Information Sciences

Print ISBN: 978-3-319-72452-2

Electronic ISBN: 978-3-319-72453-9

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-72453-9_2

Premium Partner

    Image Credits