101 results on '"Peter Kornerup"'
Search Results
2. On the Computation of Correctly-Rounded Sums.
- Author
-
Peter Kornerup, Vincent Lefèvre, Nicolas Louvet, and Jean-Michel Muller
- Published
- 2009
- Full Text
- View/download PDF
3. Single Precision Reciprocals by Multipartite Table Lookup.
- Author
-
Peter Kornerup and David W. Matula
- Published
- 2005
- Full Text
- View/download PDF
4. Revisiting SRT Quotient Digit Selection.
- Author
-
Peter Kornerup
- Published
- 2003
- Full Text
- View/download PDF
5. Modular Multiplication and Base Extensions in Residue Number Systems.
- Author
-
Jean-Claude Bajard, Laurent-Stéphane Didier, and Peter Kornerup
- Published
- 2001
- Full Text
- View/download PDF
6. An IWS Montgomery Modular Multiplication Algorithm.
- Author
-
Jean-Claude Bajard, Laurent-Stéphane Didier, and Peter Kornerup
- Published
- 1997
- Full Text
- View/download PDF
7. On Radix Representation of Rings.
- Author
-
Asger Munk Nielsen and Peter Kornerup
- Published
- 1997
- Full Text
- View/download PDF
8. Computing moments by prefix sums.
- Author
-
Feng Zhou and Peter Kornerup
- Published
- 1996
- Full Text
- View/download PDF
9. High Speed DCT/IDCT Using a Pipelined CORDIC Algorithm.
- Author
-
Feng Zhou and Peter Kornerup
- Published
- 1995
- Full Text
- View/download PDF
10. High-radix modular multiplication for cryptosystems.
- Author
-
Peter Kornerup
- Published
- 1993
- Full Text
- View/download PDF
11. Semantics for exact floating point operations.
- Author
-
Gerd Bohlender, Wolfgang Walter, Peter Kornerup, and David W. Matula
- Published
- 1991
- Full Text
- View/download PDF
12. A high-radix hardware algorithm for calculating the exponential ME modulo N.
- Author
-
Holger Orup and Peter Kornerup
- Published
- 1991
- Full Text
- View/download PDF
13. Architectural and Arithmetic Support for Multimedia (Dagstuhl Seminar 98351)
- Author
-
Guy Even and Peter Kornerup and Wolfgang Paul, Even, Guy, Kornerup, Peter, Paul, Wolfgang, Guy Even and Peter Kornerup and Wolfgang Paul, Even, Guy, Kornerup, Peter, and Paul, Wolfgang
- Published
- 2021
- Full Text
- View/download PDF
14. Reviewing 4-to-2 Adders for Multi-Operand Addition.
- Author
-
Peter Kornerup
- Published
- 2002
- Full Text
- View/download PDF
15. Necessary and Sufficient Conditions for Parallel, Constant Time Conversion and Addition.
- Author
-
Peter Kornerup
- Published
- 1999
- Full Text
- View/download PDF
16. Error bounds on complex floating-point multiplication with an fma
- Author
-
Peter Kornerup, Claude-Pierre Jeannerod, Jean-Michel Muller, Nicolas Louvet, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), ANR-13-INSE-0007,MetaLibm,Générateurs de code pour les fonctions mathématiques et les filtres(2013), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
Discrete mathematics ,Algebra and Number Theory ,Applied Mathematics ,Rounding ,[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic ,Mathematical analysis ,010103 numerical & computational mathematics ,01 natural sciences ,010101 applied mathematics ,Computational Mathematics ,Asymptotically optimal algorithm ,Approximation error ,Bounding overwatch ,Product (mathematics) ,Multiplication ,0101 mathematics ,Round-off error ,Unit (ring theory) ,Mathematics - Abstract
The accuracy analysis of complex floating-point multiplication done by Brent, Percival, and Zimmermann [{\it Math.~ Comp.}, 76:1469--1481, 2007] is extended to the case where a fused multiply-add (FMA) operation is available. Considering floating-point arithmetic with rounding to nearest and unit roundoff $u$, we show that their bound $\sqrt 5 \, u$ on the normwise relative error $|\hat z/z-1|$ of a complex product $z$ can be decreased further to $2u$ when using the FMA in the most naive way. Furthermore, we prove that the term $2u$ is asymptotically optimal not only for this naive FMA-based algorithm, but also for two other algorithms, which use the FMA operation as an efficient way of implementing rounding error compensation. Thus, although highly accurate in the componentwise sense, these two compensated algorithms bring no improvement to the normwise accuracy $2u$ already achieved using the FMA naively. Asymptotic optimality is established for each algorithm thanks to the explicit construction of floating-point inputs for which we prove that the normwise relative error then generated satisfies $|\hat z/z-1| \to 2u$ as $u\to 0$. All our results hold for IEEE floating-point arithmetic, with radix $\beta \ge 2$, precision $p \ge 2$, and rounding to nearest; it is only assumed that underflows and overflows do not occur and, when bounding errors from below, that $\beta^{p-1} \ge 12$.
- Published
- 2017
17. An approximate rational arithmetic system with intrinsic recovery of simple fractions during expression evaluation.
- Author
-
David W. Matula and Peter Kornerup
- Published
- 1979
- Full Text
- View/download PDF
18. Concepts of the MATHILDA System.
- Author
-
Peter Kornerup
- Published
- 1974
- Full Text
- View/download PDF
19. Firmware Development Systems, a Survey.
- Author
-
Peter Kornerup
- Published
- 1980
- Full Text
- View/download PDF
20. A bit-serial arithmetic unit for rational arithmetic.
- Author
-
Peter Kornerup and David W. Matula
- Published
- 1987
- Full Text
- View/download PDF
21. An integrated rational arithmetic unit.
- Author
-
Peter Kornerup and David W. Matula
- Published
- 1981
- Full Text
- View/download PDF
22. A feasibility analysis of fixed-slash rational arithmetic.
- Author
-
Peter Kornerup and David W. Matula
- Published
- 1978
- Full Text
- View/download PDF
23. An order preserving finite binary encoding of the rationals.
- Author
-
David W. Matula and Peter Kornerup
- Published
- 1983
- Full Text
- View/download PDF
24. Finite precision lexicographic continued fraction number systems.
- Author
-
Peter Kornerup and David W. Matula
- Published
- 1985
- Full Text
- View/download PDF
25. Exploiting redundancy in bit-pipelined rational arithmetic.
- Author
-
Peter Kornerup and David W. Matula
- Published
- 1989
- Full Text
- View/download PDF
26. The UNRAU a Unified Numeric Representation Arithmetic Unit.
- Author
-
Bruce D. Shriver and Peter Kornerup
- Published
- 1975
- Full Text
- View/download PDF
27. A unified numeric data type in Pascal.
- Author
-
Peter Kornerup
- Published
- 1975
- Full Text
- View/download PDF
28. A feasibility analysis of binary fixed-slash and floating-slash number systems.
- Author
-
David W. Matula and Peter Kornerup
- Published
- 1978
- Full Text
- View/download PDF
29. Reviewing High-Radix Signed Digit Adders
- Author
-
Peter Kornerup
- Subjects
Adder ,Binary tree ,Binary number ,Division (mathematics) ,Theoretical Computer Science ,Computational Theory and Mathematics ,Square root ,Hardware and Architecture ,Encoding (memory) ,Radix ,Arithmetic ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,Software ,Quotient ,Multi-operand addition, Signed Digit, Carry-Save, High-Radix ,Mathematics - Abstract
Higher radix values of the form $\beta=2^r$ have been employed traditionally for recoding of multipliers, and for determining quotient- and root-digits in iterative division and square root algorithms, usually only for quite moderate values of $r$, like 2 or 3. For fast additions, in particular for the accumulation of many terms, generally redundant representations are employed, most often binary carry-save or borrow-save, but in a number of publications it has been suggested to recode the addends into a higher radix. It is shown that there are no speed advantages in doing so if the radix is a power of~2, on the contrary, there are significant savings in using standard 4-to-2 adders, even saving half of the operations in multi-operand addition.
- Published
- 2015
30. Choosing starting values for certain Newton–Raphson iterations
- Author
-
Jean-Michel Muller, Peter Kornerup, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Computer arithmetic (ARENAIRE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
Mathematical optimization ,General Computer Science ,Square-Root Reciprocal ,[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] ,Monotonic function ,Square-Root ,010103 numerical & computational mathematics ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,symbols.namesake ,Square root ,0202 electrical engineering, electronic engineering, information engineering ,Applied mathematics ,Newton-Raphson iteration ,Root Extraction ,Newton raphson iteration ,0101 mathematics ,Newton's method ,Division ,Mathematics ,ACM B.2.4 ,G.1.0 ,Computer arithmetic ,Newton–Raphson iteration ,symbols ,020201 artificial intelligence & image processing ,Minification ,Arithmetic mean ,Computer Science(all) - Abstract
Adresse de la revue : http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description; We aim at finding the best possible seed values when computing $a^{\frac1p}$ using the Newton-Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function $f(a)$ in the interval $[a_{\min},a_{\max}]$, by building the sequence $x_n$ defined by the Newton-Raphson iteration, the natural choice consists in choosing $x_0$ equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between $x_0$ and $f(a)$. And yet, if we perform $n$ iterations, what matters is to minimize the maximum possible distance between $x_n$ and $f(a)$. In several examples, the value of the best starting point varies rather significantly with the number of iterations.
- Published
- 2006
- Full Text
- View/download PDF
31. Digit selection for SRT division and square root
- Author
-
Peter Kornerup
- Subjects
Divisor ,Truncation ,Division algorithm ,Theoretical Computer Science ,Self-descriptive number ,Computational Theory and Mathematics ,Square root ,Hardware and Architecture ,Methods of computing square roots ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Remainder ,Arithmetic ,Software ,Quotient ,Mathematics - Abstract
The quotient digit selection in the SRT division algorithm is based on a few most significant bits of the remainder and divisor, where the remainder is usually represented in a redundant representation. The number of leading bits needed depends on the quotient radix and digit set, and is usually found by an extensive search, to assure that the next quotient digit can be chosen as valid for all points (remainder, divisor) in a set defined by the truncated remainder and divisor, i.e., an "uncertainty rectangle." This work presents expressions for the number of bits needed from the truncated remainder and divisor (the truncation parameters), thus eliminating the need for a search through the truncation parameter space for validation. The analysis is then extended to the digit selection in SRT square root algorithms, where it is shown that, in general, it may be necessary to increase the number of leading bits needed for digit determination in a combined divide and square root algorithm. An easy condition to check the number of bits needed is established, also checking the number of initial digits of the root may have to be found by other means, e.g., by table look-up. The minimally redundant, radix-4 combined divide and square root algorithm is finally analyzed and it is shown that, in this case, it can be implemented without such a special table to determine initial digits for the square root.
- Published
- 2005
32. [Untitled]
- Author
-
Fei Zhou and Peter Kornerup
- Subjects
Prefix ,Moment (mathematics) ,Discrete mathematics ,Iterative method ,Computation ,Signal Processing ,Prefix sum ,Function (mathematics) ,Electrical and Electronic Engineering ,Binary logarithm ,Linear combination ,Information Systems ,Mathematics - Abstract
The goal of many image processing tasks is to recognise objects, to match scenes and to classify images. The shape, gray or colour features of objects are mainly used to describe objects. The most efficient method used to describe such features of an object is to use various transformed moments. We express the moments as a linear combination of higher order prefix sums, obtained by iterating the prefix sum computation on previous prefix sums, starting with the original function values. Thus the p'th moment m/sub p/=/spl Sigma//sub x=1//sup N/ x/sup p/f(x) can be computed by O(N/spl middot/p) additions followed by p multiply-adds. The prefix summations can be realized in time O(N) using p+1 simple adders, and in time O(p/spl middot/log N) using parallel prefix computation and O(N) adders. In 1986 Hatamian published a computationally equivalent algorithm, based on a cascade of filters performing the summations. Our recursive derivation allows for explicit expressions and recursive equations for the coefficients used in the final moment calculation. Thus a number of alternative forms for the moment computation can be derived, based on different sets of prefix sums, allowing some simplifications in the implementations.
- Published
- 2000
33. Guest Editors' Introduction: Special Section on Comuter Arithmetic
- Author
-
Jean-Michel Muller, Paolo Montuschi, Eric M. Schwarz, Peter Kornerup, Kornerup, Peter, Montuschi, Paolo, Muller, Jean-Michel, and Schwatz, Eric
- Subjects
Focus (computing) ,Computer science ,Elementary arithmetic ,Decimal arithmetic ,Mathematical proof ,Theoretical Computer Science ,Algebra ,Computational Theory and Mathematics ,Hardware and Architecture ,Special section ,Elementary function ,Multiplication ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,Arithmetic ,Software - Abstract
The eight articles in this special section focus on computer arithmetic. They are grouped onto four categories: decimal arithmetic, number systems, multiplication and elementary functions, and formal proofs.
- Published
- 2009
34. An RNS Montgomery modular multiplication algorithm
- Author
-
Laurent-Stéphane Didier, Jean-Claude Bajard, and Peter Kornerup
- Subjects
Computational complexity theory ,Modular arithmetic ,business.industry ,Cryptography ,Parallel computing ,Broadcasting ,Operand ,Residue number system ,Theoretical Computer Science ,Moduli ,Computer Science::Hardware Architecture ,Computational Theory and Mathematics ,Montgomery reduction ,Hardware and Architecture ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,Arithmetic ,business ,Mixed radix ,Algorithm ,Software ,Mathematics - Abstract
We present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a residue number system. By choosing the moduli of the RNS system reasonably large and implementing the system on a ring of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm can be implemented to run in O(n) time on O(n) processors, where n is the number of moduli in the RNS system, and the unit of time is a simple residue operation, possibly by table look-up. Two different implementations are proposed, one based on processors attached to a broadcast bus, another on an oriented ring structure.
- Published
- 1998
35. [Untitled]
- Author
-
Peter Kornerup and Feng Zhou
- Subjects
DFT matrix ,Computer science ,Discrete-time Fourier transform ,Bluestein's FFT algorithm ,Fast Fourier transform ,Prime-factor FFT algorithm ,Short-time Fourier transform ,Discrete Fourier transform ,Discrete Hartley transform ,Fractional Fourier transform ,Discrete Fourier transform (general) ,Cyclotomic fast Fourier transform ,Discrete sine transform ,Split-radix FFT algorithm ,Rader's FFT algorithm ,Signal Processing ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,Electrical and Electronic Engineering ,Arithmetic ,Harmonic wavelet transform ,Algorithm ,Information Systems - Abstract
This paper presents a new fast Discrete Fourier Transform (DFT) algorithm. By rewriting the DFT, a new algorithm is obtained that uses 2n?2(3n?13)+4n?2 real multiplications and 2n?2(7n?29)+6n+2 real additions for a real data N=2n point DFT, comparable to the number of operations in the Split-Radix method, but with slightly fewer multiply and add operations in total. Because of the organization of multiplications as plane rotations in this DFT algorithm, it is possible to apply a pipelined CORDIC algorithm in a hardware implementation of a long-point DFT, e.g., at a 100 MHz input rate, a 1024-point transform can be realized with a 200 MHz clocking of a single CORDIC pipeline.
- Published
- 1998
36. On the Computation of Correctly Rounded Sums
- Author
-
Vincent Lefèvre, Jean-Michel Muller, Peter Kornerup, Nicolas Louvet, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Computer arithmetic (ARENAIRE), ANR-06-BLAN-0257,EVA-Flo,Evaluation et Validation Automatique pour le calcul Flottant(2006), INRIA, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
Floating point ,Computer science ,Computation ,[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] ,Context (language use) ,010103 numerical & computational mathematics ,02 engineering and technology ,Minifloat ,01 natural sciences ,Theoretical Computer Science ,Set (abstract data type) ,Dependency graph ,0202 electrical engineering, electronic engineering, information engineering ,Radix ,0101 mathematics ,Arithmetic ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,2Sum and Fast2Sum algorithms. , Floating-point arithmetic , correct rounding , summation algorithms ,Mathematics ,Emulation ,[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic ,ACM: B.: Hardware/B.2: ARITHMETIC AND LOGIC STRUCTURES/B.2.4: High-Speed Arithmetic ,ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.0: General ,ACM B.2.4 ,G.1.0 ,020207 software engineering ,Floating-point arithmetic ,2Sum and Fast2Sum algorithms ,Computer Science::Numerical Analysis ,Correct rounding ,020202 computer hardware & architecture ,Computational Theory and Mathematics ,Hardware and Architecture ,Summation algorithms ,Computer Science::Mathematical Software ,Algorithm design ,Algorithm ,Software - Abstract
10 pages; International audience; This paper presents a study of some basic blocks needed in the design of floating-point summa- tion algorithms. In particular, in radix-2 floating-point arithmetic, we show that among the set of the algo- rithms with no comparisons performing only floating- point additions/subtractions, the 2Sum algorithm in- troduced by Knuth is minimal, both in terms of number of operations and depth of the dependency graph. We investigate the possible use of another algorithm, Dekker's Fast2Sum algorithm, in radix-10 arithmetic. We give methods for computing, in radix 10, the floating-point number nearest the average value of two floating-point numbers. We also prove that un- der reasonable conditions, an algorithm performing only round-to-nearest additions/subtractions cannot compute the round-to-nearest sum of at least three floating-point numbers. Starting from an algorithm due to Boldo and Melquiond, we also present new results about the computation of the correctly-rounded sum of three floating-point numbers. For a few of our algorithms, we assume new operations defined by the recent IEEE 754-2008 Standard are available.
- Published
- 2012
37. Digit-set conversions: generalizations and applications
- Author
-
Peter Kornerup
- Subjects
Lemma (mathematics) ,Computation ,Binary logarithm ,Digit sum ,Theoretical Computer Science ,Set (abstract data type) ,Computational Theory and Mathematics ,Hardware and Architecture ,Simple (abstract algebra) ,Multiplication ,Multiplier (economics) ,Arithmetic ,Algorithm ,Software ,Mathematics - Abstract
The problem of digit set conversion for fixed radix is investigated for the case of converting into a non redundant, as well as into a redundant, digit set. Conversion may be from very general digit sets, and covers as special cases multiplier recodings, additions, and certain multiplications. We generalize known algorithms for conversions into non redundant digit sets, as well as apply conversion to generalize the O(log n) time algorithm for conditional sum addition using parallel prefix computation, and a comparison is made with standard carry-lookahead techniques. Examples on multi-operand addition are used to illustrate the generality of this approach. O(1) time algorithms for converting into redundant digit sets are generalized based on a very simple lemma, which provides a framework for all conversions into redundant digit sets. Applications in multiplier recoding and partial product accumulation are used as exemplifications. >
- Published
- 1994
38. A systolic, linear-array multiplier for a class of right-shift algorithms
- Author
-
Peter Kornerup
- Subjects
Exponentiation ,Modular arithmetic ,Modular multiplicative inverse ,Systolic array ,Power of two ,Upper and lower bounds ,Theoretical Computer Science ,Computational Theory and Mathematics ,Gate count ,Hardware and Architecture ,Multiplier (economics) ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,Arithmetic ,Algorithm ,Software ,Mathematics - Abstract
A very simple multiplier cell is developed for use in a linear, purely systolic array forming a digit-serial multiplier for unsigned or 2'complement operands. Each cell produces two digit-product terms and accumulates these into a previous sum of the same weight, developing the product least significant digit first. Grouping two terms per cell, the ratio of active elements to latches is low, and only upper bound [n]/2 cells are needed for a full n by n multiply. A module-multiplier is then developed by incorporating a Montgomery type of module-reduction. Two such multipliers interconnect to form a purely systolic module exponentiator, capable of performing RSA encryption at very high clock frequencies, but with a low gate count and small area. It is also shown how the multiplier, with some simple back-end connections, can compute modular inverses and perform modular division for a power of two as modulus. >
- Published
- 1994
39. Augmented Precision Square Roots and 2-D Norms, and Discussion on Correctly Rounding sqrt(x^2+y^2)
- Author
-
Jean-Michel Muller, Nicolas Brisebarre, Mioara Joldes, Érik Martin-Dorel, Peter Kornerup, Computer arithmetic (ARENAIRE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), ANR-10-BLAN-0203,TaMaDi,Dilemme du Fabricant de Tables(2010), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
Discrete mathematics ,Floating point ,Rounding ,2D-norms ,[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] ,Approximation algorithm ,Floating-point arithmetic ,010103 numerical & computational mathematics ,02 engineering and technology ,square-root ,01 natural sciences ,Midpoint ,Electronic mail ,Correct rounding ,accurate computations ,Square root ,Approximation error ,020204 information systems ,ACM G.1.0 ,0202 electrical engineering, electronic engineering, information engineering ,Algorithm design ,compensated algorithms ,0101 mathematics ,Mathematics - Abstract
International audience; Define an "augmented precision" algorithm as an algorithm that returns, in precision-p floating-point arithmetic, its result as the unevaluated sum of two floating-point numbers, with a relative error of the order of 2^(−2p). Assuming an FMA instruction is available, we perform a tight error analysis of an augmented precision algorithm for the square root, and introduce two slightly different augmented precision algorithms for the 2D-norm sqrt(x^2 + y^2). Then we give tight lower bounds on the minimum distance (in ulps) between sqrt(x^2 + y^2) and a midpoint when sqrt(x^2 + y^2) is not itself a midpoint. This allows us to determine cases when our algorithms make it possible to return correctly-rounded 2D-norms.
- Published
- 2011
40. Addition
- Author
-
Peter Kornerup and David W. Matula
- Subjects
Two's complement ,Significand ,Sign extension ,Arbitrary-precision arithmetic ,Saturation arithmetic ,Finite field arithmetic ,Arithmetic ,Algorithm ,Affine arithmetic ,Extended precision ,Mathematics - Published
- 2010
41. Base and digit set conversion
- Author
-
Peter Kornerup and David W. Matula
- Subjects
Set (abstract data type) ,Computer science ,Arithmetic ,Base (topology) ,Numerical digit - Published
- 2010
42. Multiplication
- Author
-
David W. Matula and Peter Kornerup
- Subjects
Algebra ,Multiplication algorithm ,Arbitrary-precision arithmetic ,Kochanski multiplication ,Saturation arithmetic ,Arithmetic shift ,Multiplication ,Finite field arithmetic ,Arithmetic ,Extended precision ,Mathematics - Published
- 2010
43. Floating-point number systems
- Author
-
David W. Matula and Peter Kornerup
- Subjects
Floating point ,Mathematics ,Computational science - Published
- 2010
44. Radix polynomial representation
- Author
-
David W. Matula and Peter Kornerup
- Subjects
Discrete mathematics ,Radix point ,Hexadecimal ,Binary number ,Multiplication ,Radix ,Division (mathematics) ,Arithmetic ,Additive inverse ,Decimal ,Mathematics - Abstract
Introduction From the earliest cultures humans have used methods of recording numbers (integers), by notches in wooden sticks or collecting pebbles in piles or rows. Conventions for replacing a larger group or pile, e.g., five, ten, or twelve objects, by another object or marking, are also found in some early cultures. Number representations like these are examples of positional number systems , in which objects have different weight according to their relative positions in the number. The weights associated with different positions need not be related by a constant ratio between the weights of neighboring positions. In time, distance, old currency, and other measuring systems we find varying ratios between the different units of the same system, e.g., for time 60 minutes to the hour, 24 hours to the day, and 7 days to the week, etc. Systems with a constant ratio between the position weights are called radix systems; each position has a weight which is a power of the radix. Such systems can be traced back to the Babylonians who used radix 60 for astronomical calculations, however without a specific notation for positioning of the unit, so it can be considered a kind of floating-point notation. Manipulating numbers in such a notation is fairly convenient for multiplication and division, as is known for anyone who has used a slide rule. Our decimal notation with its fixed radix point seems to have been developed in India about 600 CE, but without decimal fractions.
- Published
- 2010
45. Modular arithmetic and residue number systems
- Author
-
Peter Kornerup and David W. Matula
- Subjects
Discrete mathematics ,Modular arithmetic ,Integer ,business.industry ,Modulo ,Prime number ,Subtraction ,Cryptography ,Residue number system ,business ,Separable space ,Mathematics - Abstract
Introduction In many applications integer computations are to be performed modulo some given constant. One such area is cryptology, where often multiplications, inversions, and exponentiations are to be performed modulo some very large integer. Hence we shall here investigate algorithms for such operations in their own right, but also because these can be used as primitives for the implementation of multiple modulus systems , also denoted residue number systems and abbreviated to RNSs . Here an integer is represented by a set of residues (the values of the integer modulo a set of given integer moduli, often chosen to be prime numbers). In such systems computations in a large integer domain can be performed truly in parallel on completely independent processors (often called “channels”), one for each modulus from the set of moduli, and thus operating in a much smaller domain. Due to this independence, additions can be performed “carry-free” in the sense that there is no interaction between the computations of the channels, each of which is operating on integers from a smaller domain. The same applies to multiplication, and as we have pointed out in Chapter 3, such arithmetic is one way to minimize the h j -separable sets, and thus to decrease the computation time by exploiting parallelism. Addition, subtraction, and multiplication in particular can thus be efficiently implemented, whereas other operations like division and comparisons are much more difficult.
- Published
- 2010
46. Square root
- Author
-
David W. Matula and Peter Kornerup
- Subjects
Kahan summation algorithm ,Root mean square ,symbols.namesake ,Square root ,symbols ,Arithmetic ,Invariant (mathematics) ,Geometric mean ,Newton's method ,Affine arithmetic ,Scientific software ,Mathematics - Published
- 2010
47. Finite Precision Number Systems and Arithmetic
- Author
-
Peter Kornerup and David W. Matula
- Abstract
Fundamental arithmetic operations support virtually all of the engineering, scientific, and financial computations required for practical applications, from cryptography, to financial planning, to rocket science. This comprehensive reference provides researchers with the thorough understanding of number representations that is a necessary foundation for designing efficient arithmetic algorithms. Using the elementary foundations of radix number systems as a basis for arithmetic, the authors develop and compare alternative algorithms for the fundamental operations of addition, multiplication, division, and square root with precisely defined roundings. Various finite precision number systems are investigated, with the focus on comparative analysis of practically efficient algorithms for closed arithmetic operations over these systems. Each chapter begins with an introduction to its contents and ends with bibliographic notes and an extensive bibliography. The book may also be used for graduate teaching: problems and exercises are scattered throughout the text and a solutions manual is available for instructors.
- Published
- 2010
48. Guest editors' introduction - Special issue on computer arithmetic
- Author
-
Peter Kornerup and Israel Koren
- Subjects
Very-large-scale integration ,Computational Theory and Mathematics ,Hardware and Architecture ,Computer science ,business.industry ,Cryptography ,Algorithm design ,Radix ,Arithmetic ,business ,Software ,Theoretical Computer Science - Abstract
—————————— ✦ —————————— DVANCES in VLSI technology and the availability of sophisticated circuit design and testing tools have made it feasible to implement very complex algorithms directly in hardware. Consequently, we are now witnessing the design and fabrication of special-purpose capabilities beyond those previously realized only in software. Arithmetic calculations play a crucial role in many applications for which speed is essential, e.g., digital signal processing, cryptography, and telecommunications. The accelerating pursuit of higher speed must be realized in tandem with satisfying user demands for higher numeric precision and standardization of the results of arithmetic operations. This necessitates algorithm design which exploits parallelism at all levels and meshes with the underlying physical technology. The explosion of research and implementation proceeding in this manner is nowhere more evident than in the advanced arithmetic capabilities provided in today's contemporary microprocessors. Computer arithmetic draws upon mathematics, computer science, and electrical engineering both in creating a theoretical framework and in improving the specific implementation technology. While the basic principles and inherent limitations of arithmetic on standard radix representations have been known for some decades, the variations and fine tunings appropriate to the currently available implementation technologies, and today's more aggressive utilization of parallelism, provide fertile areas for fundamental research and innovative design. The objective of this special issue is to present some of the state-of-the-art developments in computer arithmetic. The papers included in this special issue were selected from
- Published
- 2000
49. Performing Arithmetic Operations on Round-to-Nearest Representations
- Author
-
Jean-Michel Muller, A Panhaleux, Peter Kornerup, Computer arithmetic (ARENAIRE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
Floating point ,Floating-point representation ,Logarithm ,Computation ,[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] ,Double-rounding ,Binary number ,02 engineering and technology ,Signed-digit ,01 natural sciences ,Theoretical Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,0101 mathematics ,Arithmetic ,Round-to-nearest ,Fixed-point arithmetic ,Constant-time rounding and sign-inversion ,Mathematics ,Two's complement ,Rounding ,[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic ,Computer arithmetic ,020202 computer hardware & architecture ,010101 applied mathematics ,Computational Theory and Mathematics ,Hardware and Architecture ,ACM G.1.0 ,ACM B.2.4 ,Signed zero ,Algorithm ,Software ,Arithmetic and logic units - Abstract
Pre-print, 24 pages, submitted to IEEE Transactions on Computers.; During any composite computation there is a constant need for rounding intermediate results before they can participate in further processing. Recently a class of number representations denoted RN-Codings were introduced, allowing an un-biased rounding-to-nearest to take place by a simple truncation, with the property that problems with double-roundings are avoided. In this paper we first investigate a particular encoding of the binary representation. This encoding is generalized to any radix and digit set; however radix complement representations for even values of the radix turn out to be particularly feasible. The encoding is essentially an ordinary radix complement representation with an appended round-bit, but still allowing rounding to nearest by truncation and thus avoiding problems with double-roundings. Conversions from radix complement to these round-to-nearest representations can be performed in constant time, whereas conversion the other way in general takes at least logarithmic time. Not only is rounding-to-nearest a constant time operation, but so is also sign inversion, both of which are at best log-time operations on ordinary 2's complement representations. Addition and multiplication on such fixed-point representations are first analyzed and defined in such a way that rounding information can be carried along in a meaningful way, at minimal cost. The analysis is carried through for a compact (canonical) encoding using 2's complement representation, supplied with a round-bit. Based on the fixed-point encoding it is shown possible to define floating point representations, and a sketch of the implementation of an FPU is presented.
- Published
- 2009
50. Correcting the Normalization Shift of Redundant Binary Representations
- Author
-
Peter Kornerup
- Subjects
Normalization (statistics) ,Floating point ,Rounding ,Subtraction ,Approximation algorithm ,Binary number ,Theoretical Computer Science ,Redundant binary representation ,Significand ,Computational Theory and Mathematics ,Hardware and Architecture ,Arithmetic ,Algorithm ,Software ,Mathematics - Abstract
An important problem in the realization of floating-point subtraction is the identification of the position of the first nonzero digit in a radix-represented number, since the significand usually is to be represented left-normalized in the part of the word(s) allocated for representing its value. There are well-known log-time algorithms for determining this position for numbers in nonredundant representations, which may also be applied to suitably (linear-time) transformed redundant representations. However, due to the redundancy in the latter case, the position thus determined may need a correction by one. When determination of the shift amount is to be performed in parallel with conversion to nonredundant representation (the subtraction), it must be performed on the redundant representation. This is also the case when the significand is to be retained in a redundant representation until the final rounding. This paper presents an improved algorithm for determining the need for a correction of the normalization shift amount, which can be run in parallel with the algorithm finding the "approximate" position.
- Published
- 2009
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.