C++

Forum

 
BigInt library

Pages: 12
machinafour (66)
Many thanks for your time, you've been very helpful, I'll bookmark that link

Hopefully now I can solve a few Project Euler problems I haven't been able to do due the huge numbers involved.

Just need to work out how to use the boost library now...hopefully it isn't too hard to do some basic maths on big numbers using the multiprecision headers
machinafour (66)
So I have successfully been using the Boost library multiprecision cpp_int header after following JLBorges advice. Now I want to try using mpz_int from withing the gmp.hpp header (also found in the boost>multiprecision folder), which should, I think, allow for unlimited precision. For example one of the project Euler problems is to find the first Fibonacci number with more than 1000 digits, and numbers this big are out of the scope of the cpp_int variable type. But I cannot seem to use the mpz_int. Below is code that works for cpp_int, and very similar code for mpz_int. When I try to compile the second program I get a load of errors, some of which I pasted at the bottom.

Using the command line g++ -std=c++98 -Wall -I /Users/plangto/Desktop/boost_1_54_0 -o cpp_int_test cpp_int_test.cpp, thic works:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include </Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

int main()
{
	cpp_int v ("1");

	// Do some arithmetic:
	for(unsigned i = 1; i <= 100; ++i)
	   v *= i;

	std::cout << v << std::endl; // prints 100!
	
	return 0;
}


And using the command line g++ -std=c++98 -Wall -I /Users/plangto/Desktop/boost_1_54_0 -o mpztest mpztest.cpp, this fails to compile:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include </Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp>

using namespace boost::multiprecision;

int main()
{
	mpz_int v = 1;

	// Do some arithmetic:
	for(unsigned i = 1; i <= 1000; ++i)
	   v *= i;

	std::cout << v << std::endl; // prints 1000!
	
	return 0;
}


Here are some of the error messages:

