Classical Compilers

A modified ziggurat algorithm for generating exponentially- and normally-distributed pseudorandom numbers

The Ziggurat Algorithm is a very fast rejection sampling method for generating PseudoRandom Numbers (PRNs) from common statistical distributions. The algorithm divides a distribution into rectangular layers that stack on top of each other (resembling...

An Efficient Method for Generating Discrete Random Variables with General Distributions

article Free Access Share on An Efficient Method for Generating Discrete Random Variables with General Distributions Author: Alastair J. Walker Department of Electrical Engineering, University of Witwatersrand, 1 Jan Smuts Ave., Johnnesburg 2001, Sou...

An Extension of the String-to-String Correction Problem

article Free Access Share on An Extension of the String-to-String Correction Problem Authors: Robert A. Wagner Department of Systems and Information Sciences, Vanderbilt University, Nashville, TN Department of Systems and Information Sciences, Vander...

Computationally easy, spectrally good multipliers for congruential pseudorandom number generators

Congruential pseudorandom number generators rely on good multipliers, that is, integers that have good performance with respect to the spectral test. We provide lists of multipliers with a good lattice structure up to dimension eight and up to lag ei...

Gaussian random number generators

Rapid generation of high quality Gaussian random numbers is a key capability for simulations across a wide range of disciplines. Advances in computing have brought the power to conduct simulations with very large numbers of random numbers and with it...

GoBench: A Benchmark Suite of Real-World Go Concurrency Bugs

Go, a fast growing programming language, is often considered as “the programming language of the cloud”. The language provides a rich set of synchronization primitives, making it easy to write concurrent programs with great parallelism. However. the ...

Implementing the complex arcsine and arccosine functions using exception handling

We develop efficient algorithms for reliable and accurate evaluatins of the complex arcsine and arccosine functions. A tight error bound is derived for each algorithm; the results are valid for all machine-representable points in the complex plane. T...

LXM: better splittable pseudorandom number generators (and almost as fast)

In 2014, Steele, Lea, and Flood presented SplitMix, an object-oriented pseudorandom number generator (prng) that is quite fast (9 64-bit arithmetic/logical operations per 64 bits generated) and also splittable . A conventional prng object provides a ...

Module-Lattice-Based Key-Encapsulation Mechanism Standard

A key-encapsulation mechanism (KEM) is a set of algorithms that, under certain conditions, can be used by two parties to establish a shared secret key over a public channel. A shared secret key that is securely established using a KEM can then be use...

Optimally profiling and tracing programs

This paper presents algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs. Profiling counts the number of times each basic block in a program executes and has a variety ...

Printing floating-point numbers quickly and accurately

This paper presents a fast and accurate algorithm for printing floating-point numbers in both free- and fixed-format modes. In free-format mode, the algorithm generates the shortest, correctly rounded output string that converts to the same number wh...

Scalable statistics counters

Statistics counters are important for purposes such as detecting excessively high rates of various system events, or for mechanisms that adapt based on event frequency. As systems grow and become increasingly NUMA, commonly used naive counters impose...

SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash

The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation's measurement and standards infrastructure.ITL deve...

SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions

SLEEF: A Portable Vectorized Library of C Standard Mathematical Functions

In this paper, we present techniques used to implement our portable\nvectorized library of C standard mathematical functions written entirely in C\nlanguage. In order to make the library portable while maintaining good\nperformance, intrinsic functio...

The keyed-hash message authentication code (HMAC)

This Standard describes a keyed-hash message authentication code (HMAC), a mechanism for message authentication using cryptographic hash functions. HMAC can be used with any iterative Approved cryptographic hash function, in combination with a shared...

The Least Weight Subsequence Problem (Extended Abstract)

The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in O(n log n) time generally and, for certain w...

The Monty Python method for generating random variables

We suggest an interesting and fast method for generating normal, exponential, t, von Mises, and certain other important random variables used in Monte Carlo studies. The right half of a symmetric density is cut into pieces, then, using simple area-pr...

Topological sorting of large networks

Topological Sorting is a procedure required for many problems involving analysis of networks. An example of one such problem is PERT. The present paper presents a very general method for obtaining topological order. It permits treatment of larger net...

Unveiling and Vanquishing Goroutine Leaks in Enterprise Microservices: A Dynamic Analysis Approach

Go is a modern programming language gaining popularity in enterprise microservice systems. Concurrency is a first-class citizen in Go with lightweight “goroutines” as the building blocks of concurrent execution. Go advocates message-passing to commun...