BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Richard P. Brent

Richard P. Brent contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.NTData Structures and Algorithmsmath.NAmath.COComputationNumerical AnalysisDiscrete MathematicsDistributed, Parallel, and Cluster Computingmath.CAmath.HOMathematical Softwarequant-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
34works
0followers
12topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

34 published item(s)

preprint2021arXiv

Computation of Maximal Determinants of Binary Circulant Matrices

We describe algorithms for computing maximal determinants of binary circulant matrices of small orders. Here "binary matrix" means a matrix whose elements are drawn from $\{0,1\}$ or $\{-1,1\}$. We describe efficient parallel algorithms for the search, using Duval's algorithm for generation of necklaces and the well-known representation of the determinant of a circulant in terms of roots of unity. Tables of maximal determinants are given for orders $\le 53$. Our computations extend earlier results and disprove two plausible conjectures.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On asymptotic approximations to the log-Gamma and Riemann-Siegel theta functions

We give bounds on the error in the asymptotic approximation of the log-Gamma function $\lnΓ(z)$ for complex $z$ in the right half-plane. These improve on earlier bounds by Behnke and Sommer (1962), Spira (1971), and Hare (1997). We show that $|R_{k+1}(z)/T_k(z)| < \sqrt{πk}$ for nonzero $z$ in the right half-plane, where $T_k(z)$ is the $k$-th term in the asymptotic series, and $R_{k+1}(z)$ is the error incurred in truncating the series after $k$ terms. If $k \le |z|$, then the stronger bound $|R_{k+1}(z)/T_k(z)| < (k/|z|)^2/(π^2-1) < 0.113$ holds. Similarly for the asymptotic approximation of $\lnΓ(z+\frac{1}{2})$, except that a factor $η_k = 1/(1-2^{1-2k})$ multiplies some of the bounds. We deduce similar bounds for asymptotic approximation of the Riemann-Siegel theta function $\vartheta(t)$. We show that the accuracy of a well-known approximation to $\vartheta(t)$ can be improved by including an exponentially small term in the approximation. This improves the attainable accuracy for real $t>0$ from $O(\exp(-πt))$ to $O(\exp(-2πt))$. We discuss a similar example due to Olver (1964), and a connection with the Stokes phenomenon.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Generalising Tuenter&#39;s binomial sums

Tuenter [Fibonacci Quarterly 40 (2002), 175-180] and other authors have considered centred binomial sums of the form \[S_r(n) = \sum_k \binom{2n}{k}|n-k|^r,\] where $r$ and $n$ are non-negative integers. We consider sums of the form \[U_r(n) = \sum_k \binom{n}{k}|n/2-k|^r\] which are a generalisation of Tuenter&#39;s sums as $S_r(n) = U_r(2n)$ but $U_r(n)$ is also well-defined for odd arguments $n$. $U_r(n)$ may be interpreted as a moment of a symmetric Bernoulli random walk with $n$ steps. The form of $U_r(n)$ depends on the parities of both $r$ and $n$. In fact, $U_r(n)$ is the product of a polynomial (depending on the parities of $r$ and $n$) times a power of two or a binomial coefficient. In all cases the polynomials can be expressed in terms of Dumont-Foata polynomials. We give recurrence relations, generating functions and explicit formulas for the functions $U_r(n)$ and/or the associated polynomials.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A note on the real part of the Riemann zeta-function

We consider the real part $\Re(ζ(s))$ of the Riemann zeta-function $ζ(s)$ in the half-plane $\Re(s) \ge 1$. We show how to compute accurately the constant $σ_0 = 1.19\ldots$ which is defined to be the supremum of $σ$ such that $\Re(ζ(σ+it))$ can be negative (or zero) for some real $t$. We also consider intervals where $\Re(ζ(1+it)) \le 0$ and show that they are rare. The first occurs for $t$ approximately 682112.9, and has length about 0.05. We list the first fifty such intervals.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Further analysis of the binary Euclidean algorithm

The binary Euclidean algorithm is a variant of the classical Euclidean algorithm. It avoids multiplications and divisions, except by powers of two, so is potentially faster than the classical algorithm on a binary machine. We describe the binary algorithm and consider its average case behaviour. In particular, we correct some errors in the literature, discuss some results of Vallée, and describe a numerical computation which supports a conjecture of Vallée.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lower bounds on maximal determinants of +-1 matrices via the probabilistic method

