Naim_Hasan's blog

By Naim_Hasan, 4 weeks ago, In English,

At first thanks to Arpa who has written a very clean and fast library for handling big size number in C++. With it, i added sqrt and pow function. Also overloaded post++, post-- operator. And instead of writing "bigint", we wrote "Int" so that it become easy to write and understand.

The modified code now can handle all these operation given below:

+, -, *, /, %, =, >, < ; +=, -=, *=, /=, %=, ==, !=, >=, <= ; ++pre, post++, --pre, post-- ; pow(a,b), sqrt(a), max(a,b), min(a,b) ; [ Here a is Int type and b is Int or other integer type ]

Here is the latest code.

https://github.com/NaimHasanPappu/Algorithm/blob/master/BigInteger.cpp

To check if the library is working smoothly, try This Problem

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

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Using this base 1e9 stuff is a waste of memory, just use the actual bits of each integer instead.

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

    storing the bigint in binary does not safe much space at all but makes in and output significantly slower and harder to write. For competive programming i would always use a multiple of ten as base.

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

      Just convert back to base 10 when printing out. Right now his implementation is taking 4 times more memory than it needs.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        writing a fast base conversion is quite complicated, and you probably need to implement a division to do it (and you can not just divide by 10 multiple times...). But i have never seen a problem where i need to save so much space (sometimes i even use a long long to store 6 digits, to make multiplications and other stuff more simple). However i know many problems where i dont even need a division on big integers and it would be just a waste of time to implement it just for a base conversion...

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

          You are allowed to copy paste libraries, you know? No time at all would be wasted. And as for “I don’t need to have good memory use” attitude — well, I don’t need big integer either, but it’s always nice to have it.

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

            there are contest where you are not allowed to copy paste libraries, you know? Also it is faster and simpler not to change the base. The only reasons to use base two would be if you need binary operations or the number is already given in base two

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

      I'd say it's not the space that matters, but that arithmetic modulo 10^9 is much slower than arithmetic modulo 2^32..

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

        this is true but in my tests the impact of conversion was much bigger (in the time you need to do a single base conversion for numbers like $10^{10^{100000}}$you can do millions of modulo operations).

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

Thank you for sharing Big Integer Library. This code will be in High demand.Finally, no more need to code in java or python.

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

    no more need to code in java or python.

    That's a pretty naive thing to say. Python and Java have other useful features besides just arbitrary arithmetic precision. E.g. You will never get the same memory safety checks in C++ compared to Python and Java. Also, there's no way C++ can beat python when it comes to ease of creating a program (ignoring runtime).

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

      Actually, I use Python just in case where we have to deal with big integers.

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

Just a suggestion: I think using Github would be better.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Why did you use linear exponentiation instead of binary exponentiation? Linear will time out really fast with bigints.

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

    Yeah, after you said that I looked and its linear. Then I checked my favorite number theory library code, and for some reason they are using linear exponentiation as well for regular powers. But my favorite number theory library uses binary exponentiation for PowerMod. I'm at a loss as to why they don't do it for regular powers. They obviously know binary exponentiation method as shown in their PowerMod function, but choose linear exponentiation when its just regular exponentiation. There must be something I'm failing to understand as to why. Maybe I'll ask them and see if they respond.

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

I was curious because I was recently looking for a single file struct for BigInt in C++ but couldn't find anything, all I found was always huge libraries that link to GMP or other libraries, or if are self contained have many header files.

I just tested this out of curiosity, its about 5 to 10x slower than Victor Shoup's Number Theory Library on multiplication. https://www.shoup.net/ntl/ Which actually isn't that bad, he is a professor of number theory and has spent years optimizing his library. I'm pretty sure I compiled NTL without GMP which would make it faster but what we are looking for is something that doesn't link to external libraries.

And I only tested multiplication, I'll test the operations when I get a chance. But this interests me, I always wondered why C++ never included basic multiprecision support, at least a BigInt class.

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

How is the name 'Int' more understandable than 'BigInt' ???