Recent interest in approximate computation is driven by its potential to achieve large energy savings. We formally demonstrate an optimal way to reduce energy via voltage over-scaling at the cost of errors due to timing starvation in addition. A fundamental trade-off between error frequency and error magnitude in a timing-starved adder has been identified. We introduce a formal model to prove that for signal processing applications using a quadratic signal-to-noise ratio error measure, reducing bit-wise error frequency is sub-optimal. Instead, energy-optimal approximate addition requires limiting maximum error magnitude. Intriguingly, due to possible error patterns, this is achieved by reducing carry chains significantly below what is allowed by the timing budget for a large fraction of sum bits, using an aligned, fixed internal-carry structure for higher significance bits. We further demonstrate that remaining approximation error is reduced by realization of conditional bounding (CB) logic for lower significance bits. A key contribution is the formalization of an approximate CB logic synthesis problem that produces a rich space of Pareto-optimal adders with a range of quality-energy trade-offs. We show how CB logic can be customized to result in over- and under-estimating approximate adders, and how a dithering adder that mixes them produces zero-centered error distributions, and, in accumulation, a reduced-variance error. This work demonstrates synthesized approximate adders with energy up to 60% smaller than that of a conventional timing-starved adder, where a 30% reduction is due to the superior synthesis of inexact CB logic. When used in a larger system implementing an image-processing algorithm, energy savings of 40% are possible. / text

The thesis is concerned with techniques for realizing optimum control that are suited for analogue computers. The first half of the thesis develops an iterative scheme for the solution of the two point boundary value problem. The theory of the iterative scheme is covered in detail and the scheme is implemented on an analogue computer. Studies of the scheme have also been made using a digital computer. The iterative scheme can be modified to cope with constraints on the control law. These modifications have been tested on a digital computer. The latter half of the thesis is concerned with approximation techniques which produce, very simple controllers. These techniques require a large digital computer, such as the IBM 7040, to do the design calculations. The first approximation technique developed from the calculus of variations is covered in detail including a complete controller designed and simulated. The second approximation technique based on dynamic programming is discussed and a few points are made about the features of the controller. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

