No description available.

Στα σύγχρονα ψηφιακά συστήματα η ανάγκη για γρήγορους υπολογισμούς είναι πλέον από τους πιο καθοριστικούς παράγοντες. Άλλοι ιδιαίτερα κρίσιμοι παράγοντες είναι η απαιτούμενη επιφάνεια του κυκλώματος και η κατανάλωση ενέργειας. Ωστόσο, ο χρόνος παραμένει ένας από τους πιο σημαντικούς για πλήθος εφαρμογές. Τα αριθμητικά κυκλώματα, όπως αθροιστές, πολλαπλασιαστές και κυκλώματα ύψωσης στο τετράγωνο, είναι πλέον αναπόσπαστο κομμάτι των ψηφιακών κυκλωμάτων, γι’ αυτό η επιτάχυνση των λειτουργιών αυτών είναι ένας στόχος στην κατεύθυνση του οποίου πολλές διαφορετικές αρχιτεκτονικές έχουν προταθεί. Η μείωση της καθυστέρησης στις αριθμητικές μονάδες θα δώσει μεγάλη βελτίωση στη συνολική απόδοση των συστημάτων, μιας και οι περισσότερες εφαρμογές εμπεριέχουν πλήθος αριθμητικών πράξεων. Η πράξη της ύψωσης στο τετράγωνο αποτελεί ειδική περίπτωση της πράξης του πολλαπλασιασμού, στην οποία ο πολλαπλασιαστέος ισούται με τον πολλαπλασιαστή. Ο λόγος για τον οποίο χρησιμοποιούμε εξειδικευμένα κυκλώματα για την πράξη αυτή είναι η εκμετάλλευση του γεγονότος ότι τα δύο έντελα είναι ίσα, κάτι που οδηγεί σε ελαχιστοποίηση του χρόνου που απαιτείται για την ολοκλήρωση της πράξης, αλλά και μείωση της απαιτούμενης επιφάνειας. Η πράξη της ύψωσης στο τετράγωνο χρησιμοποιείται σε πολλές εφαρμογές των υψηλής απόδοσης επεξεργαστών ψηφιακού σήματος (digital signal processors – DSP). Τέτοιες εφαρμογές συμπεριλαμβάνουν φιλτράρισμα σήματος (signal filtering), επεξεργασία εικόνας (image processing), και διαμόρφωση για τηλεπικοινωνιακά συστήματα. Η πράξη της ύψωσης στο τετράγωνο μπορεί, επίσης, να χρησιμοποιηθεί αποδοτικά στην υλοποίηση κρυπτογραφικών αλγορίθμων για την αποφυγή της χρονοβόρας διαδικασίας της ύψωσης σε δύναμη. Το Σύστημα Αριθμητικής Υπολοίπων (RNS), είναι ένα αριθμητικό σύστημα το οποίο παρουσιάζει σημαντικά πλεονεκτήματα στην ταχύτητα με την οποία μπορούν να γίνουν οι αριθμητικές πράξεις. Στο RNS οι αριθμοί αναπαρίστανται σαν ένα σύνολο από υπόλοιπα. Για να αναπαραστήσουμε έναν αριθμό ορίζουμε ένα σύνολο από πρώτους μεταξύ τους ακεραίους που ονομάζεται βάση του συστήματος P={p1,p2,…pk}. Η αναπαράσταση ενός αριθμού X στο RNS ορίζεται ως το σύνολο των υπολοίπων του Χ ως προς τα στοιχεία της βάσης Ρ. Προκύπτει, έτσι, ότι X={x1,x2,…,xk} όπου το xi είναι το υπόλοιπο της διαίρεσης του X με το στοιχείο της βάσης pi και συμβολίζεται με Xi=|X|pi. Κάθε ακέραιος Χ που ανήκει στο εύρος τιμών 0<=X<M, όπου Μ είναι το γινόμενο όλων των στοιχείων της βάσης P, έχει μοναδική αναπαράσταση στο RNS. Μια αριθμητική πράξη δύο εντέλων, η οποία μπορεί να είναι πρόσθεση, αφαίρεση ή πολλαπλασιασμός, ορίζεται ως εξής: {z1,z2,…,zk} = {x1,x2,…,xk}*{y1,y2,…,yk}, όπου zi = (xi*yi) modpi. Συνεπώς, κάθε αριθμητική πράξη εφαρμόζεται σε παράλληλες μονάδες (μία για κάθε στοιχείο της βάσης), καθεμία από τις οποίες διαχειρίζεται μικρούς αριθμούς (υπόλοιπα), αντί μιας μονάδας που θα χρειαζόταν να διαχειριστεί μεγάλους αριθμούς. Ένα από τα πιο δημοφιλή σύνολα βάσης είναι αυτά της μορφής {2^n, 2^n -1, 2^n+1}, λόγω του ότι προσφέρουν πολύ αποδοτικά κυκλώματα με κριτήριο το γινόμενο της επιφάνειας επί το τετράγωνο της καθυστέρησης (area * time^2), καθώς επίσης και αποδοτικούς μετατροπείς από και προς το δυαδικό σύστημα. Για το λόγο αυτό η υλοποίηση αποδοτικών modulo(2^n-1) και modulo(2n+1) κυκλωμάτων είναι σημαντική. Το πρόβλημα που παρουσιάζεται είναι ότι ενώ οι modulo(2^n) και modulo(2^n-1) αριθμητικές χρειάζονται το πολύ n δυαδικά ψηφία για την αναπαράσταση όλων των δυνατών υπολοίπων, στη modulo(2^n+1) αρχιτεκτονική χρειάζονται (n+1) ψηφία. Το πρόβλημα αυτό λύνεται με τη χρήση diminished-1 αναπαράστασης. Στη diminished-1 αναπαράσταση, κάθε αριθμός Χ αναπαρίσταται ως X-1=X-1. Έτσι, απαιτούνται n δυαδικά ψηφία για την αναπαράσταση, χρειάζονται, όμως, κυκλώματα μετατροπής από και προς την diminished-1 αναπαράσταση. Όταν χρησιμοποιείται η diminished-1 αναπαράσταση η τιμή εισόδου ίση με 0 χειρίζεται ξεχωριστά. Στα πλαίσια της εργασίας αναλύονται υπάρχουσες αρχιτεκτονικές και προτείνονται νέες για κυκλώματα ύψωσης στο τετράγωνο στο Σύστημα Αριθμητικής Υπολοίπων (RNS). Οι προτεινόμενες αρχιτεκτονικές βελτιώνουν την καθυστέρηση και, ταυτόχρονα, μειώνουν τις απαιτήσεις σε επιφάνεια. / Fast computations are of major importance in modern digital systems. Other critical factors are the area and the energy consumption. However, delay is still one of the most important ones for a variety of applications. Due to the fact that arithmetic circuits, such as adders, multipliers and squarers, have been integral components of most digital systems, many schemes have been proposed in the direction of accelerating arithmetic operations. As most applications contain a big number of arithmetic operations, delay reduction in arithmetic units will lead to significant improvement in the total system’s performance. Squaring is a special case of multiplication, where the multiplier equals the multiplicand. The reason for using a special circuit for squaring is to benefit from the fact that the two operands are equal, which reduces the delay and the area needed for the calculation of the square. The squaring operation is used in many applications of high performance digital signal processors. Such applications include signal filtering, image processing and modulation of communication components. Squarers can also find applicability in several cryptographic algorithms for the implementation of modular exponentiations. The Residue Number System is an arithmetic system in which arithmetic operations can be calculated in high speed. In the RNS numbers are represented as a set of residues. In order to represent a number we define a set of pairwise relative prime integers P={p1,p2,…pk}, which is the system’s base. Every number X is represented with the set of the residues occurred after the division of X by each element of the base, P. Thus, X={x1,x2,…,xk}, where xi stands for the residue of the division of X by the ith element of the base, pi, which is denoted as Xi=|X|pi. In the RNS there is a unique representation for every integer X that 0<=X<M, where M is the product of all the elements of the base. A two-operant arithmetic operation, which can be an addition, a subtraction or a multiplication, is defined as {z1,z2,…,zk} = {x1,x2,…,xk}*{y1,y2,…,yk}, where zi = (xi*yi) modpi. Consequently, arithmetic operations are performed to parallel units (one unit for each element of the base) each one handling small residues, instead of a single unit that handles large numbers. One of the most popular base sets is those of the form {2^n, 2^n -1, 2^n+1}, due to the fact that they offer very efficient circuits when considering the area*time^2 criterion and efficient converters from/to the binary system. Thus, the design of efficient modulo (2^n-1) and modulo (2^n+1) circuits is of high importance. The problem that arises is that while in modulo(2^n) and modulo(2^n-1) arithmetic n bits are sufficient for the representation of all possible residues, in modulo(2^n+1) arithmetic (n+1) bits are needed. This can be solved by the use of the diminished-1 representation. In the diminished-1 representation every number X is represented as X-1=X-1. Therefore, n bits are sufficient for the representation, but converters from/to the diminished-1 representation are needed. In cases that the diminished-1 representation is used, operands with value 0 is treated separately. For the needs of this thesis, existing architectures of squaring circuits in the RNS are studied and new ones are proposed. The proposed architectures improve the system’s delay, while, in parallel, reduce the area needs.

