Add math functions

[faheel]

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

• pow

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

  Returns the value of base^exponent.

• sqrt

  BigInt sqrt(const BigInt& num);

  Returns the square root of num.

• gcd

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

  Returns the GCD of num1 and num2.

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

[abelmarm]

Have you started any of those?

[faheel]

No, I haven't

[abelmarm]

Mind if I start with pow?

[faheel]

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

[TheWindRider]

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

[faheel]

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.

[arvindvs]

Mind if I try to get started on sqrt?

[faheel]

@arvindvs Sure, go ahead!

[faheel]

Use Newton's method for sqrt().

[arvindvs]

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?

[faheel]

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

[anandsit043]

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

[faheel]

@anandsit043 Sure!

[arvindvs]

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)

[anandsit043]

Hi @arvindvs ,
I am working on GCD

[KingAkeem]

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

[faheel]

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

[KingAkeem]

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

[KingAkeem]

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

[faheel]

@KingAkeem Yes.

[anandsit043]

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

[arvindvs]

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

[asas2016SEC]

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

[faheel]

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

[cedrikaagaard]

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

[ankur54]

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

[DefUs3r]

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.

[liamob]

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

[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?

[youcefl]

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

[Muthulakshimi]

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

[Wodlfvllf]

Hello sir I would like to add some math function.Please assignit to me