Fype's blog

Bigint(Bignumber) Struct
By Fype, 5 years ago, In English

Here is my bigint struct in c++.

https://paste.ubuntu.com/p/Kb2Cwtk6Bg/ (new link is available)

enjoy it :))

upd1 : I added bitwise operator and shift. here is new link.

https://paste.ubuntu.com/p/FdxZ3QMG9h/

upd2 : I added popcount, ctz and tutorial to how to use change base function :D.

you can use the new code below :

https://paste.ubuntu.com/p/ZcMgDhvRhv/

upd3 : I fixed a bug found by WhaleVomit (thanks for noticing). This new code uses more memory. If you wanted to reduce the memory usage, you can use the previous version and you can use .normalize() function on each variable before each operation. It helps a little and the normalize function is of $$$O(n)$$$ where $$$n$$$ is the number of digits of the number you are using normalize on.

you can use the new code below :

https://paste.ubuntu.com/p/dzDJHqp5bf/

https://github.com/AriaAshrafi/BigInt/blob/main/BigInt.cpp

(any suggestion please comment)

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

Comments Comments (24)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Thanks, Very useful. How to use it?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

copy and paste it above your code and then use it like int. (like: bigint a;)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the maximum we can use for constant Dig?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Don't change Dig. :D I'm still not sure it is okay to change it. I wanted to change base easily with just changing Dig but something went wrong so it's just a constant that is 10. :D (change base is available from base (2 to 10) to base (2 to 10) with function CB(). Exmp: CB(A, 9, 3) will return A in Base(3) (A should be in base 9)).

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

      The way the numbers are stored is highly inefficient if using a small number like 10.

      Virtually all functions need to loop over the "digits" of the bignum. So, it would speed up things having a huge base, like 1<<30, or better 1<<62.

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

        That's a good idea. I will fix it one day.

        → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

how about using fft in multiplication

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, Can I do documentation on this and share with my friends ? I will mention you as creator and won't change anything in the code ?

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I can't use it.

[Error] 'to_string' was not declared in this scope

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

    it seems that you are using code::blocks unfortunately it's compiler doesn't have to_string() idk why! but in other compilers(like codeforces' ones) this will work fine

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

      I use Code::Blocks and it has std::stoi() and std::to_string(),you need to update version.

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

        yah it seems that they added it finally I didn't use code::block for a while now but I had this problem with it before

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Careful with using this template, as there is some bug in the == method that was giving me wrong results (albeit very rarely).

→ Reply