Made available in DSpace on 2016-04-27T16:58:52Z (GMT). No. of bitstreams: 1 Aloisio Daniel Vendeniatti.pdf: 1272014 bytes, checksum: 1262d89ac2880970c73eca396d22ca43 (MD5) Previous issue date: 2009-04-24 / Secretaria da Educação do Estado de São Paulo / The goal of this essay is to show aspects of genesis of number &#960;, inherent to the question of squaring the circle, which consists in constructing a square which has the same area as a given circle. This problem does not refer to a practical application of mathematics, but to the theoretic question that involves the distinction between a valid approach and thinking accuracy. The first attempt to squaring the circle dates back in the fifth century before Christ. After that, it was established that this construction should be carried through using a finite number of times, also the non-graduated ruler and the drawing compass itself. In the constructions with ruler and drawing compass we are referring to the first three postulates of Euclides Elements: 1) It´s possible to join two points by a straight line, 2) to expand a straight line until the necessary point, and 3) to draw a circumference around any point and with any radius. These postulates are the base of these constructions, sometimes called euclidean´s constructions. A real number &#945; is constructible, if feasible building a segment of legth &#945; with ruler and drawing compass, since a segment is taken as a unity. We show the idea of translating the geometrical problem of constructions made with ruler and drawing compass to the algebraic language and this allowed us to solve the problem of squaring the circle. We exposed that all constructible numbers are algebraic, over the rational numbers, establishing the impossibility of squaring the circle, with Lindemann´s demonstration, in 1882, of the number &#960; transcendence. This problem has been fascinating people for more than twenty centuries. We tried to supply all mathematical tools needed for this demonstration. Demonstrations play a fundamental role in the development of this essay, which purpose is not only to contribute to the math teacher formation, but also to detail the resolution of the problem of squaring the circle / O objetivo deste trabalho é apresentar aspectos da gênese do número &#960;, inerentes à questão da quadratura do círculo, a qual consiste em construir um quadrado de área igual à área de um círculo de raio r dado. Esse problema não diz respeito a uma aplicação prática da matemática, mas sim a uma questão teórica que envolve uma distinção entre uma boa aproximação e a exatidão do pensamento. O registro da primeira tentativa de se quadrar o círculo remonta a Anaxágoras, no século V a.C. Posteriormente, ficou estabelecido que essa construção deveria ser realizada utilizando-se, um número finito de vezes, a régua não graduada e o compasso. Nas construções com régua e compasso, estamos nos referindo aos três primeiros postulados dos Elementos de Euclides: 1) é possível unir dois pontos por uma reta, 2) prolongar uma linha reta até onde seja necessário e 3) traçar uma circunferência em torno de qualquer ponto e com qualquer raio. Esses postulados são a base dessas construções, muitas vezes chamadas de construções euclidianas. Um número real &#945; é construtível, se for possível "construir com régua e compasso um segmento de comprimento igual a &#945;, a partir de um segmento tomado como unidade". Apresentamos a idéia de traduzir o problema geométrico das construções com régua e compasso para a linguagem algébrica, e isso permitiu solucionar o problema da quadratura do círculo. Expomos que todo número construtível é algébrico sobre os racionais, estabelecendo a impossibilidade de quadrar o círculo com a demonstração de Lindemann, em 1882, da transcendência do número &#960;. Vemos que esse problema fascinou estudiosos por mais de 20 séculos. Procuramos fornecer todas as ferramentas matemáticas necessárias para essa demonstração. As demonstrações desempenham um papel fundamental no desenvolvimento deste trabalho, que tem por finalidade não só contribuir para a formação do professor de matemática, mas também detalhar a resolução do problema da quadratura do círculo