We show that the maximal determinant D(n) for $n \times n$ ${\pm 1}$-matrices satisfies $R(n) := D(n)/n^{n/2} \ge κ_d > 0$. Here $n^{n/2}$ is the Hadamard upper bound, and $κ_d$ depends only on $d := n-h$, where $h$ is the maximal order of a Hadamard matrix with $h \le n$. Previous lower bounds on R(n) depend on both $d$ and $n$. Our bounds are improvements, for all sufficiently large $n$, if $d > 1$. We give various lower bounds on R(n) that depend only on $d$. For example, $R(n) \ge 0.07 (0.352)^d > 3^{-(d+3)}$. For any fixed $d \ge 0$ we have $R(n) \ge (2/(πe))^{d/2}$ for all sufficiently large $n$ (and conjecturally for all positive $n$). If the Hadamard conjecture is true, then $d \le 3$ and $κ_d \ge (2/(πe))^{d/2} > 1/9$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Note on a double binomial sum relevant to the Hadamard maximal determinant problem

We prove a double binomial sum identity which differs from most binomial sum identities in that the summands involve the absolute value function. The identity is of interest because it can be used in proofs of lower bounds for the Hadamard maximal determinant problem. Our proof of the identity uses a two-variable variant of the method of telescoping sums.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On minors of maximal determinant matrices

By an old result of Cohn (1965), a Hadamard matrix of order n has no proper Hadamard submatrices of order m > n/2. We generalise this result to maximal determinant submatrices of Hadamard matrices, and show that an interval of length asymptotically equal to n/2 is excluded from the allowable orders. We make a conjecture regarding a lower bound for sums of squares of minors of maximal determinant matrices, and give evidence in support of the conjecture. We give tables of the values taken by the minors of all maximal determinant matrices of orders up to and including 21 and make some observations on the data. Finally, we describe the algorithms that were used to compute the tables.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Finding D-optimal designs by randomised decomposition and switching

The Hadamard maximal determinant (maxdet) problem is to find the maximum determinant D(n) of a square {+1, -1} matrix of given order n. Such a matrix with maximum determinant is called a saturated D-optimal design. We consider some cases where n > 2 is not divisible by 4, so the Hadamard bound is not attainable, but bounds due to Barba or Ehlich and Wojtas may be attainable. If R is a matrix with maximal (or conjectured maximal) determinant, then G = RR^T is the corresponding Gram matrix. For the cases that we consider, maximal or conjectured maximal Gram matrices are known. We show how to generate many Hadamard equivalence classes of solutions from a given Gram matrix G, using a randomised decomposition algorithm and row/column switching. In particular, we consider orders 26, 27 and 33, and obtain new saturated D-optimal designs (for order 26) and new conjectured saturated D-optimal designs (for orders 27 and 33).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

High-Performance Pseudo-Random Number Generation on Graphics Processing Units

This work considers the deployment of pseudo-random number generators (PRNGs) on graphics processing units (GPUs), developing an approach based on the xorgens generator to rapidly produce pseudo-random numbers of high statistical quality. The chosen algorithm has configurable state size and period, making it ideal for tuning to the GPU architecture. We present a comparison of both speed and statistical quality with other common parallel, GPU-based PRNGs, demonstrating favourable performance of the xorgens-based approach.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A fast vectorised implementation of Wallace&#39;s normal random number generator

Wallace has proposed a new class of pseudo-random generators for normal variates. These generators do not require a stream of uniform pseudo-random numbers, except for initialisation. The inner loops are essentially matrix-vector multiplications and are very suitable for implementation on vector processors or vector/parallel processors such as the Fujitsu VPP300. In this report we outline Wallace&#39;s idea, consider some variations on it, and describe a vectorised implementation RANN4 which is more than three times faster than its best competitors (the Polar and Box-Muller methods) on the Fujitsu VP2200 and VPP300.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An asymptotic expansion inspired by Ramanujan

