### Arpa's blog

By Arpa, history, 4 years ago, ,

Hi!

One of the C++ programmers problems is to work with integers greater than 2^64-1 (we can save 0to 2^64-1 in unsigned long long int). So I want to share the best Bignum implementation I have ever seen (Link) with CodeForces Community.

Its specifications are as follows:

• Supported operations: + , -, / , * , % , ^(pow) , gcd , lcm , abs.

• It is able to work with Standard Input/Output streams.

• It can cast data to long long, string.

• It uses fast multiplication.

source.(but I have edited that and added pow and size().)

UPD1 (September 2016): Bug in void operator=(long long v) is now fixed. Thanks to AmSen.

• +13

 » 4 years ago, # |   +8 Thank you, Arpa. Now I don't need to switch to Java.
 » 4 years ago, # |   +21 It would be fair to include the original LinkAlso what's lcp? :D
•  » » 4 years ago, # ^ | ← Rev. 4 →   -8 I have added size() and pow() functions to that library.
•  » » » 4 years ago, # ^ |   +17 This is called LCM though
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +11 Added 17 most valuable lines of code and didn't even optimize if(b%2). OK.FYI:lcp = longest common prefixlcm = least common multiple
•  » » » » 4 years ago, # ^ |   +13 To be fair, b&1 is not faster than b%2. The compiler will produce the same machine code for both.
•  » » » » » 4 years ago, # ^ |   0 I meant different aspect of it. b is a bigint with base divisible by 2, so instead of using operator % one could simply write if (b.a[0] % 2) (at this point we know that vector isn't empty).
•  » » » 4 years ago, # ^ |   +54 You should at least mention the original author of the library.
•  » » » » 4 years ago, # ^ |   +13 Apparently, he doesn't have to. I agree that it would be good to do it, though. And maybe also make a pull-request to add those new size() and pow() functions to the original code.
 » 4 years ago, # |   -10 Thanks for this BigInt library. But I see Karatsiba multipluying in this library. Where is my Furje Multiply?And can u tell me pls about BigInteger Dividing, about algo of this
•  » » 4 years ago, # ^ |   +7 Fourier Multiply is o(N*log N), but the constant is fairly large so it's only worth for very very long numbers
 » 4 years ago, # |   +29 thanks for sharing!notice the following case bigint x = 0; x= -x; cout<< x <
 » 4 years ago, # | ← Rev. 2 →   -15 Unfortunately, there isn's standard library of Big Numbers in C++. And if you write important contest, that doesn't allow use extra materials (like your copybook or internet), this implementation won't help you. If only you memorize it, but you waste a lot of time writing this code.So, the best way still solve problems with big numbers on Java.
•  » » 4 years ago, # ^ |   0 the best way is save this code and paste it when you need
 » 3 years ago, # |   0 Arpa I can't find pow and size() in this bigint library.
•  » » 3 years ago, # ^ |   0 Link.
•  » » » 3 years ago, # ^ |   0 Thanks! another question. What does line 5 and line 6 do?
•  » » » » 3 years ago, # ^ |   0 This class keeps numbers in some big base (e.g. 109) to make operations faster.
 » 3 years ago, # |   0 Arpa How do I print the bigint number using printf()? I can print it using std::cout, but how to do it using printf()?
•  » » 3 years ago, # ^ |   0 Check how it's implemented to support istream and ostream (line 297 to line 311), you may know why it can't directly support printf.If for some reason, you need this library to output with printf, you can add a function to do that. e.g. add a function called print and let it print the number with printf.
 » 3 years ago, # |   +3 You implemented += via +. It is not optimal, doing the other way is much better. Consider the example: bigint large; // some large number for (int i = 0; i < 100000; ++i) { large += i; } Here large will be copied on each iteration, because += calls +. And if you implemented += inplace, this code would run in linear time. If you do it, + is implemented like friend bigint operator+(bigint lhs, const bigint& rhs) { return lhs += rhs; } 
 » 2 years ago, # |   +17 WRONG ANSWER on tests 21-40. Problem: https://www.e-olymp.com/ru/problems/317Input: 2 numbers A, B: 0 <= A, B <= 10^195000Output: A * B
•  » » 2 years ago, # ^ |   +8 I managed to fix his code. You can see my version here.I also did some optimization, including what ifsmirnov mentioned above.My version is not well tested yet, especially on negative numbers. Please let me know some problems on OJs which requires BigInt, so I can test it :D.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thanks! I fixed it too, but my version without karatsuba multiply (only with fast fourier transform), without sqrt, comments in english, and sign of number. Now I want to study and write a quick division in time O (n log(n)) with Newton–Raphson division in base 10^9 (or another power of 10),
•  » » » 6 months ago, # ^ |   -8 Why did you use karatsuba multiplication? Is there any drawback of fft_mul?
 » 2 years ago, # |   +5 Dear good brother, I have a question. Do Iranian coders indent their code right aligned?
•  » » 2 years ago, # ^ |   0 No.