Interpreters & VMs
Language interpreters, virtual machines, and runtime systems
Repositories
(2)Papers
(13)Accurate Sum and Dot Product
Algorithms for summation and dot product of floating-point numbers are presented which are fast in terms of measured computing time. We show that the computed results are as accurate as if computed in twice or K-fold working precision, $K\ge 3$. For ...
A monotonic superclass linearization for Dylan
Object-oriented languages with multiple inheritance and automatic conflict resolution typically use a linearization of superclasses to determine which version of a property to inherit when several superclasses provide definitions. Recent work has def...
An Improved Algorithm for hypot(a,b)
We develop a fast and accurate algorithm for evaluating $\sqrt{a^2+b^2}$ for two floating point numbers $a$ and $b$. Library functions that perform this computation are generally named {\tt hypot(a,b)}. We will compare four approaches that we will de...
Applications of Finite Automata Representing Large Vocabularies.
Abstract The construction of minimal acyclic deterministic partial finite automata to represent large natural language vocabularies is described. Applications of such automata include spelling checkers and advisers, multilanguage dictionaries, thesau...
Copy-and-patch compilation: a fast compilation algorithm for high-level languages and bytecode
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers. We present copy-and-patch, an extremely fast compilation technique that also pro...
Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm
The Sch\"onhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For $N$-bit numbers it has a time bound of $O(N \cdot \log N \cdot \log \log N)$. De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotical...
Fast recursive division
We present a new recursive method for division with remainder of integers. Its running time is $2K(n)+O(n \\log n)$ for division of a $2n$-digit number by an $n$-digit number where $K(n)$ is the Karatsuba multiplication time. It pays in p ractice for...
Left Recursion in Parsing Expression Grammars
Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PE...
Packrat parsers can support left recursion.
Packrat parsing offers several advantages over other parsing techniques, such as the guarantee of linear parse times while supporting backtracking and unlimited look-ahead. Unfortunately, the limited support for left recursion in packrat parser imple...
Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen
Abstract Der bei einer Summation auftretende Rundungsfehler kann als Maß für die Güte des verwendeten Verfahrens gelten. Im folgenden werden für mehrere Summierungsverfahren, unter anderem für das übliche und das Kahan‐Babuška‐Verfahren, a‐priori‐Sch...
Two-way string-matching
article Free Access Share on Two-way string-matching Authors: Maxime Crochemore Univ. Paris, Paris, France Univ. Paris, Paris, FranceView Profile , Dominique Perrin Univ. Paris, Paris, France Univ. Paris, Paris, FranceView Profile Authors Info & Clai...