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.
division and gcd can be faster than square also.
if you have an idea say it and i may add it to my code :)
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_toruint64_ts (based on the architecture), not a list of digits in base 10. Serialization (in base 10) becomes much harder in this way, though.Are you mean to make change the base from 10 to a big number :O
It is an insane genius trick, i will do it after my exams );
But it will be slower for division, i loop to 10 to fins the number but here i will loop to a humber bigger );
Yeah, so division is hard :) I highly recommend reading Knuth, if you are serious about learning arbitrary-precision arithmetic.
ok, thanks a lot for your help <3
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.
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 !!!
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 :)
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.
Thanks for support ❤
gamed
7abyby enta agmad❤
Ana 3amltelak downvote bel8alat sawany a4elo XD
lol
XD
Na4ent sa7 elmarady
Wl3 el donya ya ray2 <3 <3
<3
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 :(
UPD: note that the
<<and>>operators are "shifting", or "multiplying $$$10^x$$$" in my code, instead of multiplying $$$2^x$$$!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
Edit : i think it is O(n*log^2(n)), i calculated it, very nice code <3