faheel/bigint

Arbitrary-sized integer class for C++

bigint's Issues

Use multi-threading

Successive operations on different data can be threaded to speed things up.
For example, in operator*(BigInt, BigInt), the operations for stripping leading zeroes from, and adding trailing zeroes to different BigInt objects can be multi-threaded and can be run concurrently.

Should is_valid_number be able to handle negative numbers?

Would it be useful if I implemented the ability to test if a negative number is valid or not.
I think it would be best to insert it into the existing function.

CI build with coverage fails

Build log

Snippet

[  3%] Building CXX object CMakeFiles/OperatorsRelationalTest.dir/test/operators/relational.cpp.o
[  5%] Linking CXX executable ../bin/OperatorsRelationalTest
[  5%] Built target OperatorsRelationalTest
Scanning dependencies of target OperatorsRelationalTest-capture-init
[  7%] Capturing initial coverage data for test/operators/relational.cpp
geninfo: ERROR: /home/travis/build/faheel/BigInt/build/CMakeFiles/OperatorsRelationalTest.dir/test/operators/relational.cpp.gcno: reached unexpected end of file
make[3]: *** [CMakeFiles/OperatorsRelationalTest.dir/test/operators/relational.cpp.info.init] Error 255
make[3]: *** Deleting file `CMakeFiles/OperatorsRelationalTest.dir/test/operators/relational.cpp.info.init'
make[2]: *** [CMakeFiles/OperatorsRelationalTest-capture-init.dir/all] Error 2
make[1]: *** [all] Error 2
make: *** [coverage] Error 2

Error line

geninfo: ERROR: /home/travis/build/faheel/BigInt/build/CMakeFiles/OperatorsRelationalTest.dir/test/operators/relational.cpp.gcno: reached unexpected end of file

Declaration with initialisation of a BigInt with a string fails

The following doesn't seem to work:

BigInt num = "12345678901234567890";

Generates the following error (using g++ version 7.x):

error: invalid conversion from ‘const char*’ to ‘const long long int&’ [-fpermissive]
     BigInt num = "12345678901234567890";
                  ^~~~~~~~~~~~~~~~~~~~~~

`log()` support

Add support for log2(x), log10(x), PROBABLY loge(x)(though it might be tricky), and then implement log(a,b) using the formula log_a(b) = log2(b)/log2(a)

`big_random` function: mistake in description and better implementation suggestion

Error in description

I assume that author has written right implementation and forgot about description and not otherwise. So he meant to generate positive BigInts.
Then this:

Returns a random BigInt with a specific number of digits

should be changed to

Returns a random positive BigInt with a specific number of digits

This should be fixed in include/functions/random.hpp and README.md.

Better implementation

1. std::random_device is used to generate random digits, but it is not intended to be used that way for general purposes(read this). So I suggest to use the modern way - std::mt19937. Properly seeded it has 2^19937-1 potential states(that's a lot).

2. When we are using % operation to achieve uniform integer distribution, that's not the right way, because some numbers are more likely to come up(read this for example). So let's use the right and modern way - std::uniform_int_distribution to generate

   • digits in BigInt number.
   • random length of BigInt number

Support for bitwise operators

Bitwise operators are useful for performing bit-level operations on integral data types like char or int that are internally stored in binary as multiplying or dividing a number efficiently by a power of 2 is as simple as shifting bits to the left or to the right.

The BigInt class, however, stores a number in its decimal form in a string, and so multiplying or dividing a number efficiently by a power of 10 is as simple as appending 0s or dropping digits from the end. And so supporting bitwise operators that work on powers of 2 wouldn't be very useful here as the number would first need to be converted to binary form, then the bitwise operation would be performed, and then the result would need to be converted to its decimal form, which isn't very efficient.

Therefore BigInt wouldn't be supporting bitwise operators, unless some good use cases come up for using them on large numbers (thousands of decimal digits in size).

sqrt returns incorrect result for inputs that are a perfect square

cout << sqrt(BigInt(121));

this code prints 1, however sqrt from 121 is 11.

Document sample commands to generate project files using CMake on Windows

In the Development section in README, add sample command(s) for properly generating project files using CMake for some popular Windows IDE, such as Visual Studio.

Cannot compile on msvc2019, cmake, when trying to compile the release 0.50

Details

if I write set(CMAKE_CXX_STANDARD 20) in my cmake list, it says that "at line 272, to_string is not a member of std"
at line 395, it is stoi that is not a member of std

if i change the c++ version to 14 or 17, it says that there is no "or" "and"

System info

• OS: Windows10
• Compiler: cmake, msvc2019, clion

Build fails in CLion 2017.3

Hi, I am trying to set up this project for development in CLion (on Windows 10, 64bit) but am having issues,
Currently, I have forked and pulled changes. In Clion, CMake Generation path is set as follows:

When trying to Run any test, say "ConstructorsTest" for example, I get the following errors and the build fails:

Improve the documentation related to development

Add details regarding how and when to create a new header file for new features, how to write tests for it, and how to compile and run the tests using CMake and CTest.

Operations on integers and strings with a BigInt should return a BigInt

Performing binary operations on integers or strings with a BigInt object as the second operand should return a BigInt:

big_int_1 =  5  + big_int_2;
big_int_1 = "5" + big_int_2;
// similarly for all other binary arithmetic and relational operators

Add math functions

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.

Elaborate instructions on which files to #include for which functions/operators

The README states that you only have to #include a single header file. That's not true. You also have to include one or more header files from the directories below the one with BigInt.hpp depending one the needs of your code.

Fix for MSVC?

Thank you very much for such a nice library!

I had to integrate it in a project running on Windows. A couple of places had to be fixed since MSVC complained -- nothing big, mostly comparisons between a signed and unsigned value. Would you like me to create a pull request?

I also saw that suffix increments are written instead of commonly-used prefix increments (i++ instead of ++i). Would you like me to fix that as well?

Invalid string access on modulo

The following modulo computation causes an invalid string access in the library:

#include "BigInt.hpp"

#include <iostream>

int main() {
    BigInt number("12345678901234567890123456789012345678901234567889");
    std::cout << number % 4 << std::endl;
    return 0;
}

Hex support

how to create bigInt object from hexString ?
example :
i have 512 bit number b hex

std::string i = "66676466FFFFFFF6676466676466676466677a7863787a637a783635343635343634323334323334323334323335333435333134"

BigInt a(i);
a += randomNumber;
string hexVar = a.toHex();

i want create bigInt object from this, and export this object to hex

Add functions that generate a random BigInt

The following functions that generate a random BigInt need to be implemented under include/functions/random.hpp:

• Having specific number of digits:

  friend BigInt big_random(size_t num_digits);

  Returns a random BigInt having the specified number of digits. If the number of digits are not specified, use a random value for it.

• Within a certain range:

  friend BigInt big_random(const T& low, const T& high);

  Returns a random BigInt such that low <= BigInt <= high.

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

Includes in math.hpp

There weren't any includes in math.hpp file, after adding them abs function is failing, I'm working on it.

Very slow compared to the GNU MP Bignum Library

https://gmplib.org/manual/Installing-GMP
I am learning c++, and doing an course assignment which require big integer
I ‘ve done a test for this BigInt library and GNU MP Bignum Library
this library is nearly O(n^2), while the gmp is only O(n) .
It seems the karatsuba algortithm in this library does not work well.

Multiplication Algorithms (GNU MP 6.2.1) (gmplib.org)

Support bitwise operation

Why don't we add bitwise operators here?

Features for bitwise operation

1. bitwise opeartors

• bitwise OR ( | )
• bitwise AND ( & )
• bitwise XOR ( ^ )
• bitwise NOT ( ~ )
• bitwise LEFT SHIFT ( << )
• bitwise RIGHT SHIFT ( >> )

2. bitwise-assignment opeartors

• bitwise-assignment OR ( |= )
• bitwise-assignment AND ( &= )
• bitwise-assignment XOR ( ^= )
• bitwise-assignment LEFT SHIFT ( <<= )
• bitwise-assignment RIGHT SHIFT ( >>= )

Cannot run tests from command line

For some reasons, I can't run tests from command line, I'm not sure if it's an error with my specific configuration or with the test themselves.

Details

Whenever I attempt to compile test by running "make" or run them using "make test", I get an error that "lcov is not found".
Here's the full error:

~/BigInt $ make 
CMake Error at CMake/modules/CodeCoverage.cmake:115 (MESSAGE): lcov not found! Aborting...
Call Stack (most recent call first): CMakeLists.txt:84 (SETUP_TARGET_FOR_COVERAGE)


-- Configuring incomplete, errors occurred!
See also "~/BigInt/build/CMakeFiles/CMakeOutput.log".
Makefile:7: recipe for target 'default' failed
make: *** [default] Error 1

System info

• OS: Ubuntu 16.04 LTS (Linux)
• Compiler: GCC 5.4.0/GNU Make 4.1

Improve README

Use attaswift/BigInt as an inspiration for updating the README.

Also, make sure that the README is compatible to be used as the main page for the documentation generated by Doxygen (see #50).

BigInt problem with hexdigit string

BigInt header only does not work with hexdigit string like
std::string hexStr = "123456789abcdef123456789abcdef";
It is very kind of you to extend it.

Best thanks

Automate documentation generation

Use Doxygen or other documentation generators for generating detailed and up-to-date documentation.

sqrt() always returns 1

Details

Calling sqrt() always returns 1, regardless of the number

System info

• OS: Windows
• Compiler: MinGW

big_random might return a BigInt having a value with a leading 0

big_random might return a BigInt whose value has a leading '0', which will cause problems.

Optimise binary arithmetic operations for powers of 10

• first * second
  If any one of the operands is 10^x, return the other operand appended by x zeroes.

• first / second
  If the second operand is 10^x (and is less than the first operand), return the first size - x digits of the first operand.

• first % second
  If the second operand is 10^x (and is less than the first operand), return the last x digits of the first operand.

NOTE: in the implementation of the operators, the first operand is *this, and the second operand is num.

Use a vector of integers instead of a string for faster computation

Instead of having the number's magnitude stored in a string, it would be much more efficient, in terms of both time and space, to have it stored in a vector of unsigned 64-bit integers (std::vector<uint64_t>). That is, store a number's digits in base 2⁶⁴.

The following table lists how the number's magnitude will be represented in base 2⁶⁴:

Magnitude	Representation	Comment
0	{0}	0⋅(264)0
1	{1}	1⋅(264)0
2	{2}	2⋅(264)0
264 - 1	{18446744073709551615}	18446744073709551615⋅(264)0
264	{0, 1}	1⋅(264)1
264 + 1	{1, 1}	1⋅(264)0 + 1⋅(264)1
264 + 2	{2, 1}	2⋅(264)0 + 1⋅(264)1
265	{0, 2}	2⋅(264)1
550	{11670147153572883801, 4814824860968089}	11670147153572883801⋅(264)0 + 4814824860968089⋅(264)1
2128	{0, 0, 1}	1⋅(264)2
2192	{0, 0, 0, 1}	1⋅(264)3
2256	{0, 0, 0, 0, 1}	1⋅(264)4

The way how it could speed up performance is that, for example, when adding two BigInts, instead of adding their corresponding decimal digits together, their corresponding base 2⁶⁴ digits will be added, each digit in a single operation. Moreover, this addition (or any other arithmetic operation) of vectors can be vectorised by using SSE or AVX, which would further improve performance by a few folds.

Say, for instance, that you were adding two 5000 digit numbers. In base 10 they have 5000 digits, which means that it would take 5000 operations to add them together. Instead, if they were in base 2⁶⁴, they would have 260 digits, and would therefore require only 260 operations. Using AVX-512, vectors with up to 8 64-bit digits can be added together in a single operation. Which means that by using vectorized operations, two 5000 digit numbers could be added using just 33 operations.

a bug in DIV

Details

a bug in (1453302010683093905187502545111768308832134376934/(-10531))
the result is -1380022880000293790256148755589380714920912959
but the right is -138002280000293790256148755589380714920912959

in function "std::tuple<BigInt, BigInt> divide(const BigInt& dividend, const BigInt& divisor) "
"while (temp < dividend) " may change to "while (temp <= dividend) "

System info

• OS: Red Hat 4.8.5-4
• Compiler: gcc version 4.8.5

Cannot assign string literal directly

There is no way of assigning a string literal to a BigInt directly. You can declare a BigInt and then assign a string literal but you can't do it at the same time.

For example, if I attempt:
BigInt a = "12345"
I get an error that says error: invalid conversion from ‘const char*’ to ‘const long long int&’

But this is legal:
BigInt a;
a = "12345"
I can also do:
BigInt a = (string) "12345"

I think the solution to this would simply to add a constructor and assignment for
BigInt(const char *)
BigInt& operator=(const char*)

System info

• OS: Linux Mint 18.2 Cinnamon 64-bit
• Compiler: gcc 6.3.0

MacOS Invalid token in expression during Make

Details

When compiling on MacOS Big Sur a clang error is issued by the compiler on test/catch.hpp.

In file included from BigInt/test/test_runner.cpp:10:
BigInt/include/third_party/catch.hpp:5025:13: error: invalid token in expression
CATCH_BREAK_INTO_DEBUGGER();

System info

• OS: MacOS Big Sur 11.2.1
• Compiler: Apple clang version 12.0.0 (clang-1200.0.32.29)

Add support for hexadecimal string in constructor

I think it will be useful for the BigInt to take hex as input and represent it as BigInt and support all the operations? Let me know what you think of it and I can start working on it.

I/O operators

Wouldn't be redundant using overloaded operators like >> or << for I/O?, they could be used as bitwise operators in the future, especially considering you have a to_string() method which could serve as an out method, and one of yours constructors accepts a string as a parameter, you could just input a string and then call it.

Add integration test for release file