C++ BigInt and BigFloat.

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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.

Комментарии (24)

Написать комментарий?

ShaoNianTongXue5307

7 месяцев назад, # |

division and gcd can be faster than square also.

→ Ответить

darkahmed

7 месяцев назад, # ^ |

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

_Kee

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.

← Rev. 2 →

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 !!!

5 месяцев назад, # ^ |

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 :)

TryOmar

+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.

Thanks for support ❤

O_Elmasry

gamed

-8

7abyby enta agmad❤

-7

Ana 3amltelak downvote bel8alat sawany a4elo XD

Omar-G

lol

-11

Na4ent sa7 elmarady

InfernalMind

Wl3 el donya ya ray2 <3 <3

L_Wave

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<Unsigned, Unsigned> 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$$$!

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

← Rev. 3 →

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

Блог пользователя darkahmed