• Status: Solved
• Priority: Medium
• Security: Public
• Views: 3478

# Big Integer

Hi
I need a very fast bigint support in C/C++
currently im using this library: http://sourceforge.net/projects/cpp-bigint/
I tested it to calculate factorial(3000) and after about 9 sec it finished
Im wondering that Java's BigInteger computes fact(3000) in less than a sec

the algoritms that im using are as follow

C++
RossiBigInt i(1);
int fact = atoi(argv[1]);
for(int k = 2; k <= fact; k++)
i = i * k;
cout << i << endl;

Java
BigInteger i = BigInteger.ONE;
BigInteger k = BigInteger.ONE;
int fact = Integer.parseInt(args[0]);
for(int j = 1; j < fact; j++) {
i = i.multiply(k);
}
System.out.println(i);

I also tested the java version with another library from http://swiss.csail.mit.edu/~adams/BigInt/class_BigInt.html
that has been written purely in java (unlike BigInteger which its methods are mostly native)
and surprisingly it gave me the result as soon as BigInteger did
therefore it brings in mind that the algorithm used in C++ bigint is not efficient
can anyone suggest a fast C/C++ library for bigint calculations ?
0
hoomanv
• 3
• 2
1 Solution

Commented:
I have not tried it, but I think gmp (http://swox.com/gmp/) is better. It uses fft multiplication, which is much faster for large numbers.

the demo calculates 3000! in less than 1 ms: http://swox.com/cgi-bin/gmp_calc.pl?expr=3000%21
0

Author Commented:
wow it claims to be the fastest bignum library on the planet
0

Author Commented:
BTW can you explain what is FFT ?
0

Author Commented:
many thanks to you :)
0

## Featured Post

• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.