Assuming a widely believed hypothesis concerning the least prime in an arithmetic progression, we show that polynomials of degree less than \( n \) over a finite field \( \mathbb {F}_q \) with \( q \) elements can be multiplied in time \(\( O (n \log ...\)

We start with a mathematical definition of a real interval as a closed, connected set of reals. Interval arithmetic operations (addition, subtraction, multiplication, and division) are likewise defined mathematically and we provide algorithms for ...

Methods are presented for finding reductions between the computations of certain arithmetic functions that preserve asymptotic Boolean complexities (circuit depth or size). They can be used to show, for example, that all nonlinear algebraic functions ...

Let E be an arithmetic expression involving n variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the ...

Let ƒ(x) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let M(n) be the number of single-precision operations required to multiply n-bit integers. It is shown that ƒ(x) can be evaluated, with relative error Ο(2^-n), in Ο(...

The problem of computing a desired function value to within a prescribed tolerance can be formulated in the following two distinct ways: Formulation I: Given x and ∈ > 0, compute f(x) to within ∈. Formulation II: Given only that x is in a closed ...

It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log₂n + 10(n - 1)/p using p ≥ 1 processors which can ...

Efficiently computable a posteriori error bounds are attained by using a posteriori models for bounding roundoff errors in the basic floating-point operations. Forward error bounds are found for inner product and polynomial evaluations. An analysis of ...

A bound on the relative error in floating-point addition using a single-precision accumulator with guard digits is derived. It is shown that even with a single guard digit, the accuracy can be almost as good as that using a double-precision accumulator. ...

Finite-precision interval arithmetic evaluation of a function ƒ of n variables at an n-dimensional rectangle T which is the Cartesian product of intervals yields an interval which is denoted by F(T). Correspondingly, finite-precision real arithmetic ...

The problem of evaluating arithmetic expressions on a machine with N ≥ 1 general purpose registers is considered. It is initially assumed that no algebraic laws apply to the operators and operands in the expression. An algorithm for evaluation of ...

A definition is given of computer interval arithmetic suitable for implementation on a digital computer. Some computational properties and simplifications are derived. An ALGOL code segment is proved to be a correct implementation of the definition on a ...

Winograd has considered the time necessary to perform numerical addition and multiplication and to perform group multiplication by means of logical circuits consisting of elements each having a limited number of input lines and unit delay in computing ...

The fifth in a series of experiments in semi-automated mathematics is described. These experiments culminated in large complex computer programs which allow a mathematician to prove mathematical theorems on an man/machine basis. SAM V, the fifth program,...