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

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++) {
            k = k.add(BigInteger.ONE);
            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
Asked:
hoomanv
  • 3
  • 2
1 Solution
 
cwwkieCommented:
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
 
hoomanvAuthor Commented:
wow it claims to be the fastest bignum library on the planet
0
 
hoomanvAuthor Commented:
BTW can you explain what is FFT ?
0
 
hoomanvAuthor Commented:
many thanks to you :)
0

Featured Post

SMB Security Just Got a Layer Stronger

WatchGuard acquires Percipient Networks to extend protection to the DNS layer, further increasing the value of Total Security Suite.  Learn more about what this means for you and how you can improve your security with WatchGuard today!

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