Hi!

One of the C++ programmers problems is to work with integers greater than `2^64-1`

(we can save `0`

to `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.

Thank you, Arpa. Now I don't need to switch to Java.

It would be fair to include the original Link

Also what's lcp? :D

I have added

`size()`

and`pow()`

functions to that library.This is called LCM though

Added 17 most valuable lines of code and didn't even optimize

`if(b%2)`

. OK.FYI:

lcp = longest common prefix

lcm = least common multiple

To be fair,

`b&1`

is not faster than`b%2`

. The compiler will produce the same machine code for both.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).You should at least mention the original author of the library.

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.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

Fourier Multiply is o(N*log N), but the constant is fairly large so it's only worth for very very long numbers

thanks for sharing!

notice the following case

this will print -0

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.

the best way is save this code and paste it when you need

Arpa I can't find pow and size() in this bigint library.

Link.

Thanks! another question. What does line 5 and line 6 do?

This class keeps numbers in some big base (e.g. 10

^{9}) to make operations faster.Arpa How do I print the bigint number using printf()? I can print it using std::cout, but how to do it using printf()?

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.

You implemented

`+=`

via`+`

. It is not optimal, doing the other way is much better. Consider the example: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 likeWRONG ANSWER on tests 21-40. Problem: https://www.e-olymp.com/ru/problems/317

Input: 2 numbers A, B: 0 <= A, B <= 10^195000

Output: A * B

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.

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),

Why did you use karatsuba multiplication? Is there any drawback of fft_mul?

Dear good brother, I have a question. Do Iranian coders indent their code right aligned?

No.