En 1824, un mathématicien et astronome Iranien, ‘Alī Muḥammad ibn Muḥammad Ḥusayn al-Iṣfahānī, propose une nouvelle théorie des équations cubiques, dans un traité intitulé "Takmilat al-'Uyūn". Écrit en langue arabe dans un style ancien, sans symbolisme mathématique, ce traité est exclusivement consacré à la résolution des équations cubiques pour lesquelles il ne met en œuvre que des algorithmes numériques. Ce traité emprunte quelques algorithmes aux mathématiques de ses prédécesseurs comme Sharaf al-Dīn al-Ṭūsī, al-Kāshī ou al-Yazdī. Al-Iṣfahānī résout l'ensemble des vingt-cinq équations cubiques en utilisant les formules classiques connues depuis al-Khawārizmī pour toutes les équations du premier et second degré et celles du troisième degré réductibles au second degré. Il applique, sans se l'approprier, l'algorithme d'extraction de la racine chiffre par chiffre utilisé par Sharaf al-Dīn al-Ṭūsī, et plus tard par al-Yazdī, à l'ensemble des équations cubiques non réductibles au second degré mais qui ne contiennent pas le cube et le nombre dans un même membre de l'équation. Aux cinq équations qu’al-Ṭūsī résout par des méthodes analytiques de géométrie algébrique, celles qui contiennent le cube et le nombre dans un même membre de l'équation, il apporte un ensemble d'algorithmes tous basés sur l'idée d'une solution approchée initiale améliorée par le calcul itératif des termes d'une suite convergente. L'une de ces méthodes, fondée sur l'idée du calcul d'un point fixe d'une fonction, est déjà présente dans le traité d'al- Kāshī qui résout un ancien problème des mathématiques grecques: le calcul du sinus 1°. Une autre de ces méthodes résout ce type d'équations par une réduction de l'intervalle de la racine, et une troisième catégorie de méthode combine l'extraction de la racine chiffre par chiffre avec la réduction de l'intervalle. Le point commun entre ces algorithmes itératifs est que le nombre d'itérations ne peut pas être connu à priori, comme cela était possible dans l'algorithme d'extraction de la racine chiffre par chiffre. C'est visiblement la raison pour laquelle al-Iṣfahānī utilise l’expression de méthodes par 'Istiqrā' pour qualifier cette itération indéterminée : l'algorithme s'arrête lorsque la différence entre deux calculs successifs devient infiniment petite. Tout en se rattachant à la tradition des arithméticiens algébristes mais aussi à la tradition d'al-Khayyām/al-Ṭūsī, le traité d’al-Iṣfahānī constitue une contribution originale à la théorie des équations cubiques par l'analyse numérique. Un point remarquable dans ce traité doit être souligné: al-Iṣfahānī propose pour ces algorithmes plusieurs versions qui se distinguent entre elles par la complexité des calculs qu'il signale explicitement et qu'il montre à travers des exemples qu'il compare vis-à-vis de la quantité des calculs. L'objectif de cette thèse n'est nullement celui d'écrire l'histoire générale des équations cubiques dans les mathématiques arabes, mais partant de l'édition critique de Takmilat al 'Uyūn, d'étudier d'une part les algorithmes d’al-Iṣfahānī et d'autre part d'analyser les traditions mathématiques dans lesquelles il s'inscrit. / In 1824, an Iranian mathematician and astronomer, ‘Alī Muḥammad ibn Muḥammad Ḥusayn al-Iṣfahānī proposed a new theory of cubic equations in a treatise titled "Takmilat al-'Uyūn".Written in Arabic language in the ancient style, without mathematical symbolism, this treatise is exclusively dedicated to solving cubic equations for which it uses only numerical algorithms.This treatise borrows some algorithms from the mathematics of its predecessors, such as Sharaf al-Dīn al-Ṭūsī, al-Kāshī or al-Yazdī. Al-Iṣfahānī solves all the twenty-five cubic equations using the classical formulas, known since al-Khawārizmī, for all the equations of the first and second degree and those of the third degree reducible to the second degree.He applies, without appropriating it, the digit by digit root extraction algorithm used by Sharaf al-Dīn al-Ṭūsī and later by al-Yazdī to the set of cubic equations not reducible to the second degree and that contain the cube and the number on the same side of the equation.To the five equations that al-Ṭūsī solves by analytical methods of algebraic geometry, he gives a set of algorithms all based on the idea of an initial approximate solution improved by iteratively computed terms of a convergent suite.One of these methods, based on the idea of calculating the fixed point of a function, already exists in the treatise of al-Kāshī where he solves the ancient problem of Greek mathematics concerning the determination of the value of sinus 1°. Another one of these methods solves this kind of equations by reducing the interval of the root of the equation, and a third method combines the digit by digit root extraction with the interval reduction method.The common point between these iterative algorithms is that the number of iterations cannot be known in advance, before the calculation of the solution. This is obviously the reason why al-Iṣfahānī uses the expression of methods by 'Istiqrā’ to qualify this indeterminate iteration: the algorithm stops when the difference between two successive calculations becomes infinitely small.While relating to the tradition of algebraic arithmeticians, but also to the tradition of al-Khayyām/al-Ṭūsī, the treatise of al-Iṣfahānī is an original contribution to the theory of cubic equations by numerical analysis.A remarkable point in this treatise must be emphasized: al-Iṣfahānī gives for these iterative algorithms several versions that he compares with respect to the complexity of the calculations, and he explicitly indicates and shows it through many examples that he compares to the quantity of calculations.The purpose of this thesis is not to write the general history of cubic equations in Arabic mathematics, but starting from the critical edition of Takmilat al-'Uyūn we aim to study on the one hand the algorithms of al-Iṣfahānī and then to analyse the mathematical traditions within which his work is inscribed.