In file included from mpztest.cpp:1:
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:19:17: error: gmp.h: No such file or directory
In file included from mpztest.cpp:1:
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:346: error: ISO C++ forbids declaration of ‘mpf_t’ with no type
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:346: error: expected ‘;’ before ‘&’ token
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:351: error: expected `;' before ‘const’
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:351: error: ISO C++ forbids declaration of ‘mpf_t’ with no type
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:351: error: expected ‘;’ before ‘&’ token
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:356: error: expected `;' before ‘protected’
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:357: error: ‘mpf_t’ does not name a type
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp: In copy constructor ‘boost::multiprecision::backends::detail::gmp_float_imp<digits10>::gmp_float_imp(const boost::multiprecision::backends::detail::gmp_float_imp<digits10>&)’:
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:77: error: ‘m_data’ was not declared in this scope
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp: In member function ‘boost::multiprecision::backends::detail::gmp_float_imp<digits10>& boost::multiprecision::backends::detail::gmp_float_imp<digits10>::operator=(const boost::multiprecision::backends::detail::gmp_float_imp<digits10>&)’:
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:90: error: ‘m_data’ was not declared in this scope
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:93: error: ‘m_data’ was not declared in this scope
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp: In member function ‘boost::multiprecision::backends::detail::gmp_float_imp<digits10>& boost::multiprecision::backends::detail::gmp_float_imp<digits10>::operator=(long long unsigned int)’:
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:105: error: ‘m_data’ was not declared in this scope
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:109: error: ‘mpf_t’ was not declared in this scope
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:109: error: expected `;' before ‘t’
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:110: error: ‘t’ was not declared in this scope
/Users/plangto/Desktop/boost_1_54_0/boost/multiprecision/gmp.hpp:111: error: ‘m_data’ was not declared in this scope
JLBorges (13770)
Once you have the compiler option -I /Users/plangto/Desktop/boost_1_54_0,
just #include <boost/multiprecision/cpp_int.hpp> would be adequate.
(The directory /Users/plangto/Desktop/boost_1_54_0 would be searched for files included with <>)


> Fibonacci number with more than 1000 digits,
> and numbers this big are out of the scope of the cpp_int variable type

boost::multiprecision::cpp_int supports arbitrary precision integers.

This back-end is the "Swiss Army Knife" of integer types as it can represent both fixed and arbitrary precision integer types, and both signed and unsigned types - http://www.boost.org/doc/libs/1_54_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <sstream>

int main()
{
    boost::multiprecision::cpp_int n = 12345678 ;
    for( int i = 0 ; i < 10 ; ++i ) n = n * n ;

    std::ostringstream stm ;
    stm << n ;
    const std::string str = stm.str() ;

    std::cout << "the number has " << str.size() << " digits.\n" ;
}

http://coliru.stacked-crooked.com/a/792451598819a9af



> But I cannot seem to use the mpz_int. Below is code that works for cpp_int, and very similar code for mpz_int. When I try to compile the second program I get a load of errors,

You need to install GMP (or MPIR) to be able to use boost::multiprecision::mpz_int. It is a thin wrapper around the GMP mpz_t.

(And you need to install libtommath to be able to use boost::multiprecision::tom_int)
machinafour (66)
OK great, well if cpp_int supports arbitrary precision integers then I don't need gmp right now. But I still have a problem. I am trying to do Project Euler problem 25 where you have to find the first Fibonacci number with 1000 digits, below is my code. The trouble is, it prints the Fibonacci terms correctly up to and including term 740 (155 digits), but from term 741 onwards (also 155 digits) the terms are wrong and hence I get the wrong answer at the end. I can't work out why this is happening. Any ideas? Thanks in advance 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
#include <sstream> 
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;

int main() {
	boost::multiprecision::cpp_int a ("1");
	boost::multiprecision::cpp_int b ("1");
	boost::multiprecision::cpp_int sum ("0");
	unsigned long long counter = 2;
	
	for(;;)
	{
		counter = counter + 1;
		sum = a + b;
		ostringstream convert;
		convert << sum;
		string sumstr = convert.str();
		cout << sumstr << endl << "size = " << sumstr.size() << endl << "counter = " << counter << endl << endl;
		a = b;
		b = sum;
		if(sumstr.size() == 1000) break;
	}
	cout << counter << endl;
	return 0;
}
machinafour (66)
^^ I realize my counter += 1 may be in the wrong place here :)
JLBorges (13770)
You might want to create an alias for invoking the compiler.

For instance, bash (this is probably the shell you are using):
alias c++='g++ -std=c++98 -Wall -Wextra -pedantic-errors -I /Users/plangto/Desktop/boost_1_54_0'

You can put this in your .bashrc (/Users/plangto/.bashrc)
http://en.wikipedia.org/wiki/Bash_%28Unix_shell%29#Startup_scripts

And then, you can compile and run with:
c++ -o myprogram my_program.cc && ./myprogram



> I am trying to do Project Euler problem 25 where you have to find the first Fibonacci number with 1000 digits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include <sstream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
#include <cmath>

int main()
{
    using boost::multiprecision::cpp_int ;
    const cpp_int ub = boost::multiprecision::pow( cpp_int(10), 999 ) ;

    {
        /////////// btute force /////////////////

        cpp_int a = 1 ;
        cpp_int b = 1 ;
        cpp_int fib ;

        int n = 2 ;
        while( fib < ub )
        {
            ++n ;
            fib = a + b ;
            a = b ;
            b = fib ;
        }

        std::cout << n << '\n' ; // 4782
    }

    {
        //////////// computation by rounding ////////////////
        // http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

        const double phi = ( std::sqrt(5.0) + 1 ) / 2.0 ; // golden ratio
        double n = std::ceil( ( std::log(10.0) * 999 + std::log(5.0) / 2 ) / std::log(phi) ) ;
        std::cout << n << '\n' ; // 4782
    }
}

http://coliru.stacked-crooked.com/a/541ca761728c4274
machinafour (66)
I am using bash. So when I create this alias a physical file will be created that I can put into /Users/plangto/.bashrc ?? Where will this file appear? Am I right in thinking that I can use this alias to compile any c++ program, even if it doesn't use the boost library? Sorry to ask so many questions, you've been a great help already.

Regarding the Project Euler problem: I realized there was probably a mathematical trick to get the answer but I try and do these problems without searching around online, which means I usually solve them by brute force.

I'm modifying my code based on your brute force answer above but it is still a complete mystery to me why my code failed to produce the correct term at n = 741 and onwards.

I like the way you set the ub constant to 10^999, good stuff

const cpp_int ub = boost::multiprecision::pow( cpp_int(10), 999 ) ;
Last edited on
JLBorges (13770)
> I can put into /Users/plangto/.bashrc ?? Where will this file appear?

See if you already have a .bashrc in your home directory
ls -la ~/.bashrc (~ is an abbreviation for your home directory)

If it is present, add the line defining the alias to the file.
If it is not present, create a new file .bashrc (with the alias).


> Am I right in thinking that I can use this alias to compile any c++ program, even if it doesn't use the boost library?

Yes. -I /Users/plangto/Desktop/boost_1_54_0 just adds the boost directory to the list of directories to search for files included with <>; it does not affect anything else.

machinafour (66)
OK I'll give that a go.

When I try compiling and running your exact code above for the Euler problem I get the following error message:

1000FibJL(2033) malloc: *** error for object 0x10b600948: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6
JLBorges (13770)
> When I try compiling and running your exact code above for the Euler problem
> I get the following error message:
> malloc: *** error for object 0x10b600948:
> incorrect checksum for freed object - object was probably modified after being freed.

I noticed that #include <iostream> was missing, and added it.

However, I am unable to reproduce the error (compiling with the -fsanitize=address option).

Do you still get the error with this (slightly modified) code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
#include <cmath>

int main()
{
    using boost::multiprecision::cpp_int ;
    const cpp_int ten(10) ;
    const cpp_int ub = boost::multiprecision::pow( ten, 999 ) ;

    {
        /////////// btute force /////////////////

        cpp_int a = 1 ;
        cpp_int b = 1 ;
        cpp_int fib = 0 ; // explicitly intialized to zero

        int n = 2 ;
        while( fib < ub )
        {
            ++n ;
            fib = a + b ;
            a = b ;
            b = fib ;
        }

        std::cout << n << '\n' ; // 4782
    }

    {
        //////////// computation by rounding ////////////////
        // http://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding

        const double phi = ( std::sqrt(5.0) + 1 ) / 2.0 ; // golden ratio
        double n = std::ceil( ( std::log(10.0) * 999 + std::log(5.0) / 2 ) / std::log(phi) ) ;
        std::cout << n << '\n' ; // 4782
    }
}
machinafour (66)
Yeah I still get the error.

What does this mean?:
However, I am unable to reproduce the error (compiling with the -fsanitize=address option).


I used:
g++ -std=c++98 -Wall -I /Users/plangto/Desktop/boost_1_54_0 -o 1000FibJL 1000FibJL.cpp
to compile and:
./1000FibJL
to run
JLBorges (13770)
> What does this mean?:

-fsanitize=address is a compiler option with clang 3.1+ and GCC 4.9. It turns on a memory error checker, which checks for errors in memory usage (use after free among other things).
https://code.google.com/p/address-sanitizer/wiki/AddressSanitizer#Using_AddressSanitizer

Compile with these additional options -O1 -fno-omit-frame-pointer -g and run the program, and you may get somewhat more detailed error information.
Topic archived. No new replies allowed.
Pages: 12