Corollary 2, Entry 9, Chapter 4 of Ramanujan&#39;s first notebook claims that a certain sum is asymptotic to ln(x) + gamma, where x is a real variable in the sum and gamma is Euler&#39;s constant. Ramanujan&#39;s claim is known to be correct for the case n = 1, but incorrect for n > 2 (here n is an integer parameter in the sum). We show that the result is correct for n = 2. We also consider the order of the error term, and discuss a different, correct generalisation of the case n = 1.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An O(M(n) log n) algorithm for the Jacobi symbol

The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n) log n), using Schönhage&#39;s fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n) log n) algorithm based on the binary recursive gcd algorithm of Stehlé and Zimmermann. Our implementation - which to our knowledge is the first to run in time O(M(n) log n) - is faster than GMP&#39;s quadratic implementation for inputs larger than about 10000 decimal digits.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Factorizations of Cunningham numbers with bases 13 to 99

This Report updates the tables of factorizations of a^n +- 1 for 13 < a < 100, previously published as CWI Report NM-R9212 (June 1992) and updated in CWI Report NM-R9419 (Update 1, September 1994) and CWI Report NM-R9609 (Update 2, March 1996). A total of 951 new entries in the tables are given here. The factorizations are now complete for n < 76, and there are no composite cofactors smaller than 10^102.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Fast normal random number generators on vector processors

We consider pseudo-random number generators suitable for vector processors. In particular, we describe vectorised implementations of the Box-Muller and Polar methods, and show that they give good performance on the Fujitsu VP2200. We also consider some other popular methods, e.g. the Ratio method of Kinderman and Monahan (1977) (as improved by Leva (1992)), and the method of Von Neumann and Forsythe, and show why they are unlikely to be competitive with the Polar method on vector processors.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

George Forsythe&#39;s last paper

We describe von Neumann&#39;s elegant idea for sampling from the exponential distribution, Forsythe&#39;s generalization for sampling from a probability distribution whose density has the form exp(-G(x)), where G(x) is easy to compute (e.g. a polynomial), and my refinement of these ideas to give an efficient algorithm for generating pseudo-random numbers with a normal distribution. Later developments are also mentioned.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

MP users guide

MP is a package of ANSI Standard Fortran (ANS X3.9-1966) subroutines for performing multiple-precision floating-point arithmetic and evaluating elementary and special functions. The subroutines are machine independent and the precision is arbitrary, subject to storage limitations. The User&#39;s Guide describes the routines and their calling sequences, example and test programs, use of the Augment precompiler, and gives installation instructions for the package.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Note on Computing Ratings from Eigenvectors

We consider the problem of computing ratings using the results of games played between a set of n players, and show how this problem can be reduced to computing the positive eigenvectors corresponding to the dominant eigenvalues of certain n by n matrices. There is a close connection with the stationary probability distributions of certain Markov chains. In practice, if n is large, then the matrices involved will be sparse, and the power method may be used to solve the eigenvalue problems efficiently. We give an algorithm based on the power method, and also derive the same algorithm by an independent method.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On computing factors of cyclotomic polynomials

For odd square-free n > 1 the n-th cyclotomic polynomial satisfies an identity of Gauss. There are similar identity of Aurifeuille, Le Lasseur and Lucas. These identities all involve certain polynomials with integer coefficients. We show how these coefficients can be computed by simple algorithms which require O(n^2) arithmetic operations and work over the integers. We also give explicit formulae and generating functions for the polynomials, and illustrate the application to integer factorization with some numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the periods of generalized Fibonacci recurrences

We give a simple condition for a linear recurrence (mod 2^w) of degree r to have the maximal possible period 2^(w-1).(2^r-1). It follows that the period is maximal in the cases of interest for pseudo-random number generation, i.e. for 3-term linear recurrences defined by trinomials which are primitive (mod 2) and of degree r > 2. We consider the enumeration of certain exceptional polynomials which do not give maximal period, and list all such polynomials of degree less than 15.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the precision attainable with various floating-point number systems

