The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.2.9 Arbitrary Precision Arithmetic

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: Two very large integers, x and y.

Problem: What is x+y, x-y, x x y and x / y?

Excerpt from The Algorithm Design Manual: Any programming language whose level rises above basic assembler supports single- and perhaps double-precision integer/real addition, subtraction, multiplication, and division. But what if we wanted to represent the national debt of the United States in pennies? One trillion dollars worth of pennies requires 15 decimal digits, which is far more than can fit into a 32-bit integer.

In other applications much larger integers are needed. The RSA algorithm for public-key cryptography requires integer keys of at least 100 digits to achieve any level of security, and 1000 digits are recommended. Experimenting with number-theoretic conjectures for fun or research always requires playing with large numbers.


Implementations

  • PARI - Package for Number Theory (C) (rating 9)
  • High-Precision Software Directory (C++, FORTRAN) (rating 7)
  • Handbook of Algorithms and Data Structures (C,Pascal) (rating 5)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 4)
  • Algorithms in C++ -- Sedgewick (C++) (rating 3)

  • Recommended Books

    A Computational Introduction to Number Theory and Algebra by V. Shoup Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky The Art of Computer Programming : Seminumerical Algorithms by Donald Knuth
    Algorithmic Number Theory : Efficient Algorithms by Eric Bach and Jeffrey Shallit Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein Introduction to Algorithms by U. Manber
    The Design and Analysis of Computer Algorithms by A. Aho and J. Hopcroft and J. Ullman

    Related Problems


      
    Calendrical Calculations
      
    Cryptography
      
    Factoring and Primality Testing
      
    Discrete Fourier Transform



    This page last modified on 2008-07-10 .
    www.algorist.com