New algorithms for the matrix exponential and its Fréchet derivative are presented. First, we derive a new scaling and squaring algorithm (denoted expm[new]) for computing eA, where A is any square matrix, that mitigates the overscaling problem. The algorithm is built on the algorithm of Higham [SIAM J.Matrix Anal. Appl., 26(4): 1179-1193, 2005] but improves on it by two key features. The first, specific to triangular matrices, is to compute the diagonal elements in the squaring phase as exponentials instead of powering them. The second is to base the backward error analysis that underlies the algorithm on members of the sequence {||Ak||1/k} instead of ||A||. The terms ||Ak||1/k are estimated without computing powers of A by using a matrix 1-norm estimator. Second, a new algorithm is developed for computing the action of the matrix exponential on a matrix, etAB, where A is an n x n matrix and B is n x n₀ with n₀ << n. The algorithm works for any A, its computational cost is dominated by the formation of products of A with n x n₀ matrices, and the only input parameter is a backward error tolerance. The algorithm can return a single matrix etAB or a sequence etkAB on an equally spaced grid of points tk. It uses the scaling part of the scaling and squaring method together with a truncated Taylor series approximation to the exponential. It determines the amount of scaling and the Taylor degree using the strategy of expm[new].Preprocessing steps are used to reduce the cost of the algorithm. An important application of the algorithm is to exponential integrators for ordinary differential equations. It is shown that the sums of the form $\sum_{k=0}^p\varphi_k(A)u_k$ that arise in exponential integrators, where the $\varphi_k$ are related to the exponential function, can be expressed in terms of a single exponential of a matrix of dimension $n+p$ built by augmenting $A$ with additional rows and columns. Third, a general framework for simultaneously computing a matrix function, $f(A)$, and its Fréchet derivative in the direction $E$, $L_f(A,E)$, is established for a wide range of matrix functions. In particular, we extend the algorithm of Higham and $\mathrm{expm_{new}}$ to two algorithms that intertwine the evaluation of both $e^A$ and $L(A,E)$ at a cost about three times that for computing $e^A$ alone. These two extended algorithms are then adapted to algorithms that simultaneously calculate $e^A$ together with an estimate of its condition number. Finally, we show that $L_f(A,E)$, where $f$ is a real-valued matrix function and $A$ and $E$ are real matrices, can be approximated by $\Im f(A+ihE)/h$ for some suitably small $h$. This approximation generalizes the complex step approximation known in the scalar case, and is proved to be of second order in $h$ for analytic functions $f$ and also for the matrix sign function. It is shown that it does not suffer the inherent cancellation that limits the accuracy of finite difference approximations in floating point arithmetic. However, cancellation does nevertheless vitiate the approximation when the underlying method for evaluating $f$ employs complex arithmetic. The complex step approximation is attractive when specialized methods for evaluating the Fréchet derivative are not available.

