Arpa's blog

By Arpa, history, 9 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

| Write comment?
»
9 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.

»
9 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

  • »
    »
    9 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.

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

      This is called LCM though

    • »
      »
      »
      9 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

      • »
        »
        »
        »
        9 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.

        • »
          »
          »
          »
          »
          9 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).

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

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

      • »
        »
        »
        »
        9 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.

»
9 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

  • »
    »
    9 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

»
9 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

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

  • »
    »
    9 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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        7 years 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.

»
7 years 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()?

  • »
    »
    7 years 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.

»
7 years 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;
}
»
7 years 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

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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),

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

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

»
7 years 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?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to calculate 30! correctly?.... I failed to calculate 30! with unsigned long long int...

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

    Well, if you look up how big 30! is, and then compare it to the maximum value of unsigned long long, then you'll have your answer.

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

      The author compare unsigned long long int to BigInteger(java),one of the reader of the post say that he dont have to learn java for BigInteger only.My curious mind wants to know,Is unsigned long long int is comparable with BigInteger of java?

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

        I don't know much about Java, but my understanding is that Java has a builtin BigInteger implementation, while C++ does not.

        BigInt and unsigned long long aren't really the same. The purpose of BigInt is to hold arbitrarily large values, and do operations on them. Unsigned long long is a just primitive data type, like int or long long. Unsigned long long is the one that can hold the largest possible number. However it will still overflow once you get to a big enough number (in this case, 264).

        If you use BigInt, your calculations will be slower, but you can guarantee that you will never overflow. However I've never needed to use BigInt on Codeforces, so I don't think it's that common.

»
4 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Why should you put in the name of allah in a code ?

for fuck sake...

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

    I personally don't do that, but I don't see any problem with it. People have their beliefs, and you should respect them.

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

      Yeah, just like they slaughter humans in france.

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

        The actions of a few do not define everybody in a group.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -24 Vote: I do not like it

        So you believe that 1.8 billion allah devotee are slaughters. You seriously need to get checked.

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

          yep, if they have the chance and power to do so, they will do it. They believe they should be the one in power to express sharia law, only this law can solve all humanity problems.

          sharia law explicitly call muslims to kill all unbelievers.

          You can't ask someone sane to respect such idea, the idea is the problem not the humans. Maybe you should get checked too.

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

            Dear keyboard warrior, before you say something in future, please provide the source and the context of that source. Anything out of context will surely sound irrational. If you do not know the source and context, do not talk.

            This is not the place. If you want to learn, you have internet. If you want to rant, you have other dedicated social networks.

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

              Dear keyboard terrorist, why don't you try to write an argument to correct my view. You can view the horrifying verses in my edit history.

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

                Actually, they not. Everyone thinks like that because of some foolish people who think that killing people is commanded in Quran, but it was for the times that they were a war between Muslims and others, others were trying to kill Muslims where ever they see, Muslims weren't sure about killing them because their prophet didn't say anything about it and Quran says that human lives are important and be kind to unbelievers and teach them the ways of Quran. But the Quran said your lives are matter too, so you can kill them (for self-defense, in such case, it's not a crime for laws too). Also, other versicles have appeared in cases like that too, so please check the versicle's history and when they appeared before talking like that, it can be easily found on YouTube and other platforms by peoples who have searched and have more information about this. Also, there is no Sharia law to kill unbelievers, that's bullshit. (Another thing, not all Muslims live according to Sharia.)

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

                  why don't you try teaching that to a group of terrorist ? I know, because they will also defend their view because it's equally valid.

                  Your religion is strict but ambiguous, and there's no parser capable to read your holybook, that's why these kind of things happen.

                  Your god is weak, because he can't even make your book unambiguous, so maybe you all should stop putting his name in a piece of code.

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

                  I didn't say anything about my religion, or I didn't say anything about it's not ambiguous, I just said that you just writing things without searching, just with hearsay, so I wrote some information with proof that I know. And The thing about religions is everyone can have their own view, without that there will be no religion, there would be just some orders, commands, there wouldn't be any part of human will in this. (Also I don't write Allah in my codes, I think it's kinda weird too, but just because of that, you can't say something like all Muslims are murderers, they aren't like, "Hey bro, let's get out and kill some atheists, I need exp")

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

Hi, sorry for necroposting but the link for the source code is down. Can you fix it please?