Efficient multiple-precision integer division algorithm

Design and implementation of division algorithm is one of the most complicated problems in multi-precision arithmetic. Huang et al. [1] proposed an efficient multi-precision integer division algorithm, and experimentally showed that it is about three times faster than the most popular algorithms proposed by Knuth [2] and Smith [3]. This paper reports a bug in the algorithm of Huang et al. [1], and suggests the necessary corrections. The theoretical correctness proof of the proposed algorithm is also given. The resulting algorithm remains as fast as that of [1].     

On parallel integer sorting

We present an optimal algorithm for sortingn integers in the range [1,n ^c ] (for any constantc) for the EREW PRAM model where the word length isn , for any >0. Using this algorithm, the best known upper bound for integer sorting on the (O(logn) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.Supported by NSF-DCR-85-03251 and ONR contract N00014-87-K-0310     

On the optimal control of a hydroelectric power plant

A class of optimal control problems with phase restrictions is investigated whose performance index and state equation are linear in the control variable. First some necessary conditions for optimality are proved and then they are used to get the optimal solution.     

On one problem of integer optimization

A recognition problem of the following form is studied: to find put for the prescribed polyhedron whether the maximum of the linear objective function is achieved at its integral point. It is established that this problem is NP-hard in the general case and polynomially solvable in the class of rooted semimetric polyhedra.     

On the regularization of vector integer quadratic programming problems

For a vector integer quadratic programming problem, a regularizing operator is proposed that acts on a vector criterion and transforms a possibly unstable initial problem into a series of perturbed stable problems with the same Pareto set. The technique of ε-regularization is developed that allows replacing the considered problem by perturbed ε-stable problems. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 128–134, March–April 2009.     

On unification of terms with integer exponents

We consider terms in which some patterns can be repeatedn times.n is an integer variable which is part of the syntax of the terms (and hence may occur more than once in them). We show that unification of such terms is decidable and finitary, extending Chen and Hsiang's result onp-term unification. Finally, extending slightly the syntax yields an undecidable unification problem.     

On the K best integer network flows

We address the problem of finding the K best integer solutions of a linear integer network flow problem. We design an O(f(n,m,L,U)+KmS(n,m,L)) time and O(K+m) memory space algorithm to determine the K best integer solutions, in a directed network with n nodes, m arcs, maximum absolute value cost L, and an upper bound U on arc capacities and node supplies. f(n,m,L,U) is the best time needed to solve the minimum cost flow problem in a directed network and S(n,m,L) is the best time to solve the single-source shortest path problem in a network with non-negative lengths. The introduced algorithm efficiently determines a “proper minimal cycle” by taking advantage of the relationship between the best solutions. This way, we improve the theoretical as well as practical memory space bounds of the well-known method due to Hamacher. Our computational experiments confirm this result.     

On the OBDD complexity of the most significant bit of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. In this paper it is shown that the OBDD complexity of the most significant bit of integer multiplication is exponential answering an open question posed by Wegener (2000) [18].     

On the use of integer arithmetic to achieve confirmably correct computation

An example is provided from biostatistics to show that transformation to a unit normal deviate can be inadvisable. This is used to motivate a definition of commensurable units of measurement. An argument is presented to show that a unit cell size can be determined that is termed the ‘least distinguishable difference’. The recommended commensurable unit is obtained by reseating the least distinguishable difference to unity. Thus, the data are transformed to Integer-valued variates. Since the transformed data are integer-valued and optimally ranged for integer accumulation, this is recommended. On most computers integer overflow is detectable, therefore in the absence of overflow one is assured that the intervening computation is correct. A few concluding remarks are appended.     

On the linear complexity of bounded integer sequences over different moduli

We give a relation between the linear complexity over the integers and over the residue rings modulo m of a bounded integer sequence. This relation can be used to obtain a variety of new results for several sequences widely studied in the literature. In particular we apply it to Sidelnikov sequences.     

On the primitivity of the division of fuzzy relations

 Allowing for flexible queries enables database users to express preferences inside elementary conditions and priorities between conditions. The division is one of the algebraic operators defined in order to query regular databases. This operation aims at the selection of A-elements which are connected with (at least) a given subset of B-elements, e.g., the stores which ordered all the items supplied by a given manufacturer. It is mainly used in the framework of the relational model of data, although it makes sense in object-oriented databases as well. In the relational context, the division is a non-primitive operation which may be expressed in terms of other operations, namely projection, Cartesian product and set difference. When fuzzy predicates appear, this operator needs to be extended to fuzzy relations and this requires the replacement of the usual implication by a fuzzy one. This paper proposes two types of meaning of the extended division and it investigates the issue of the primitivity of the extended operation (i.e., if the division of fuzzy relations is expressible in terms of other operations). The final objective is to decide whether this operator is necessary or not for the purpose of flexible querying and to help the design of a query language supporting flexible queries, among which those conveying a division of fuzzy relations.     

A two-stage stochastic integer programming model for a thermal power system expansion

In this paper the obtaining of an optimum policy in the capacity expansion planning of a particular thermal‐electric power system is proposed. Therefore, a two‐stage stochastic integer programming is formulated. The model includes, through a finite group of scenarios, the existent uncertainty related to the future availability of the thermal plants currently under operation. The resultant model is solved numerically by the application of the L‐shaped method, whose implementation and development were executed using the software AMPL, with CPLEX as a solver. The results reached are shown, which validate the use of the methodology adopted in this work.     

A mixed integer programme for optimal static capacitor allocation in power systems

A method is presented for the determination of optimal size and location of static capacitor installations in a power system network for maintenance of the bus voltage magnitudes within prescribed limits under highly loaded or outage conditions. The problem is formulated as an optimization problem with the objective function representing the cost of capacitor installations and the constraints represent the reactive power flow equation of the system and the limits on the variations of the tap settings of the tap changing transformers and the generator bus voltages. The generator bus voltage magnitudes are continuously variable and the capacitor units to be installed and the tap settings are treated as discrete or integer variables. By partioning the variables into control and controlled quantities, a number of variables are eliminated from the problem. The problem is then decomposed into two smaller subproblems with integer or continuous variables. These result in the reduction of the computer memory and time requirements.