Transcript b - Department of Computer Science

Programming Interest Group
http://www.comp.hkbu.edu.hk/~chxw/pig/index.htm
Tutorial Four
High-Precision Arithmetic
1
Machine Arithmetic

32-bit machine


64-bit machine



An integer is roughly in the range ±231=
±2,147,483,648
An integer is roughly in the range ±263=
±9,223,372,036,854,775,808
Unsigned integer can double the upper limit
Sometimes we need to operate on very large
integers, especially in the area of cryptography

High-precision integers, or multiple precision integers
2
Integer Libraries

C:


<stdlib.h>, <math.h>
C++:

GNU C++: Integer class


http://www.chemie.fuberlin.de/chemnet/use/info/libgpp/libgpp_20.html
Java:

BigInteger class in java.math

http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigIn
teger.html
3
Java BigInteger Example

Factorial n (usually written n!) is the product of all
integers up to and including n (1x 2 x 3 x ... x n).
import java.math.BigInteger;
public class Factorial {
public static void main(String[] args) {
//-- BigInteger solution.
BigInteger n = BigInteger.ONE;
for (int i=1; i<=20; i++) {
n = n.multiply(BigInteger.valueOf(i));
System.out.println(i + "! = " + n);
}
//-- int solution (BAD IDEA BECAUSE ONLY WORKS TO 12).
int fact = 1;
for (int i=1; i<=20; i++) {
fact = fact * i;
System.out.println(i + "! = " + fact);
}
}
}
4
Java BigInteger Example (Cont.)
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 1932053504
14! = 1278945280
15! = 2004310016
16! = 2004189184
17! = -288522240
18! = -898433024
19! = 109641728
20! = -2102132736
BAD
BAD
BAD
BAD
BAD
BAD
BAD
BAD
5
What are we doing now?


As a CS student, it’s not enough to just know
how to use those high-precision integer
libraries.
It’s better to know how to design and
implement a high-precision integer arithmetic
library.


One student from our department has done this
as his Honours Project.
Addition, subtraction, multiplication, and
division, modular, exponentiation, etc
6
Review of Number Systems


Positional notation using base b (or radix b) is
defined by the rule:
Radix Point
(…a3a2a1a0.a-1a-2…)b
= …+a3b3+a2b2+a1b1+a0+a-1b-1+a-2b-2+…
Binary number system: b = 2


Decimal number system: b = 10


2 digits: 0 and 1
10 digits: 0, 1, 2, 3, …, 9
Hexadecimal number system: b = 16

16 digits: 0, 1, 2, …, 9, A, B, C, D, E, F
7
High-precision Integers

How to represent enormous integers?

Arrays of digits
 The initial element of the array represents the least
significant digits:

An integer 1234567890 is stored as an array:
{0, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Maintain a counter for the number of digits
 Maintain the sign of the integer: positive or negative?
Linked list of digits
 It can support real arbitrary precision arithmetic
 But:




Waste of memory (each node takes a pointer)
The performance is not as good as arrays
8
An Example: Using Array
http://www.comp.hkbu.edu.hk/~chxw/pig/code/bignum.c
#define MAXDIGITS 100
/*maximum length bignum */
#define PLUS 1
/* positive sign bit */
#define MINUS -1
/* negative sign bit */
typedef struct {
char digits[MAXDIGITS];
/* represent the number */
int signbit;
/* PLUS or MINUS */
int lastdigit;
/* index of high-order digit */
} bignum;
Remarks:
1. Each digit (0-9) is represented using a single-byte character.
2. In fact, using higher numerical bases (e.g., 64, 128, 256) is more efficient.
9
Print a Bignum
void print_bignum(bignum *nPtr)
{
int i;
if (nPtr->signbit == MINUS)
printf(“-”);
for (i = nPtr->lastdigit; i >= 0; i--)
printf(“%c”, ‘0’+nPtr->digits[i]);
printf(“\n”);
}
10
Convert an Integer to Bignum
int_to_bignum(int s, bignum *nPtr)
{
int i;
int t;
/* counter */
/* int to work with */
if (s >= 0) nPtr->signbit = PLUS;
else nPtr->signbit = MINUS;
for (i=0; i<MAXDIGITS; i++)
nPtr->digits[i] = (char) 0;
nPtr->lastdigit = -1;
t = abs(s);
while (t > 0) {
nPtr->lastdigit ++;
nPtr->digits[ nPtr->lastdigit ] = (t % 10);
t = t / 10;
}
if (s == 0) nPtr->lastdigit = 0;
}
11
Initialize a Bignum
initialize_bignum(bignum *nPtr)
{
int_to_bignum(0,nPtr);
}
int max(int a, int b)
{
if (a > b) return(a);
else return(b);
}
12
Compare Two Bignums
compare_bignum(bignum *a, bignum *b)
{
int i;
/* counter */
if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);
if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);
for (i = a->lastdigit; i>=0; i--) {
if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
}
return(0);
}
13
How to avoid leading zeros?
zero_justify(bignum *n)
{
while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
n->lastdigit --;
if ((n->lastdigit == 0) && (n->digits[0] == 0))
n->signbit = PLUS;
/* hack to avoid -0 */
}
14
Addition of Two Bignums
add_bignum(bignum *a, bignum *b, bignum *c)
{
int carry;
/* carry digit */
int i;
/* counter */
initialize_bignum(c);
if (a->signbit == b->signbit) c->signbit = a->signbit;
else {
if (a->signbit == MINUS) {
a->signbit = PLUS;
subtract_bignum(b,a,c);
a->signbit = MINUS;
} else {
b->signbit = PLUS;
subtract_bignum(a,b,c);
b->signbit = MINUS;
}
return;
}
15
Addition of Two Bignums (cont.)
c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
carry = 0;
for (i=0; i<=(c->lastdigit); i++) {
c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10;
carry = (carry + a->digits[i] + b->digits[i]) / 10;
}
zero_justify(c);
}
16
Subtraction of Two Bignums
subtract_bignum(bignum *a, bignum *b, bignum *c)
{
int borrow;
/* has anything been borrowed? */
int v;
/* placeholder digit */
int i;
/* counter */
initialize_bignum(c);
if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
b->signbit = -1 * b->signbit;
add_bignum(a,b,c);
b->signbit = -1 * b->signbit;
return;
}
if (compare_bignum(a,b) == PLUS) {
subtract_bignum(b,a,c);
c->signbit = MINUS;
return;
}
17
Subtraction of Two Bignums (Cont.)
c->lastdigit = max(a->lastdigit,b->lastdigit);
borrow = 0;
for (i=0; i<=(c->lastdigit); i++) {
v = (a->digits[i] - borrow - b->digits[i]);
if (a->digits[i] > 0)
borrow = 0;
if (v < 0) {
v = v + 10;
borrow = 1;
}
c->digits[i] = (char) v % 10;
}
zero_justify(c);
}
18
Digit Shift
/* E.g., shift 123456 by 2 will get 12345600
In memory:
{6,5,4,3,2,1}  {0,0,6,5,4,3,2,1}
*/
digit_shift(bignum *nPtr, int d)
/* multiply *nPtr by 10^d */
{
int i;
/* counter */
if ((nPtr->lastdigit == 0) && (nPtr->digits[0] == 0)) return;
for (i=nPtr->lastdigit; i>=0; i--)
nPtr->digits[i+d] = nPtr->digits[i];
for (i=0; i<d; i++) nPtr->digits[i] = 0;
nPtr->lastdigit = nPtr->lastdigit + d;
}
19
Multiplication of Two Bignums
multiply_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row;
/* represent shifted row */
bignum tmp;
/* placeholder bignum */
int i, j;
/* counters */
initialize_bignum(c);
row = *a;
for (i=0; i <= b->lastdigit; i++) {
for (j=1; j <= b->digits[i]; j++) {
add_bignum(c,&row,&tmp);
*c = tmp;
}
digit_shift(&row,1);
}
c->signbit = a->signbit * b->signbit;
zero_justify(c);
}
20
Division of Two Bignums
divide_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row;
/* represent shifted row */
bignum tmp;
/* placeholder bignum */
int asign, bsign;
/* temporary signs */
int i, j;
/* counters */
initialize_bignum(c);
c->signbit = a->signbit * b->signbit;
asign = a->signbit;
bsign = b->signbit;
a->signbit = PLUS;
b->signbit = PLUS;
21
Division of Two Bignums (Cont.)
initialize_bignum(&row);
initialize_bignum(&tmp);
c->lastdigit = a->lastdigit;
for (i=a->lastdigit; i >= 0; i--) {
digit_shift(&row,1);
row.digits[0] = a->digits[i];
c->digits[i] = 0;
while (compare_bignum(&row,b) != PLUS) {
c->digits[i] ++;
subtract_bignum(&row,b,&tmp);
row = tmp;
}
}
zero_justify(c);
a->signbit = asign;
b->signbit = bsign;
}
22
For more information:

Donald E. Knuth: The Art of Computer
Programming, Volume 2.

Seminumerical Algorithms, Chapter 4

Arithmetic







Positional number systems
Floating point arithmetic
Multiple precision arithmetic
Radix conversion
Rational arithmetic
Polynomial arithmetic
Manipulation of power series
23
Practice I: Primary Arithmetic



http://acm.uva.es/p/v100/10035.html
Children are taught to add multi-digit numbers from right-toleft one digit at a time. Many find the "carry" operation - in
which a 1 is carried from one digit position to be added to
the next - to be a significant challenge. Your job is to count
the number of carry operations for each of a set of addition
problems so that educators may assess their difficulty.
Input


Each line of input contains two unsigned integers less than 10
digits. The last line of input contains 0 0.
Output

For each line of input except the last you should compute and
print the number of carry operations that would result from adding
the two numbers, in the format shown below.
24
Practice I: Primary Arithmetic
Sample Input
123 456
555 555
123 594
00
Sample Output
No carry operation.
3 carry operations.
1 carry operation.
Hint:
Use an array of characters to
store the digits of an integer
25
Practice II: Reverse and Add