TITLE: Agebraic Curves in History and School AUTHOR: Bc. Tomáš Fabián DEPARTMENT: The Department of mathematics and teaching of mathematics SUPERVISOR: prof. RNDr. Ladislav Kvasz, Dr. ABSTRACT: The thesis includes a series of exercises for senior high school students and the first year of university students. In these exercises, students will increase their knowledge about conics, especially how to draw them. Furthermore, students can learn about two unfamiliar curves: Conchoid and Quadratrix. All these curves are afterwards used for solving other problems - some Apollonius's problems, Three impossible constructions etc. Most of the construction is done in GeoGebra software. All the tasks are designed for students to learn how to work with this software. The subject discussed is put into historical context, and therefore the exercises are provided with historical commentary. The thesis also includes didactic notes, important or interesting solutions of exercises, possible issues, mistakes and another relevant notes. KEYWORDS: conic, circle, ellipse, parabola, hyperbole, conchoid, quadratrix, trisecting an angle, squaring the circle, rectification of the circle, doubling a cube, Apollonius's problem, GeoGebra

TITLE: Agebraic Curves in History and School AUTHOR: Bc. Tomáš Fabián DEPARTMENT: The Department of mathematics and teaching of mathematics SUPERVISOR: prof. RNDr. Ladislav Kvasz, Dr. ABSTRACT: The thesis includes a series of exercises for senior high school students and the first year of university students. In these exercises, students will increase their knowledge about conics, especially how to draw them. Furthermore, students can learn about two unfamiliar curves: Conchoid and Quadratrix. All these curves are afterwards used for solving other problems - some Apollonius's problems, Three impossible constructions etc. Most of the construction is done in GeoGebra software. All the tasks are designed for students to learn how to work with this software. The subject discussed is put into historical context, and therefore the exercises are provided with historical commentary. The thesis also includes didactic notes, important or interesting solutions of exercises, possible issues, mistakes and another relevant notes. KEYWORDS: conic, circle, ellipse, parabola, hyperbole, conchoid, quadratrix, trisecting an angle, squaring the circle, rectification of the circle, doubling a cube, Apollonius's problem, GeoGebra

