Arpa's blog

By Arpa, history, 3 years ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +13
  • Vote: I do not like it  

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It would be fair to include the original Link

Also what's lcp? :D

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it -8 Vote: I do not like it

    I have added size() and pow() functions to that library.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      This is called LCM though

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        To be fair, b&1 is not faster than b%2. The compiler will produce the same machine code for both.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +54 Vote: I do not like it

      You should at least mention the original author of the library.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

thanks for sharing!

notice the following case

bigint x = 0;
x= -x;
cout<< x <<endl;

this will print -0

»
3 years ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This class keeps numbers in some big base (e.g. 109) to make operations faster.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Arpa How do I print the bigint number using printf()? I can print it using std::cout, but how to do it using printf()?

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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;
}
»
10 months ago, # |
  Vote: I like it +17 Vote: I do not like it

WRONG 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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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