http://acm.uva.es/p/v100/10018.html
The "reverse and add" method is simple: choose a number, reverse its
digits and add it to the original. If the sum is not a palindrome (which
means, it is not the same number from left to right and right to left),
repeat this procedure.
For example:
In this particular case the
195 Initial number
palindrome 9339 appeared after
591
----the 4th addition.
786
687
This method leads to palindromes
----in a few step for almost all of the
1473
integers. But there are interesting
3741
----exceptions. 196 is the first number
5214
for which no palindrome has been
4125
found. It is not proven though, that
----there is no such a palindrome.
9339 Resulting palindrome
26
Practice II: Reverse and Add

Task :
You must write a program that gives the resulting palindrome and the
number of iterations (additions) to compute the palindrome.

You might assume that all tests data on this problem:
- will have an answer ,
- will be computable with less than 1000 iterations (additions),
- will yield a palindrome that is not greater than 4,294,967,295.

The Input


The first line will have a number N with the number of test cases, the next N lines
will have a number P to compute its palindrome.
The Output

For each of the N tests you will have to write a line with the following data :
minimum number of iterations (additions) to get to the palindrome and the
resulting palindrome itself separated by one space.
27
Practice II: Reverse and Add

Sample Input
3
195
265
750

Sample Output
4 9339
5 45254
3 6666
28
Practice III: Archeologist’s
Dilemma





http://acm.uva.es/p/v7/701.html
An archeologist seeking proof of the presence of extraterrestrials in the
Earth's past, stumbles upon a partially destroyed wall containing strange
chains of numbers.
The left-hand part of these lines of digits is always intact, but unfortunately
the right-hand one is often lost by erosion of the stone. However, she
notices that all the numbers with all its digits intact are powers of 2, so that
the hypothesis that all of them are powers of 2 is obvious.
To reinforce her belief, she selects a list of numbers on which it is apparent
that the number of legible digits is strictly smaller than the number of lost
ones, and asks you to find the smallest power of 2 (if any) whose first digits
coincide with those of the list.
Thus you must write a program such that given an integer, it determines (if it
exists) the smallest exponent E such that the first digits of 2E coincide with
the integer (remember that more than half of the digits are missing).
29
Practice III: Archeologist’s
Dilemma

Input


It is a set of lines with a positive integer N not bigger than
2147483648 in each of them.
Output

For every one of these integers a line containing the
smallest positive integer E such that the first digits of 2E are
precisely the digits of N, or, if there is no one, the sentence
``no power of 2".
Sample Input:
Sample Output:
1
2
10
7
8
20
(2, 4, 8, 16, 32, 64, 128=27)
(2, 4, 8, 16, 32, 64, 128, 256=28)
(2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
8192, 16384, 32768, 65536, 131072, 262144,
524288, 1048576=220)
30
Analysis of the problem



The legible digits form a number N
Assume there are k missing digits
The we have the following inequalities:


We perform the lg() operation:



Nx10k <= 2E < (N+1)x10k
lg(Nx10k) <= lg(2E) < lg ((N+1)x10k), which leads to
lgN + klg10 <= E < lg(N+1) + klg10
We can search for the k such that, there is an
integer in the middle
31
Sample
Solution
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void process(int n)
{
int k, e;
double d1, d2, d3, d4;
double left, right;
d4 = log(2);
d3 = log(10) / d4;
d1 = log(n) / d4;
d2 = log(n+1) / d4;
void process(int);
int length(int);
k = length(n)+1;
left = d1+k*d3;
right = d2+k*d3;
e = (int)ceil(left);
while(e >= right)
{
k++;
left = d1+k*d3;
right = d2+k*d3;
e = (int)ceil(left);
}
printf("%d\n", e);
int main()
{
int in;
while( scanf("%u", &in) != EOF)
process(in);
return 0;
}
}
int length(int n)
{
int len = 0;
if(n < 10)
return 1;
while(n > 0)
{
n = n/10;
len++;
}
return len;
}
32
Practice IV: How Many Fibs?


http://acm.uva.es/p/v101/10183.html
Recall the definition of the Fibonacci
numbers:


f1 = 1, f2 = 2, fn = fn-1+fn-2 (n >= 3)
Given two numbers a and b, calculate how
many Fibonacci numbers are in the range
[a,b].
33
Practice IV: How Many Fibs?

Input Specification


The input contains several test cases. Each test
case consists of two non-negative integer
numbers a and b. Input is terminated by a=b=0.
Otherwise, a<=b<=10100. The numbers a and b
are given with no superfluous leading zeros.
Output Specification

For each test case output on a single line the
number of Fibonacci numbers fi with a<=fi<=b.
34
Practice IV: How Many Fibs?


Sample Input
10 100
1234567890 9876543210
00
Hint:
Sample Output
Use the bignum functions!
5
4
35
More practice on basic arithmetic





http://acm.uva.es/p/v8/847.html
http://acm.uva.es/p/v100/10077.html
http://acm.uva.es/p/v101/10105.html
http://acm.uva.es/p/v101/10127.html
http://acm.uva.es/p/v102/10202.html
36