### darkahmed's blog

By darkahmed, history, 6 weeks ago,

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.

• +43

 » 6 weeks ago, # |   +5 division and gcd can be faster than square also.
•  » » 6 weeks ago, # ^ |   0 if you have an idea say it and i may add it to my code :)
•  » » » 6 weeks ago, # ^ |   0 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.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Are you mean to make change the base from 10 to a big number :O
•  » » » » 6 weeks ago, # ^ |   0 It is an insane genius trick, i will do it after my exams );
•  » » » » 6 weeks ago, # ^ |   0 But it will be slower for division, i loop to 10 to fins the number but here i will loop to a humber bigger );
•  » » » » » 6 weeks ago, # ^ |   0 Yeah, so division is hard :) I highly recommend reading Knuth, if you are serious about learning arbitrary-precision arithmetic.
•  » » » » » » 6 weeks ago, # ^ |   0 ok, thanks a lot for your help <3
•  » » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 6 weeks ago, # ^ |   0 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 !!!
 » 6 weeks ago, # |   +11 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.
•  » » 6 weeks ago, # ^ |   0 Thanks for support ❤
 » 6 weeks ago, # |   0 gamed
•  » » 6 weeks ago, # ^ |   -8 7abyby enta agmad❤
•  » » 6 weeks ago, # ^ |   -7 Ana 3amltelak downvote bel8alat sawany a4elo XD
•  » » » 6 weeks ago, # ^ |   +1 lol
•  » » » » 6 weeks ago, # ^ |   -11 XD
•  » » » » 6 weeks ago, # ^ |   -8 Na4ent sa7 elmarady
 » 6 weeks ago, # |   0 Wl3 el donya ya ray2 <3 <3
•  » » 6 weeks ago, # ^ |   0 <3
 » 6 weeks ago, # | ← Rev. 2 →   0 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 friend pair div_bf(Unsigned a, const Unsigned& b) { if (a < b) return {(Unsigned)0, (Unsigned)a}; // cout << '\$' << b.size() << endl << flush; assert((bool)b); Unsigned c(0); c.init_size(a.size() - b.size() + 1); for (int i = c.size(); i; i--) { int lo = 0, hi = Z - 1, mi, res = 0; while (lo <= hi) { mi = (lo + hi) >> 1; if (((b * mi) << (i - 1)) <= a) { res = mi; lo = mi + 1; } else hi = mi - 1; } c[i] = res; a -= ((b * res) << (i - 1)); } c.flat(); return {c, a}; } friend Unsigned num_inv(const Unsigned& a) { // cout << a << ' ' << a.size() << endl << flush; if (a.size() <= 20) { // cout << "FINISH RECURSION\n"; // cout << a.size() << endl << flush; Unsigned b; b.init_size(a.size() << 1 | 1); b.back() = 1; return div_bf(b, a).ff; // cout << "EIOFJEOIFJOWE\n" << flush; } Unsigned b; int m = a.size(), k = (m + 5) >> 1; b.init_size(k); for (int i = b.size(), j = a.size(); i; i--, j--) b[i] = a[j]; b.flat(); Unsigned c = num_inv(b), d = a * c * c; d >>= (k * 2); b = c + c; b <<= m - k; Unsigned res = b - d - 1; d.init_size(m << 1 | 1); d.back() = 1; c = d - res * a; if (c >= a) ++res; return res; } friend Unsigned div_newton(const Unsigned& a, const Unsigned& b) { if (a.size() < b.size()) return Unsigned(); Unsigned x = a, y = b; int n = x.size(), m = y.size(); if (n > m * 2) { x <<= n - m * 2; y <<= n - m * 2; m = n - m; n = m << 1; } Unsigned z = num_inv(y); y = x * z; y >>= m * 2; x = b * y; // cout << x.size() << "#\n" << flush; z = a - x; if (z >= b) ++y; return y; } UPD: note that the << and >> operators are "shifting", or "multiplying $10^x$" in my code, instead of multiplying $2^x$!
•  » » 6 weeks ago, # ^ |   0 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
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Edit : i think it is O(n*log^2(n)), i calculated it, very nice code <3