/** An instance wraps an integer (of any size) */
public class BigInt {
/** The base in which big integers (BigInts) are maintained.
1 less BASE less= Short.MAX_VALUE.
*/
public static final int BASE= 2;
private static final Integer int0= new Integer(0);
/* An integer is maintained in base BASE in field bigint; its sign
is in variable sign. The elements in bigint are always of
class Integer. An unsigned integer
i = bk*BASE^k + ... + b2*BASE^2 + b1*BASE^1 + b0*BASE^0
is maintained as the list (b0, b1, b2, ..., bk), so that the
low-order digit is first and the high-order digit is last.
This makes manipulating integers (e.g. adding) easier.
The integer 0 is represented by bigint = (0) and
sign being true.
If the integer is not 0, the high order digit is nonzero.
Note: in one or two places, integers are kept in another base.
This will be explained at the right time.
*/
public List bigint; // The unsigned integer --see above
public boolean sign; // The sign of the integer
/** Constructor: the integer 0 */
public BigInt() {
bigint= new List(int0,null);
sign= true;
}
/** Constructor: an instance that represents i */
public BigInt(long i) {
sign= i>=0;
bigint= encode(Math.abs(i), BASE);
}
/** Constructor: an instance that represents i, but in base base */
public BigInt(long i, int base) {
sign= i>=0;
bigint= encode(Math.abs(i), base);
}
/** = the List that represents i in base base.
Precondition: i >= 0
*/
private static List encode(long i, int base) {
if (i == 0)
{ return new List(int0,null); }
// {i > 0}
List res= null; // Will contain the final List
long n= i;
List p= null;
// inv: p is the name of the last node in list res (null if res is null)
// The representation of i in base base is given by
// res followed by the representation of n
while (n > 0) {
Integer nextDigit= new Integer((int)(n % base));
if (p == null) {
res= new List(nextDigit, null);
p= res;
}
else {p.next= new List(nextDigit,null);
p= p.next;
}
n= n/base;
}
return res;
}
/** = the number of digits this integer requires in base BASE */
public int numberDigits() {
return List.length(this.bigint);
}
/** = "this BigInt is less than b". Precondition: b != null */
public boolean less(BigInt b) {
if (this.sign != b.sign)
{ return b.sign; }
return this.sign ? less(this.bigint, b.bigint) : less(b.bigint, this.bigint);
}
// = the value in the first node of List p, which must be of class Integer
public static int getVal(List p) {
return ((Integer)List.first(p)).intValue();
}
// = "unsigned integer b1 is less than unsigned integer b2"
// Precondition: b1 and b2 are nonnull
private static boolean less(List b1, List b2) {
List p1= b1;
List p2= b2;
int d= 0;
//inv: p1 is a node of b1 (or null when done) and
// p2 is the corresponding node of b2 (or null when done) and
// d = -1, 0, or 1 depending on whether the value before
// p1 is less, equal, or greater than the value before p2
while (p1 != null && p2 != null) {
int i1= getVal(p1);
int i2= getVal(p2);
if (i1 < i2)
{ d= -1; }
else if (i1 > i2)
{ d= 1; }
p1= p1.next; p2= p2.next;
}
// {the end of at least one list has been fully processed}
if (p1 == null && p2 == null)
{ return d < 0; }
// {one list was not fully processed. That list represents
// the larger of the two lists}
return p1 == null;
}
/** = - this */
public BigInt negate() {
if (isZero(this))
{ return this; }
// Create folder bi to contain result; and fill in bigint and sign
BigInt bi= new BigInt();
bi.bigint= this.bigint;
bi.sign= !this.sign;
return bi;
}
/** = this - b. Precondition: b is not null */
public BigInt subtract(BigInt b) {
return this.add(b.negate());
}
/** = the unsigned integer that is b1 - b2.
Precondition: b1 and b2 are not null and b1 > b2 */
private static List subtract(List b1, List b2) {
List p1= b1;
List p2= b2;
int i1= getVal(p1);
int i2= getVal(p2);
int sum= i1-i2;
int carry= 0;
if (sum < 0)
{ carry= -1; sum= sum+BASE; }
List res= new List(new Integer(sum), null);
List p3= res;
//inv: p1 is a node of b1 and
// p2 is the corresponding node of b2 and
// p3 is the last node of res and
// res is the sum of lists b1 and b2 up to and counting nodes
// p1 and p2
// carry is the carry
while (p1.next != null || p2.next != null) {
sum= carry;
if (p1.next != null) {
p1= p1.next;
sum= sum + getVal(p1);
}
if (p2.next != null) {
p2= p2.next;
sum= sum - getVal(p2);
}
if (sum < 0)
{ carry= -1; sum= sum+BASE; }
else { carry= 0; }
p3.next= new List(new Integer(sum),null);
p3= p3.next;
}
// {carry is 0 because b1 <= b2}
return removeleadzeros(res);
}
/** = this + b. Precondition: b is not null */
public BigInt add(BigInt b) {
BigInt res= new BigInt(); // will contain the result
if (this.sign == b.sign) {
res.sign= this.sign;
res.bigint= add(this.bigint, b.bigint);
return res;
}
// {this and b have different signs, so a subtraction has to be done}
if (less(this.bigint, b.bigint)) {
res.sign= b.sign;
res.bigint= subtract(b.bigint, this.bigint);
return res;
}
// {this and b have different signs and b's bigint is smaller
res.sign= this.sign;
res.bigint= subtract(this.bigint, b.bigint);
return res;
}
/** = the unsigned integer that is b1 + b2.
Precondition: b1 and b2 are not null */
private static List add(List b1, List b2) {
List p1= b1;
List p2= b2;
List res= null;
List p3= res;
int carry= 0;
//inv: p1 is a node of b1 (or null when done) and
// p2 is the corresponding node of b2 (or null when done) and
// p3 is the last node of res (or null if res is null) and
// res is the sum of lists b1 and b2 up to but not including nodes p1 and p2
// and carry is the carry
while (p1 != null || p2 != null) {
int sum= carry;
if (p1 != null) {
sum= sum + getVal(p1);
p1= p1.next;
}
if (p2 != null) {
sum= sum + getVal(p2);
p2= p2.next;
}
if (res == null) {
res= new List(new Integer(sum%BASE),null);
p3= res;
}
else {
p3.next= new List(new Integer(sum%BASE),null);
p3= p3.next;
}
carry= sum/BASE;
}
// Add in final carry, if it is not 0
if (carry > 0) {
p3.next= new List(new Integer(carry), null);
}
return res;
}
/** = b * x. Precondition: 0 at most x less BASE. */
private static BigInt mult(BigInt b, int x) {
if (x == 0 || isZero(b))
{ return new BigInt(); }
BigInt res= new BigInt(); // res will contain the result
res.sign= b.sign;
// Perform a conventional multiplication of b and x; stor result in res
List p= b.bigint;
int i= ((Integer)p.element).intValue()*x;
res.bigint= new List(new Integer(i%BASE), null);
List q= res.bigint;
int carry= i/BASE;
//inv: p is a node of b.bigint and
// q is the last node of res.bigint and
// res is the product of lists b.bigint and x up to and
// counting node p and
// carry is the carry
while (p.next != null) {
p= p.next;
i= getVal(p)*x + carry;
q.next= new List(new Integer(i%BASE),null);
q= q.next;
carry= i/BASE;
}
if (carry > 0)
{ q.next= new List(new Integer(carry),null); }
return res;
}
// = b*BASE^c. Precondition: c >= 0, b is a list like a bigint field
private static List multBASE(List b, int c) {
Integer k= int0;
if (b.next==null && getVal(b)==0)
{ return b; }
List p= null;
while (c != 0) {
p= List.prepend(k,p);
c= c-1;
}
return List.append(p,b);
}
/** = this * b. Precondition: b is not null */
public BigInt mult(BigInt b) {
if (isZero(this))
{ return this; }
if (isZero(b))
{ return b; }
// {neither this nor b is 0}
List p= b.bigint;
int c= 0;
BigInt ans= new BigInt(); // ans will contain the result
// Copy folder this into a new folder thisCopy and make
// sign of the copy true
BigInt thisCopy= new BigInt();
thisCopy.sign= true;
thisCopy.bigint= this.bigint;
// inv: p is a node of b.bigint (null if at all done)
// c is the number of this node in b (the first is number 0)
// ans is the product of thisCopy and the first c nodes of b
while (p != null) {
BigInt temp= mult(thisCopy, getVal(p));
temp.bigint= multBASE(temp.bigint,c);
ans= ans.add(temp);
p= p.next;
c= c+1;
}
// Fix the sign of the result
ans.sign= this.sign == b.sign;
return ans;
}
// = "b is 0"
private static boolean isZero(BigInt b) {
return b.bigint.next==null && getVal(b.bigint)==0;
}
// = b with leading zeros removed. Since b represents an unsigned integer with
// the low order digit first, by leading zeros we mean the ones at the end, not at
// the beginning.
// This method may change list b and return it!!
// (it's the only method that does so)
public static List removeleadzeros(List b) {
List p= b;
List q= null;
// Store in q the name of the highest-order nonzero (null if none)
// inv: p is a node of list b (null if whole list has been processed)
// and q is name of highest-order nonzero node that occurs before p
while (p != null) {
if (getVal(p) != 0)
{ q= p; }
p= p.next;
}
if (q == null)
return new List(int0,null);
q.next= null;
return b;
}
/** = "this BigInt equals b". Precondition: b != null */
public boolean equals(BigInt b) {
return this.sign == b.sign && List.equals(this.bigint,b.bigint);
}
// digits[i] is the conventional String character that is used to represent
// integer i in any base that is at most 16.
private static final String[] digits= {"0", "1", "2", "3", "4", "5",
"6", "7", "8", "9", "A", "B",
"C", "D", "E", "F"};
/** = this BigInt, written in base BASE, with the high-order digit first.<br>
If BASE at most 16, it is given in conventional form. <br>
If BASE greater 16, it is given with commas between the digits
and is delimited by ( and )
*/
public String toStringBASE() {
// In creating the decimal representation of this integer, the high-order
// digit has to be first. So store the reverse of this's
// unsigned integer in b
List b= List.reverse(bigint); // unsigned int with high-order digit first
String s= sign ? "" : "-"; // sign of this integer
if (BASE > 16) {
return s + List.toString(b);
}
// Construct the representation of the integer in s
while (b != null) {
int d= getVal(b);
s= s + digits[d];
b= b.next;
}
return s;
}
/** Store in q the quotient when b is divided by y
and return the remainder. Quotient q will be in base base<br><br>
Precondition (0): b is in base base (not necessarily BASE).<br>
Precondition (1): 0 less y less base.<br>
Precondition (2): this > 0.<br>
Precondition (3): q is nonull and different this and y.
*/
private static int division(BigInt b, int y, BigInt q, int base) {
q.sign= true;
int r= divisionSimple(b,y,q,base);
if (0 <= r) {
return r;
}
// {1 < b < this}
// Put the digits of this in array dig, with high-order bit first
int n= List.length(b.bigint);
int dig[]= new int[n];
List p= b.bigint;
for (int i= 0; i != n; i= i+1) {
dig[n-1-i]= getVal(p);
p= p.next;
}
// Divide integer in dig by y, putting quotient in qa in r
// Remember that 1 < b < this.
int[] qa= new int[dig.length];
qa[0]= dig[0]/y;
r= dig[0]%y;
// inv: 0 <= i <= dig.length and
// qn[0..i-1] and r contain the quotient and remainder
// of dividing dig[0..i-1] by y
for (int i= 1; i != dig.length; i++) {
int temp= r*base + dig[i];
qa[i]= temp/y;
r= temp%y;
}
// Put the digits of qa into q.bigint. The first digit may be 0
q.bigint= null;
if (qa[0] != 0)
{ q.bigint= List.prepend(new Integer(qa[0]), q.bigint); }
for (int j= 1; j != qa.length; j++)
{ q.bigint= List.prepend(new Integer(qa[j]), q.bigint); }
return r;
}
/** Store in q the quotient when this is divided by y
and return the remainder.<br><br>
Precondition (1): 0 less y less BASE.<br>
Precondition (2): this > 0<br>
Precondition (3): q is nonnull and different this and y.
*/
public int division(int y, BigInt q) {
return division(this, y, q, BASE);
}
/** if 0 at most b at most y or y=1, store in q the quotient of b divided by y
and return the remainder. q will be in base b.
in all other cases, return -1.<br><br>
Precondition (0): b is in base base (not necessarily base BASE)<br>
Precondition (1): 0 less y less base --this is a big restriction.<br>
Precondition (2): this >= 0 --this is also a big restriction<br>
Precondition (2): q is nonull and different this and b.
*/
private static int divisionSimple(BigInt b, int y, BigInt q, int base) {
q.sign= true;
BigInt by= new BigInt(y, base);
if (b.less(by)) {
q.bigint= new List(int0, null);
return getVal(b.bigint);
}
if (b.equals(by)) {
q.bigint= new List(new Integer(1), null);
return 0;
}
if (by.equals(new BigInt(1, base))) {
q.bigint= b.bigint;
return 0;
}
return -1;
}
/** = a List with same value as b (which is in base BASE) but its base is BASE^4.
Precondition: 0 less BASE less 10 */
private static List base4(List b) {
List l= new List(b.element,null);
List pb= b;
List pl= l;
int i= 0; // 0 <= i < 4
int basei= 1;
// inv: pb is a node of b, and
// pl is the last node of l, and
// l, in base BASE^4, has the same value as b through pb, in base BASE, and
// i = (number of nodes of b before node pb) % 4
// basei= BASE^((i-1)%4)
while (pb.next != null) {
pb= pb.next;
int ib= getVal(pb);
i= (i+1)%4;
if (i == 0) {
pl.next= new List(new Integer(0),null);
pl= pl.next;
basei= 1;
}
else
{ basei= basei*BASE; };
int il= getVal(pl);
il= il + ib*basei;
pl.element= new Integer(il);
}
return l;
}
/** = this integer as a String (in decimal)
*/
public String toString() {
BigInt x= new BigInt();
x.sign= true;
x.bigint= this.bigint;
int base= BASE;
// The algorithm will perform successive divisions by 10 on
// x. This will work only if the base in which x is stored is
// at least 10. Therefore if BASE is in 2..9, change x to
// contain the same number in base BASE^4 (and change base
// accordingly)
if (BASE < 10) {
x.bigint= base4(x.bigint);
base= base*base*base*base;
}
String s= "";
// inv: the representation of abs(this) is s followed by (representation of x)
while (!isZero(x)) {
BigInt q= new BigInt();
int r= x.division(x, 10, q, base);
s= r + s;
x= q;
}
if (s.equals(""))
s="0";
// remove leading 0's
while (s.length() > 1 && s.charAt(0) =='0')
s= s.substring(1);
if (!this.sign)
{ s= "-" + s; }
return s;
}
// = factorial n (for 0 <= n)
// 21 is the smallest natural number n for which fact(n) is not
// a long. It takes 5, 20, and 66 digits to represent fact(21)
// in base Short.MAX_VALUE, 20, and 2, respectively.
public static BigInt fact(int n) {
if (n <= 1)
return new BigInt(1);
BigInt x= new BigInt(2);
int i= 2;
// invariant: 2 <= i <= n and x = factorial i
while (i != n) {
i= i+1;
x= x.mult(new BigInt(i));
}
return x;
}
// = Fibonacci number n (for n>= 0).
// Note: Fib(0) = 0, Fib(1) = 1, Fib(n) = Fib(n-1) + Fib(n-1) for n>=2
// fib(200) = 280571172992510140037611932413038677189525
// It has 10 digits in base 32767
public static BigInt Fib(int n) {
if (n<=1)
return new BigInt(n);
BigInt b= new BigInt(0);
BigInt c= new BigInt(1);
int k= 1;
//inv: 1 <= k <= n and c = Fib(k) and b = Fib(k-1)
while (k != n) {
BigInt temp= c.add(b);
b= c;
c= temp;
k= k+1;
}
return c;
}
}