Description
1 Multiplication of large positive integers
The multiplication of two n-digit numbers by the usual long multiplication algorithm (column-wise) that is
taught in schools takes about O(n
2
) single-digit multiplications.
According to the Wikipedia, Karatsuba’s algorithm (discovered by Anatoly Karatsuba in 1960) reduces the
complexity of multiplication of two n-digit numbers to at most n
lg23
single-digit multiplications.
2 Karatsuba’s algorithm
Given two n-digit (for large n) positive integers x and y in a base B > 1. For m = dn/2e = b(n + 1)/2c we have
x = x1Bm + x0, for some x0, x1 < Bm
y = y1Bm + y0, for some y0, y1 < Bm
x.y = x1y1B2m + (x1y0 + x0y1)Bm + x0y0, for some y0, y1 < Bm
Let
z2 = x1y1 < B2m
z1 = x1y0 + x0y1 < 2B2m
z0 = x0y0 < B2m Hence xy = z2B 2m + z1B m + z0 (1) would require 4 multiplications of m-digit numbers of which z1 requires two multiplication operations. Hence for any k > 0, such that 2k−1 < n ≤ 2
k
, the computation of xy would require O(n
2
) multiplications.
Now consider
(x1 + x0).(y1 + y0)
= z2 + z1 + z0
It is possible that the computation of z1 may result in an overflow.
z1 = (x1 + x0).(y1 + y0) − z2 − z0
= (x1 + x0).(y1 + y0) − x1y1 − x0y0
= (x1y1 + x1y0 + x0y1 + x0y0 − x1y1 − x0y0
= (−x1y1 + x1y0 + x0y1 − x0y0) + x1y1 + x0y0
= −(x1y1 − x1y0 − x0y1 + x0y0) + x1y1 + x0y0
= −(x1 − x0)(y1 − y0) + x1y1 + x0y0
= (x0 − x1)(y1 − y0) + x1y1 + x0y0
= sgn(x0 − x1).sgn(y1 − y0).|x0 − x1|.|y1 − y0| + x1y1 + x0y0
where sgn(x) denotes the sign of x. Now the computation of z1 requires only one multiplication operation though
we may have to deal with negative numbers because of the subtraction operations. The numbers (x0 − x1) and
(y1 − y0) lie in the interval [−Bm, Bm]. However since |x0 − x1| ≤ max(x1, x0) and |y1 − y0| ≤ max(y1, y0) By
separating out the signs and doing an absolute value multiplication, we are guaranteed that |x0 −x1|.|y1 −y0| ≤
max(x1, x0)×max(y0, y1) will not overflow if none of the other products computed in z2 and z0 do not overflow.
Problem Statement
Your task is to implement a function to compute factorial of large numbers using Karatsuba’s multiplication
algorithm in Standard ML or OCaml.
What you have to do
1. Decide whether to program in Standard ML or OCaml and choose the appropriate instruction from each
of the following steps.
2. Create a file .ml if you choose to use OCaml or .sml if you choose
Standard ML.
3. Note that the input numbers to your program might be larger than Int.maxInt (in case of sml) or max int
(in case of OCaml).
4. You are NOT allowed to use existing libraries and structures (such as IntInf or Big int) for arbitrarily
large integers.
5. Your submission should contain two methods – karatsuba (implements Karatsuba’s multiplication) and
factorial (computes factorial using Karatsuba’s method wherever multiplication is required). We might
evaluate both of these methods separately.
6. The input and output numbers to these functions are strings of digits.
7. Define functions fromString : string -> int list and toString: int list -> string for purposes of input and output respectively.
8. You have to manipulate the numbers as lists of digits in base B = 109
(for OCaml) and B = 104
(for
Standard ML).
9. The Karatsuba multiplication function takes two numbers as input and returns the result of multiplication.
The function to compute Karatsuba multiplication should have signature val karatsuba: int list ->
int list -> int list.
10. The factorial function takes one non-negative integer and returns it’s factorial. The function should have
signature val factorial: string -> string.
11. If the input string is not a valid number, or the input to factorial is negative your program should raise
an exception of type exception Invalid Input exception of string
Submission Instruction
Submit an Ocaml file .ml or a Standard ML file .sml on Moodle (https://moodle.iitd.ac.in).
Important Notes
1. Do not change any of the names given in the signature. You are not even allowed to change upper-case
letters to lower-case letters or vice-versa.
2. You may define any new functions you like besides those mentioned in the signature.
3. Do not use libraries for arbitrary precision arithmetic.
4. Follow the input output specification as given. We will be using automated script for evaluation. In case
of mismatch, you might be awarded zero marks.
5. Since the evaluator is going to look at your source code before evaluating it, you must explain your
algorithms in the form of ML comments, so that the evaluator can understand what you have implemented.
