BigInt Add math functions

Note: type T can be a BigInt, std::string or long long.

[x] pow

BigInt pow(const T& base, int exponent);

Returns the value of base^exponent.

[x] sqrt
```
BigInt sqrt(const BigInt& num);
```
Returns the square root of num.

[x] gcd

BigInt gcd(const T& num1, const BigInt& num2);
BigInt gcd(const BigInt& num1, const T& num2);

Returns the GCD of num1 and num2.

[x] lcm

BigInt lcm(const T& num1, const BigInt& num2);
BigInt lcm(const BigInt& num1, const T& num2);

Returns the LCM of num1 and num2.

[ ] is_probable_prime
```
bool BigInt::is_probable_prime(size_t certainty);
```
Returns true with a certainty of for whether this BigInt is prime, based on either the Fermat or Miller-Rabin primality tests. Similar to Java's BigInteger.isProbablePrime.

Dec 05 '17 00:12 faheel

Have you started any of those?

Dec 23 '17 17:12 abelmarm

No, I haven't

Dec 24 '17 10:12 faheel

Mind if I start with pow?

Dec 24 '17 12:12 abelmarm

Whichever way you like. For pow use the binary exponentiation method.

Dec 24 '17 13:12 faheel

Hello! Came across this project from Up For Grabs

I have some doubt on the new pow function. It's doing the a^n = (-a)^(1/n) if n < 0 transformation, but I think the formula should be a^n = 1/(a^(-n)) if n < 0.

And the test didn't include any n < 0 cases yet...

Dec 28 '17 21:12 TheWindRider

Yeah, I'm fixing the pow function and the tests. There are a few more issues with it such as handling 0⁰, 0^-1, 0^-2 etc.

Dec 28 '17 22:12 faheel

Mind if I try to get started on sqrt?

Dec 28 '17 22:12 arvindvs

@arvindvs Sure, go ahead!

Dec 28 '17 22:12 faheel

Use Newton's method for sqrt().

Dec 28 '17 22:12 faheel

I'm currently having trouble compiling the code (sorry I'm completely new to open source and contributions ). I have edited the math.test.cpp file and math.hpp file and they are ready to commit to the branch I have created. Is it alright if I go ahead and push this commit without compiling and correcting potential errors, and you can take a look at it?

Dec 29 '17 00:12 arvindvs

Yes, you can push your changes and create a PR. Then you can comment regarding the issue you're facing in your PR.

Dec 29 '17 00:12 faheel

Hi, I would like to contribute this project. Can I implement gcd part?

Dec 29 '17 08:12 anandsit043

@anandsit043 Sure!

Dec 29 '17 10:12 faheel

Can I get started on LCM? (I will have to implement GCD in order to make this work. If someone else is working on GCD, I can wait for them to finish. Otherwise I can proceed with both)

Dec 31 '17 18:12 arvindvs

Hi @arvindvs , I am working on GCD

Jan 01 '18 11:01 anandsit043

I would like to take up the is_probable_prime function if no is currently working on it.

Jan 02 '18 04:01 KingAkeem

@KingAkeem Go for it, as it doesn't seem like anyone else is working on it.

Jan 02 '18 07:01 faheel

Awesome, I'm working on implementing Rabin-Miller primality testing now.

Jan 02 '18 12:01 KingAkeem

Should is_probable_prime be declared as a public member function but defined inside of math.hpp?

Jan 02 '18 15:01 KingAkeem

@KingAkeem Yes.

Jan 03 '18 02:01 faheel

Hi @arvindvs, Should I implement the lcm part or you are done with it?

Jan 04 '18 07:01 anandsit043

@anandsit043 Sorry for the late response. Go ahead, I have not yet completed LCM.

Jan 04 '18 21:01 arvindvs

how can i contribute to this project. I new to open source. Please guide.

Jan 17 '18 20:01 asas2016SEC

@AanjaneyaSinghDhoni All of the functions mentioned in this issue have been implemented (PR for is_probable_prime is under review).

If you'd like to contribute, you can try implementing the functions mentioned in issues #18 and #19. If you need some more info regarding implementation details, comment on the respective issues.

Jan 18 '18 18:01 faheel

Hello, is_probable_prime is not yet implemented right? Would it be okay if I gave it a shot?

May 27 '18 20:05 cedrikaagaard

Hello! Is this issue still open? I would like to contribute to it.

Oct 04 '18 08:10 ankur54

Hello @faheel sir, I am new to contributions and cmake, though I have a very good experience in coding with c++. I would like to take up the task of building a function out of the list mentioned above or if you can suggest any new function. Or if there's any other issue that might suit me, please suggest.

Oct 04 '18 12:10 DefUs3r

Hello! I'll give the "is_probable_prime" function a try! I'll send a message when it's finished.

Dec 08 '19 19:12 liamob

Hello @faheel I have implemented and tested the is_probable_prime function, however it is difficult to test using a very large number due to the incredibly significant runtime caused when you take the (randomNumber) to the power of another amount.

On the wikipedia page (https://en.wikipedia.org/wiki/Miller–Rabin_primality_test) it would be where the pseudocode says x ← a^d mod n Any tips?

Jan 29 '20 05:01 jslcontributor

Hello @faheel I have implemented and tested the is_probable_prime function, however it is difficult to test using a very large number due to the incredibly significant runtime caused when you take the (randomNumber) to the power of another amount.

On the wikipedia page (https://en.wikipedia.org/wiki/Miller–Rabin_primality_test) it would be where the pseudocode says x ← a^d mod n Any tips?

You have to implement and use a modular exponentiation i.e. when computing X = A^B mod N, you do not compute A^B and then take the remainder modulo N, you loop on the binary representation of B squaring and/or multiplying by A mod N depending on whether the current bit is set. Have a look at https://en.wikipedia.org/wiki/Modular_exponentiation and/or https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/.

Feb 17 '20 10:02 youcefl

Hi, checked this up at -up for grabs. Can someone help me with understanding what I should do? Does this issue ask for coding any program with math functions..

Oct 07 '21 15:10 Muthulakshimi

BigInt BigInt copied to clipboard

Add math functions

BigInt
BigInt copied to clipboard