hi

for all the people that are interested in computation with big numbers, here are some exercices (this is the first part of an exam problem in computer science for the Ecole Normales Sup?rieures) :

we consider we are working with integers that are B bits long (typically, B = 32). a word is therefore an integer that is 0 <= a < 2^B.
arithmetical operations on word (addition mod 2^B, subtraction mod 2^B, opposite mod 2^B, multiplication division (div) and rest (mod), mod 2^B) operate in constant time (O(1)). We also suppose that dynamical memory allocation functions operate in O(1).
We represent big numbers as arrays along with a bit sign, we suppose that B is even, B >= 4, the array is
a_0, ..., a_{k-1}, where a_i < 2^{B-2}, such that the absolute value of n is |n| = a_0 + a_1 * 2^{B-2} + ... + a_{k-1}*2^{(k-1)(B-2)}. The size of n is defined as k.

1. Show that we can compute the sum and difference of two big numbers of size <= k in time O(k)

2. Propose a constant time (O(1)) algorithm that inputs two words n_1 and n_2 such that 0 <= n_1, n_2 < 2^{B-2} and return their product as a list of two words a_1 and a_2 (so that n_1 * n_2 = a_1 + 2^{B-2}*a_2

3. Show that we can compute the product of two big numbers of size <= k in time O(k^alpha), where alpha is a constant < 2 that you'll determine. (use the remarkable identity (a*2^p + b)(c*2^p + d) = ac2^{2p} + ((a+b)(c+d) - ac - bd)*2^p + bd, and notice that the right side only contains 3 different products ac, bd, (a+b)(c+d).

4. We'll admit that we can also compute the quotient and the rest of the division of two big numbers of size <= k in O(k^alpha).
Show that we can compute the product mod p of two big numbers n_1, n_2 such that 0 <= n_1, n_2 < p, where p is of size <= k, in time O(k^alpha). (We ask the result to be between 0 inclusive and p exclusive).

5. Show that we can compute the sum and the difference of two big numbers mod p n_1, n_2 such that 0 <= n_1, n_2 < p in time O(k) (the result must be >= 0, < p, and notice that the time must be O(k), not O(k^alpha)).

6. We consider the function BEZOUT :


function BEZOUT (n, n')
if n' = 0 then return (n, 1, 0)
else (d, b, b') <- BEZOUT (n', n mod n')
a <- b'
a' <- b - b'*(n div n')
return (d, a, a')

Show that if n, n' are positive big numbers that aren't both null, and such that n >= n', BEZOUT (n,n') terminates and returns a 3-uple (d, a, a') such that an + a'n' = d, where d is gcd(n, n')

7. We'll admit that BEZOUT (n, n') terminate in time O(k^{1+alpha}). Propose an algorithm MDIV that inputs 3 big numbers n, n', p such that 0 <= n, n' < p, and n' is relatively prime to p, and outputs n/n' mod p, that is the only big integer m modulo p such thath n = n'm (mod p). The MDIV algorithm must terminate in time O(k^{1+alpha}), justify.
Posted on 2003-03-15 13:03:38 by roy
hi

so noone is posting solutions ?
try a bit =)
for instance, for the 1., a possible solution is two make two procs add_abs, sub_abs , that adds or subs the absolute values of the numbers, make a abs_comp proc that compares the absolute values of the numbers (whether |n_1| > , =, < |n_2|) and two procs add and sub that check bitsign, compare numbers if needed, and operate.

I guess the whole exam was either a 4 hours or 6 hours one, but wasn't meant to be possible to finish, so i guess the first part that i gave should take maybe around 2 hours or a bit more to make (all the algorithms must have their proof of termination and correction).
Posted on 2003-03-18 12:11:20 by roy