There exist fast variants of the gcd algorithm which are all based on principles due to Knuth and Schonhage. On inputs of size n, these algorithms use a Divide and Conquer approach, perform FFT multiplications with co...
详细信息
There exist fast variants of the gcd algorithm which are all based on principles due to Knuth and Schonhage. On inputs of size n, these algorithms use a Divide and Conquer approach, perform FFT multiplications with complexity mu(n) and stop the recursion at a depth slightly smaller than lg n. A rough estimate of the worst-case complexity of these fast versions provides the bound O(mu(n) log n). Even the worst-case estimate is partly based on heuristics and is not actually proven. Here, we provide a precise probabilistic analysis of some of these fast variants, and we prove that their average bit-complexity on random inputs of size n is (sic) (mu(n) log n), with a precise remainder term, and estimates of the constant in the (sic)-term. Our analysis applies to any cases when the cost mu(n) is of order Omega(n log n), and is valid both for the FFT multiplication algorithm of Schonhage-Strassen, but also for the new algorithm introduced quite recently by Furer [Furer, M., 2007. Faster integer Multiplication. In: Proceedings of STOC'07, pp. 57-66]. We view such a fast algorithm as a sequence of what we call interrupted algorithms, and we obtain two main results about the (plain) euclid algorithm, which are of independent interest. We precisely describe the evolution of the distribution of numbers during the execution of the (plain) euclid algorithm, and we exhibit an (unexpected) density psi which plays a central role since it always appears at the beginning of each recursive call. This strong regularity phenomenon proves that the interrupted algorithms are locally "similar" to the total algorithm. This ultimately leads to the precise evaluation of the average bit-complexity of these fast algorithms. This work uses various tools, and is based on a precise study of generalised transfer operators related to the dynamical system underlying the euclid algorithm. (C) 2008 Elsevier Ltd. All rights reserved.
In this paper, a fast O(n(2)) algorithm is presented for computing recursive triangular factorization of a Bezoutian matrix associated with quasiseparable polynomials via a displacement equation. The new algorithm app...
详细信息
ISBN:
(纸本)9783319569321;9783319569307
In this paper, a fast O(n(2)) algorithm is presented for computing recursive triangular factorization of a Bezoutian matrix associated with quasiseparable polynomials via a displacement equation. The new algorithm applies to a fairly general class of quasiseparable polynomials that includes real orthogonal, Szegd polynomials, and several other important classes of polynomials, e.g., those defined by banded tiessenberg matrices. While the algorithm can be seen as a Schur-type for the Bezoutian matrix it can also be seen as a euclid-type for quasiseparable polynomials via factorization of a displacement equation. The process, i.e., fast euclid-type algorithm for quasiseparable polynomials or Schur-type algorithm for Bezoutian associated with quasiseparable polynomials, is carried out with the help of a displacement equation satisfied by Bezoutian and Confederate matrices leading to O (n(2)) complexity.
In this paper we take a fresh look at the well-known Berlekamp-Massey (BM) algorithm for decoding of Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) codes. RS and BCH codes are a very important family, of cycli...
详细信息
ISBN:
(纸本)9781538663783
In this paper we take a fresh look at the well-known Berlekamp-Massey (BM) algorithm for decoding of Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) codes. RS and BCH codes are a very important family, of cyclic codes, and are included in most elementary courses on code theory. One of the most important tools in decoding of RS and BCH codes was developed by Berlekamp, and later formulated as an algorithm for synthesizing short LFSR-s by Massey and is now known as the Berlekamp-Massey (BM) algorithm. An alternative algorithm for decoding such codes is the extended euclid algorithm. We present another viewpoint to the BM algorithm which is simpler than the Massey formulation, and mirrors the extended euclid algorithm. This presentation may replace the common treatment of the BM algorithm in elementary courses with a simpler and more rigorous presentation. Moreover, this approach enables to improve the HW implementation of BCH decoding. This is promising as BCH codes are gaining renewed interest lately in latency sensitive applications. Another advantage of the new approach is that it provides a simple derivation of erasure decoding.
In this paper, we present a semianalytical method for evaluating quadratic cost functionals for linear time-invariant systems with multiple time delays. The main computational tasks involved in the method are the solu...
详细信息
In this paper, we present a semianalytical method for evaluating quadratic cost functionals for linear time-invariant systems with multiple time delays. The main computational tasks involved in the method are the solution of a symbolic Diophantine equation by the euclid algorithm and the factorization of a finite degree polynomial. To illustrate the numerical implementation of the proposed method, an example is provided.
A novel VLSI design for a pipeline Reed-Solomon decoder is presented. The transform decoding technique used in a previous study is replaced by a time-domain algorithm through a detailed comparison of their VLSI implem...
详细信息
A novel VLSI design for a pipeline Reed-Solomon decoder is presented. The transform decoding technique used in a previous study is replaced by a time-domain algorithm through a detailed comparison of their VLSI implementations. An architecture that implements the time-domain algorithm permits efficient pipeline processing with reduced circuitry. Erasure correction capability is also incorporated with little additional complexity. By using multiplexing technique, an implementation of euclid"s algorithm maintains the throughput rate with less circuitry. Some improvements result in both enhanced capability and significant reduction in silicon area, making it possible to build the decoder on a single chip
A result by V. A. Bykovskii (1981) on the number of solutions of the congruence xy equivalent to l (mod q) under the graph of a twice continuously differentiable function is refined. As an application, Porter's re...
详细信息
A result by V. A. Bykovskii (1981) on the number of solutions of the congruence xy equivalent to l (mod q) under the graph of a twice continuously differentiable function is refined. As an application, Porter's result (1975) on the mean number of steps in the euclidean algorithm is sharpened and extended to the case of Gauss-Kuzmin statistics.
An asymptotic formula is found for the average number of local minima of three-dimensional complete integral lattices with determinant in the interval [1, N]. This is a generalization to the two-dimensional case of th...
详细信息
An asymptotic formula is found for the average number of local minima of three-dimensional complete integral lattices with determinant in the interval [1, N]. This is a generalization to the two-dimensional case of the classical result about the average length of a finite continued fraction with denominator belonging to [1, N].
A sensor node in a wireless sensor network has a limited machine word size. This limitation restricts the use of cryptographic algorithms developed for computer networks in a wireless sensor node. Most of the modern c...
详细信息
ISBN:
(纸本)9781424426027
A sensor node in a wireless sensor network has a limited machine word size. This limitation restricts the use of cryptographic algorithms developed for computer networks in a wireless sensor node. Most of the modern cryptographic algorithms use the multiplicative inverse of a Galois field and therefore it is important to develop storage- and energy-efficient approaches for sensors to calculate multiplicative inverses. This paper presents two techniques to compute multiplicative inverses of a Galois field of order prime p for a wireless sensor network. The performance of the proposed algorithm is compared with that of the extended euclid algorithm. The results show that the proposed approaches are storage- and energy-efficient, and are computationally better than the extended euclid algorithm.
暂无评论