Naim_Hasan's blog

By Naim_Hasan, 4 months ago, ,

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

• +65

 » 4 months ago, # |   +5 Using this base 1e9 stuff is a waste of memory, just use the actual bits of each integer instead.
•  » » 4 months ago, # ^ |   +6 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 months ago, # ^ |   0 Just convert back to base 10 when printing out. Right now his implementation is taking 4 times more memory than it needs.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +8 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 months ago, # ^ |   0 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 months ago, # ^ |   0 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 months ago, # ^ |   0 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 months ago, # ^ |   0 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 months ago, # |   0 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 months ago, # ^ | ← Rev. 3 →   0 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 months ago, # ^ |   +3 Actually, I use Python just in case where we have to deal with big integers.
 » 4 months ago, # |   0 Just a suggestion: I think using Github would be better.
•  » » 4 months ago, # ^ |   0 But i am not much familiar with github.
•  » » 4 months ago, # ^ |   0 Added github link :)
 » 4 months ago, # |   +6 Why did you use linear exponentiation instead of binary exponentiation? Linear will time out really fast with bigints.
•  » » 4 months ago, # ^ |   0 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 months ago, # |   0 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 months ago, # |   0 How is the name 'Int' more understandable than 'BigInt' ???
•  » » 4 months ago, # ^ |   0 easier to type i think