For scientific computations on a digital computer the set of real number is usually approximated by a finite set F of &#34;floating-point&#34; numbers. We compare the numerical accuracy possible with difference choices of F having approximately the same range and requiring the same word length. In particular, we compare different choices of base (or radix) in the usual floating-point systems. The emphasis is on the choice of F, not on the details of the number representation or the arithmetic, but both rounded and truncated arithmetic are considered. Theoretical results are given, and some simulations of typical floating-point computations (forming sums, solving systems of linear equations, finding eigenvalues) are described. If the leading fraction bit of a normalized base 2 number is not stored explicitly (saving a bit), and the criterion is to minimize the mean square roundoff error, then base 2 is best. If unnormalized numbers are allowed, so the first bit must be stored explicitly, then base 4 (or sometimes base 8) is the best of the usual systems.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Some integer factorization algorithms using elliptic curves

Lenstra&#39;s integer factorization algorithm is asymptotically one of the fastest known algorithms, and is ideally suited for parallel computation. We suggest a way in which the algorithm can be speeded up by the addition of a second phase. Under some plausible assumptions, the speedup is of order log(p), where p is the factor which is found. In practice the speedup is significant. We mention some refinements which give greater speedup, an alternative way of implementing a second phase, and the connection with Pollard&#39;s &#34;p-1&#34; factorization algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Some linear-time algorithms for systolic arrays

We survey some results on linear-time algorithms for systolic arrays. In particular, we show how the greatest common divisor (GCD) of two polynomials of degree n over a finite field can be computed in time O(n) on a linear systolic array of O(n) cells; similarly for the GCD of two n-bit binary numbers. We show how n * n Toeplitz systems of linear equations can be solved in time O(n) on a linear array of O(n) cells, each of which has constant memory size (independent of n). Finally, we outline how a two-dimensional square array of O(n)* O(n) cells can be used to solve (to working accuracy) the eigenvalue problem for a symmetric real n* n matrix in time O(nS(n)). Here S(n) is a slowly growing function of n; for practical purposes S(n) can be regarded as a constant. In addition to their theoretical interest, these results have potential applications in the areas of error-correcting codes, symbolic and algebraic computations, signal processing and image processing.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Some long-period random number generators using shifts and xors

Marsaglia recently introduced a class of xorshift random number generators (RNGs) with periods 2n-1 for n = 32, 64, etc. Here we give a generalisation of Marsaglia&#39;s xorshift generators in order to obtain fast and high-quality RNGs with extremely long periods. RNGs based on primitive trinomials may be unsatisfactory because a trinomial has very small weight. In contrast, our generators can be chosen so that their minimal polynomials have large weight (number of nonzero terms). A computer search using Magma has found good generators for n a power of two up to 4096. These have been implemented in a free software package xorgens.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The myth of equidistribution for high-dimensional simulation

A pseudo-random number generator (RNG) might be used to generate w-bit random samples in d dimensions if the number of state bits is at least dw. Some RNGs perform better than others and the concept of equidistribution has been introduced in the literature in order to rank different RNGs. We define what it means for a RNG to be (d,w)-equidistributed, and then argue that (d,w)-equidistribution is not necessarily a desirable property.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Unrestricted algorithms for elementary and special functions

We describe some &#34;unrestricted&#34; algorithms which are useful for the computation of elementary and special functions when the precision required is not known in advance. Several general classes of algorithms are identified and illustrated by examples. The topics include: power series methods, use of halving identities, asymptotic expansions, continued fractions, recurrence relations, Newton&#39;s method, numerical contour integration, and the arithmetic-geometric mean. Most of the algorithms discussed are implemented in the MP package (arXiv:1004.3173).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Uses of randomness in computation

Random number generators are widely used in practical algorithms. Examples include simulation, number theory (primality testing and integer factorization), fault tolerance, routing, cryptography, optimization by simulated annealing, and perfect hashing. Complexity theory usually considers the worst-case behaviour of deterministic algorithms, but it can also consider average-case behaviour if it is assumed that the input data is drawn randomly from a given distribution. Rabin popularised the idea of &#34;probabilistic&#34; algorithms, where randomness is incorporated into the algorithm instead of being assumed in the input data. Yao showed that there is a close connection between the complexity of probabilistic algorithms and the average-case complexity of deterministic algorithms. We give examples of the uses of randomness in computation, discuss the contributions of Rabin, Yao and others, and mention some open questions. This is the text of an invited talk presented at &#34;Theory Day&#34;, University of NSW, Sydney, 22 April 1994.

0 citations0 reviewsNo code linkedOpen access