The first International Congress of Mathematicians (ICM) was held in Zurich in 1897, setting the standards for all future ICMs. Whilst giving an overview of the congress itself, this thesis focuses on the Swiss organisers, who were predominantly university professors and secondary school teachers. As this thesis aims to offer some insight into their lives, it includes their biographies, highlighting their individual contributions to the congress. Furthermore, it explains why Zurich was chosen as the first host city and how the committee proceeded with the congress organisation. Two of the main organisers were the Swiss geometers Carl Friedrich Geiser (1843-1934) and Ferdinand Rudio (1856-1929). In addition to the congress, they also made valuable contributions to mathematical education, and in Rudio's case, the history of mathematics. Therefore, this thesis focuses primarily on these two mathematicians. As for Geiser, the relationship to his great-uncle Jakob Steiner is explained in more detail. Furthermore, his contributions to the administration of the Swiss Federal Institute of Technology are summarised. Due to the overarching theme of mathematical education and collaborations in this thesis, Geiser's schoolbook "Einleitung in die synthetische Geometrie" is considered in more detail and Geiser's methods are highlighted. A selection of Rudio's contributions to the history of mathematics is studied as well. His book "Archimedes, Huygens, Lambert, Legendre" is analysed and compared to E W Hobson's treatise "Squaring the Circle". Furthermore, Rudio's papers relating to the commentary of Simplicius on quadratures by Antiphon and Hippocrates are considered, focusing on Rudio's translation of the commentary and on "Die Möndchen des Hippokrates". The thesis concludes with an analysis of Rudio's popular lectures "Leonhard Euler" and "Über den Antheil der mathematischen Wissenschaften an der Kultur der Renaissance", which are prime examples of his approach to the history of mathematics.