检索结果-内蒙古大学图书馆

Regularity of the euclid algorithm;application to the analysis of fast GCD algorithms

JOURNAL OF SYMBOLIC COMPUTATION 2009年第7期44卷 726-767页

作者： Cesaratto, Eda Clement, Julien Daireaux, Benoit Lhote, Loick Maume-Deschamps, Veronique Vallee, Brigitte Univ Caen CNRS GREYC UMR 6072 F-14032 Caen France ENSICAEN Caen France Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina Univ Nacl Gral Sarmiento Inst Desarrollo Humano Buenos Aires DF Argentina IrisRes Ctr Stavanger Norway Univ Lyon 1 ISFA F-69365 Lyon France

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.

关键词： euclid algorithm Divide and conquer algorithms Fast multiplication Analysis of algorithms Transfer operators Perron formula

来源：评论

学校读者我要写书评

暂无评论

A Fast Schur-euclid-Type algorithm for Quasiseparable Polynomials 21st

引用

Conference on Applications of Computer Algebra (ACA)

作者： Perera, Sirani M. Olshevsky, Vadim Embry Riddle Aeronaut Univ Daytona Beach FL 32114 USA Univ Connecticut Storrs CT USA

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.

关键词： Quasiseparable matrices Bezoutians euclid algorithm Schur algorithm Fast algorithms Displacement structure

来源：评论

学校读者我要写书评

暂无评论

Berlekamp-Massey algorithm: euclid in Disguise

Berlekamp-Massey Algorithm: Euclid in Disguise

引用

IEEE International Conference on the Science of Electrical Engineering in Israel (ICSEE)

作者： Ilani, Ishai Western Digital Kefar Sava Israel

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.

关键词： BM algorithm euclid algorithm backward polynomial division backward euclid algorithm ged dom

来源：评论

学校读者我要写书评

暂无评论

Computation of quadratic cost functionals for linear systems with multiple time delays

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2000年第4期45卷 800-805页

作者： Hwang, JH Tsay, SY Hwang, C Natl Cheng Kung Univ Dept Chem Engn Tainan 701 Taiwan Natl Chung Cheng Univ Dept Chem Engn Chiayi 621 Taiwan

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.

关键词： euclid algorithm linear systems partial fraction expansion quadratic cost functionals time delays

来源：评论

学校读者我要写书评

暂无评论

ON THE VLSI DESIGN OF A PIPELINE REED-SOLOMON DECODER USING SYSTOLIC ARRAYS

引用

IEEE TRANSACTIONS ON COMPUTERS 1988年第10期37卷 1273-1280页

作者： SHAO, HM REED, IS CALTECH JET PROP LABPASADENACA 91109 UNIV SO CALIF DEPT ELECT ENGNLOS ANGELESCA 90089

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

关键词： Cellular Arrays Decoding VLSI Erasure Correction euclid algorithm VLSI Design Pipeline Reed Solomon Decoder Systolic Arrays Transform Decoding Technique Time Domain algorithm Multiplexing Technique Very Large Scale Integration Reed Solomon Codes Decoding Systolic Arrays Polynomials Pipeline Processing Circuits Computer Architecture algorithm Design And Analysis Throughput

来源：评论

学校读者我要写书评

暂无评论

ON THE NUMBER OF SOLUTIONS OF THE CONGRUENCE xy ≡ l (mod q) UNDER THE GRAPH OF A TWICE CONTINUOUSLY DIFFERENTIABLE FUNCTION

引用

ST PETERSBURG MATHEMATICAL JOURNAL 2009年第5期20卷 813-836页

作者： Ustinov, A. V. Russian Acad Sci Khabarovsk Div Inst Appl Math Far Eastern Branch Khabarovsk 680000 Russia

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.

关键词： euclid algorithm Gauss-Kuzmin statistics Kloosterman sums

来源：评论

学校读者我要写书评

暂无评论

AVERAGE NUMBER OF LOCAL MINIMA FOR THREE-DIMENSIONAL INTEGRAL LATTICES

引用

ST PETERSBURG MATHEMATICAL JOURNAL 2012年第3期23卷 551-570页

作者： Illarionov, A. A. Russian Acad Sci Khabarovsk Div Inst Appl Math Khabarovsk 680000 Russia

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... 详细信息

关键词： Lattice local minimum multidimensional continued fraction euclid algorithm

来源：评论

学校读者我要写书评

暂无评论

Calculating a Cryptographic Primitive: Suitable for Wireless Sensor Networks

Calculating a Cryptographic Primitive: Suitable for Wireless...

引用

Australasian Networks and Applications Conference 2008

作者： Suthaharan, Shan Univ N Carolina Dept Comp Sci Greensboro NC 27402 USA

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.

关键词： Wireless sensor networks Galois field multiplicative inverse euclid algorithm energy efficient

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：