Solved

# Big Integer

Posted on 2006-06-05
3,467 Views
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
Question by:hoomanv

LVL 14

Accepted Solution

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

LVL 14

Author Comment

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

LVL 14

Author Comment

BTW can you explain what is FFT ?
0

LVL 14

Expert Comment

0

LVL 14

Author Comment

many thanks to you :)
0

## Featured Post

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.