darkahmed's blog

C++ BigInt and BigFloat.
By darkahmed, history, 9 months ago, In English

Hello Codeforces!!

A few days ago, I wrote a code for BigInt and BigFloat classes and i would like to share it with you for feedback and improvement. For the code Press here.

Note: My BigFloat class stores numbers as a numerator and denominator to efficiently represent fractions like (1/3) without wasting data.

You can use functions like floor(object, n), ceil(object, n), or round(object, n) to extract the first n decimal places or convert the object to a string with a specified precision using str(n).

I've also implemented all comparison operations for BigFloat objects.

Note: The modulus operation for BigFloat currently calculates the modular inverse of the number. While this is interesting, you might also consider offering standard modulus behavior for users.

The Important Operations is

Multiplication: O((n + m) * log(n + m)) using FFT (Fast Fourier Transform). However, for small values of m, O(n * m) might be faster due to lower constant factors. (Here, n refers to the number of digits in the first number, and m refers to the number of digits in the second number.)

Addition and Subtraction: O(max(n, m)) for efficient handling.

Division and Modulus: O(n * m).

Bitwise Operations: O(n * log(n)).

GCD (Greatest Common Divisor) and LCM (Least Common Multiple): O(n * n * log(n)).

Other Mathematical Functions: I've added ceil, floor, round, abs, sqrt, and cbrt (using Newton's Method) to enhance the functionality of the BigFloat class.

Finally, I would like to thank mostafa133 for his help for this code and TryOmar for training me during the beaver scholarship.

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

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

division and gcd can be faster than square also.

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

    if you have an idea say it and i may add it to my code :)

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

      It's very tricky to make long division efficiently. I think the best reference in this area is Donald Kunth's "The Art of Computer Programming Volume 2" (chapter 4).

      Basically, for the best efficiency (of all arithmetic, not only division), a BigInt must be represented as a vector of uint32_t or uint64_ts (based on the architecture), not a list of digits in base 10. Serialization (in base 10) becomes much harder in this way, though.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Are you mean to make change the base from 10 to a big number :O

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

        It is an insane genius trick, i will do it after my exams );

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

        But it will be slower for division, i loop to 10 to fins the number but here i will loop to a humber bigger );

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

          Yeah, so division is hard :) I highly recommend reading Knuth, if you are serious about learning arbitrary-precision arithmetic.

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

            ok, thanks a lot for your help <3

            → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I have an idea, no one care about the memory so i can do the two methods and the big number i can make it a power of two to do the binary operation fast and do fft and all operations for the 2 polynomials, edit : i will read the book after the exams.

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

        Thanks a lot <3, i have a very nice idea now will change my bigint to be very faster, multiplay faster 20 times or more and divide faster 4 times and plus faster 18 times and minus faster 18 times and binary operations in O(n) and n is the number divide ULLONG_MAX !!! gcd faster 360 times !!!

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

        I will do it but after ecpc if i was free :) this is a great idea and i can do ntt for a big mod to make it better :)

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

Great job using Templates and operator overloads! It makes it easy to use and work with. I also liked the idea of the BigFloat. Well done.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

gamed

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wl3 el donya ya ray2 <3 <3

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

Hey guys, I have a way to deal with division and modular in $$$\Theta(f(n)\log n)$$$ time, where $$$f(n)$$$ is the complexity of multiplying two $$$n$$$-length integer (which means, the complexity is $$$\Theta(n\log^2n)$$$ altogether). The code was written a long time ago, so I can't remember how did I implement it :(

Code

UPD: note that the << and >> operators are "shifting", or "multiplying $$$10^x$$$" in my code, instead of multiplying $$$2^x$$$!

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

    Very cool, i will read it and add it to my new idea that will make all operation faster and binary operations will be O(n)!!! Or lower but the division will be O(n^2) so i will read your code because it will be very cool, thanks a lot for helping <3

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Edit : i think it is O(n*log^2(n)), i calculated it, very nice code <3

    → Reply