# Multi-Precision Arithmetic

CS 301 Lecture, Dr. Lawlor

Reminder:

CF--The
"carry flag". Set to
indicate the bit that carries out of an addition or subtraction.
For signed numbers, this doesn't really indicate a problem, but for
unsigned numbers, this carry indicates an overflow.
Can be used by the "jc" (jump if carry flag is set) instruction.
Set by all the arithmetic instructions.
Can be added into another arithmetic operation with "adc" (add with
carry), which computes:

output register = output register + input register + CF

new CF = carry out of the above addition ^ ^ ^

For example, you can preserve the bit overflowing out of
a big add (between ecx and ecx) like this:

mov ecx, 0x8000ff00

add ecx, ecx

mov eax,0

adc eax,eax ; Adds eax, eax, and the carry flag together

"adc" is used in the compiler's implementation of the 64-bit "long
long" datatype on 32-bit machines, as we describe below.

## Multi-Precision Arithmetic

You can do register-register addition in a single instruction
(add). But if you want to add numbers bigger than the registers,
you need to break up the addition into register-sized pieces, ordered
from lowest value to highest. You'd also have to make sure the
carry bits will actually pass between the pieces. To add a two-int multiprecision number, then, you'd

add loA,loB

adc hiA,hiB

This way, the carry bit coming out of the low addition would be read by the higher addition.

To do this "for real", there are several excellent libraries, such as GMP.

## Fast Exponentiation Trick

Say you want to compute x to the power y. This is just x*x*x*...*x, with a total of y copies of x:

The obvious way to do this is really quite slow for big values of y:

int prod=1;

for (int i=1;i<=y;i++) prod*=x;

return prod;

But it's *exponentially* faster to compute x raised to the powers of two by
repeated squaring, then combine those powers of two to get x to the
y. For example, you can compute x to the 16th by squaring x four
times, like so:

int x2=x*x;

int x4=x2*x2;

int x8=x4*x4;

int x16=x8*x8;

Harkening back to our bitwise operators, we can just decompose y into
the corresponding powers-of-two of x, by looking at the bits of y:

/* Return x raised to the power y */

double mypow(double x,int y)

{

double prod=1; /* will hold x to the y power */

double xpow=x; /* will take powers of x */

for (unsigned int bit=0;bit<sizeof(int)*8;bit++) {

int mask=(1<<bit);

if (y&mask) prod=prod*xpow; /* include this power of x */

if (y<mask) break; /* no higher powers of x included in y */

xpow=xpow*xpow; /* find next higher square */

}

return prod;

}

(Try this in NetRun now!)

For example, raising 2 to the 100th power takes only 8 iterations with
this "fast exponentiation" method, but over 100 iterations with slow
exponentiation.

The fast exponentiation trick applies to all sorts of stuff--and there's an exact analog for multiplication!