As early as the 16th century. Simon Jacob, a German reckoning master, noticed that the worst case in computing the greatest common divisor of two numbers by the euclidean algorithm occurs if these numbers are equimult...
详细信息
As early as the 16th century. Simon Jacob, a German reckoning master, noticed that the worst case in computing the greatest common divisor of two numbers by the euclidean algorithm occurs if these numbers are equimultiples of two consecutive members of the Fibonacci sequence. (C) 1995 Academic Press, Inc.
We prove a quadratic expression for the Bezoutian of two univariate polynomials in terms of the remainders for the euclidean algorithm. In case of two polynomials of the same degree, or of consecutive degrees, this al...
详细信息
We prove a quadratic expression for the Bezoutian of two univariate polynomials in terms of the remainders for the euclidean algorithm. In case of two polynomials of the same degree, or of consecutive degrees, this allows us to interpret their Bezoutian as the Christoffel-Darboux kernel for a finite family of orthogonal polynomials, arising from the euclidean algorithm. We give orthogonality properties of remainders, and reproducing properties of Bezoutians.
Finding the intersection point of two lines in the plane is easy. But doing the same for a pair of algebraic plane curves is more difficult, not least because each point on both curves may be a multiple intersection p...
详细信息
Finding the intersection point of two lines in the plane is easy. But doing the same for a pair of algebraic plane curves is more difficult, not least because each point on both curves may be a multiple intersection point. However, we show that, with the help of the euclidean algorithm for polynomials, this general problem can be reduced to the case of intersecting lines, giving an algorithm for finding these intersection points, with multiplicities. It also yields a simple proof of Bézout’s theorem, giving the total number of such points.
In order to compute gcd of polynomials, the euclidean algorithm is used. We estimate the complexities of known euclidean algorithms. Further, we propose a heuristic euclidean algorithm. This is faster than ordinary me...
详细信息
In order to compute gcd of polynomials, the euclidean algorithm is used. We estimate the complexities of known euclidean algorithms. Further, we propose a heuristic euclidean algorithm. This is faster than ordinary methods under some special conditions by the use of the recurrent Karatsuba multiplication.
The need to reduce a periodic structure given in terms of a large supercell and associated lattice generators arises frequently in different fields of application of crystallography, in particular in the ab initio the...
详细信息
The need to reduce a periodic structure given in terms of a large supercell and associated lattice generators arises frequently in different fields of application of crystallography, in particular in the ab initio theoretical modelling of materials at the atomic scale. This paper considers the reduction of crystals and addresses the reduction associated with the existence of a commensurate translation that leaves the crystal invariant, providing a practical scheme for it. The reduction procedure hinges on a convenient integer factorization of the full period of the cycle (or grid) generated by the repeated applications of the invariant translation, and its iterative reduction into sub-cycles, each of which corresponds to a factor in the decomposition of the period. This is done in successive steps, each time solving a Diophantine linear equation by means of a euclidean reduction algorithm in order to provide the generators of the reduced lattice.
As with euclidean rings and rings admitting a restricted Nagata's pairwise algorithm, we will give an internal characterization of 2-stage euclidean rings. Applying this characterization we are capable of providin...
详细信息
As with euclidean rings and rings admitting a restricted Nagata's pairwise algorithm, we will give an internal characterization of 2-stage euclidean rings. Applying this characterization we are capable of providing infinitely many integral domains which are omega-stage euclidean but not 2-stage euclidean. Our examples solve finally a fundamental question related to the notion of k-stage euclidean rings raised by G.E. Cooke [G.E. Cooke, A weakening of the euclidean property for integral domains and applications to algebraic number theory I, J. Reine Angew, Math. 282 (1976) 133-156]. The question was stated as follows: "I do not know of an example of an omega-stage euclidean ring which is not 2-stage euclidean." Also, in this article we will give a method to construct the smallest restricted Nagata's pairwise algorithm theta on a unique factorization domain which admits a restricted Nagata's pairwise algorithm. It is of interest to point out that in a euclidean domain the shortest length d(a, b) of all terminating division chains starting from a pair (a, b) and the value theta(a, b) with g.c.d.(a, b) not equal 1 can be determined by each other. (C) 2011 Elsevier Inc. All rights reserved.
A modified form of Euclid's algorithm has gained popularity among musical composers following Toussaint's 2005 survey of so-called euclidean rhythms in world music. We offer a method to easily calculate Euclid...
详细信息
A modified form of Euclid's algorithm has gained popularity among musical composers following Toussaint's 2005 survey of so-called euclidean rhythms in world music. We offer a method to easily calculate Euclid's algorithm by hand as a modification of Bresenham's line-drawing algorithm. Notably, this modified algorithm is a nonrecursive matrix construction, using only modular arithmetic and combinatorics. This construction does not outperform the traditional divide-with-remainder method;it is presented for combinatorial interest and ease of hand computation.
The binary euclidean algorithm is a modification of the classical euclidean algorithm for computation of greatest common divisors which avoids ordinary integer division in favour of division by powers of two only. The...
详细信息
The binary euclidean algorithm is a modification of the classical euclidean algorithm for computation of greatest common divisors which avoids ordinary integer division in favour of division by powers of two only. The expectation of the number of steps taken by the binary euclidean algorithm when applied to pairs of integers of bounded size was first investigated by R.P. Brent in 1976 via a heuristic model of the algorithm as a random dynamical system. Based on numerical investigations of the expectation of the associated Ruelle transfer operator, Brent obtained a conjectural asymptotic expression for the mean number of steps performed by the algorithm when processing pairs of odd integers whose size is bounded by a large integer. In 1998 B. Vallee modified Brent's model via an induction scheme to rigorously prove an asymptotic formula for the average number of steps performed by the algorithm;however, the relationship of this result with Brent's heuristics remains conjectural. In this article we establish previously conjectural properties of Brent's transfer operator, showing directly that it possesses a spectral gap and preserves a unique continuous density. This density is shown to extend holomorphically to the complex right half-plane and to have a logarithmic singularity at zero. By combining these results with methods from classical analytic number theory we prove the correctness of three conjectured formulae for the expected number of steps, resolving several open questions promoted by D.E. Knuth in The Art of Computer Programming. (C) 2016 The Author. Published by Elsevier Inc.
In this paper, an efficient euclidean decoding algorithm is presented to solve the Berlekamp's key equation of Reed-Solomon (RS) code for correcting erasures as well as errors by replacing the initial condition of...
详细信息
ISBN:
(纸本)0780379780
In this paper, an efficient euclidean decoding algorithm is presented to solve the Berlekamp's key equation of Reed-Solomon (RS) code for correcting erasures as well as errors by replacing the initial condition of the euclidean algorithm with the erasure locator polynomial and the Forney syndrome polynomial. By this proposed algorithm, the errata locator polynomial and errata evaluator polynomial can be obtained simultaneously without the computations of polynomial division and field element inversion. Moreover, the whole recursive decoding produce for solving Berlekamp's key equation could be performed with a fixed number of iterations. And, the weights used to reduce the degree of the errata evaluator polynomial at each iteration can be extracted from the coefficient of fixed degree. As a consequence, the complexity of RS decoder to correct both errors and erasures is reduced substantially. Therefore, this Proposed algorithm provides more modular, regular and simple for both software and hardware implementation. An example using this proposed algorithm is given for a (255, 239) RS code for correcting erasures and errors with s + 2v less than or equal to 16.
暂无评论