----- Original Message ----- From: "Ronald Garcia" <garcia@cs.indiana.edu>

Greetings,

The one response I saw to your library mentioned some compilation problems. Have those been addressed?

Cheers, ron

Yes, the big integer library now also works on gcc 3.4. The library is now tested with vc7.1, gcc 3.2.2 and gcc 3.4. It uses partial specializations, so it won't work on vc7 and lower. I haven't got access to other compilers, so I can't say anything about compliance with other compilers. Richard Peters

----- Original Message ----- From: "Jody Hagins" <jody-boost-011304@atdesk.com>

"Richard Peters" <r.a.peters@student.tue.nl> wrote:

...

Hello,

I am wondering what the opinions about the big_integer library are. A few months ago, discussion indicated much interest in a library like this, but after I posted my library two weeks ago, I only got one response. Are there people who have tried this library or read its documentation, and if so, what are your comments? I would like to know if I'm on the right track with this library.

I think most people would like to see one, but may be in the same boat as me. I wrote my own many years ago (based on the algorithms in Knuth, vol 2), and it works well in most cases, except where I need really good performance. In that case, I have yet to see anything beat gmp. I imagine you will have to do a lot of architecture dependent stuff to match their performance. I don't like their C++ wrappers, so I rolled my own that are more geared to what I want.

At the moment, I'm looking for comments about the interface, not about speed. Once the interface is stable, I will look for fast implementations, and make gmp available via preprocessor switches.

Most people may fall into a similar boat, which, when coupled with the intricate official reviews going on right now, makes it hard to set aside time to examine another library, just for the sake of examining the library.

You may get a better response with time...

Ok, I guess I'll have to be patient... best regards, Richard Peters

----- Original Message ----- From: "Christoph Ludwig" <cludwig@cdc.informatik.tu-darmstadt.de>

Hi,

I didn't read earlier discussions of your proposal. But could you briefly summarize what does your library set apart from other arbitrary precision libraries (from the top of my head: gmp, libI, cln, piologie...)?

Regards

Christoph

There is not much special about my library. Like the gmp, this library uses expression templates to avoid the creation of temporary values, which when the values become large provide an increase in performance. Once the interface matures, I want to make the library be able to use other arbitrary magnitude libraries to perform high-speed calculations. Apart from that, this library is released under the boost license. The other libraries that I know of are released under GPL or have other restrictions. best regards, Richard Peters

"Thorsten Ottosen" <nesotto@cs.auc.dk> writes: | "Richard Peters" <r.a.peters@student.tue.nl> wrote in message | news:03e901c42dde$d0463c30$38639b83@campus.tue.nl...

| | Apart from that, this library is released under the boost license. The | other | | libraries that I know of are released under GPL or have other | restrictions.

| which is very good. GPL is like saying nobody wants to use it. OTOH: GPL != LGPL -- Lgb

----- Original Message ----- From: "Christoph Ludwig" <cludwig@cdc.informatik.tu-darmstadt.de>

Hi,

...

There is not much special about my library. Like the gmp, this library uses expression templates to avoid the creation of temporary values, which when the values become large provide an increase in performance.

I sometimes wonder whether a bigint library that implements move semantics could not provide an additional significant efficiency gain. (Since I can avoid temporaries most of the time, my applications don't profit from expression templates that much.) I never performed experiments, though, this is only a conjecture.

Do you have any plans in this direction?

What would implementing move semantics look like? Do you mean that an expression like x = y * z where y and z aren't used after this expression can be implemented as a swap(x, y); x *= z? I'm not sure how to implement it, but if a method exists which provides a significant efficiency gain and does not interfere with the interface too much, then I'm certainly interested in implementing it.

...

Once the interface matures, I want to make the library be able to use other arbitrary magnitude libraries to perform high-speed calculations.

Hm, I "inherited" some time ago the task to maintain a computer algebra library that can be built on top of several bigint libraries. Since these libraries are optimized for different use cases and this fact shows in their respective interfaces, it is hard to come up with a wrapper that does neither favour one particular library nor pulls all libraries down to their least common denominator.

My idea was to delegate the simple operations +, -, * etc. to the other libraries, like gmp. This makes the speed of the library higher in the case such a library is installed, but does not give me the burden of coding really efficient versions of those operators myself. The big integer library will remain a reasonably general-purpose integer library. I do not intend to make this library cover every area where large integers are needed, but I want to provide a reasonable library for average integer calculations. I intend to use this library for cryptographic algorithms, where I want decent performance, but also a simple intuitive interface. Therefore, I would like a 'normal' library where the backend is adapted to the frontend, and not the other way around. Best regards, Richard Peters

Christoph Ludwig <cludwig@cdc.informatik.tu-darmstadt.de> writes:

Hi,

On Fri, Apr 30, 2004 at 12:01:01PM +0200, Richard Peters wrote:

...

From: "Christoph Ludwig" <cludwig@cdc.informatik.tu-darmstadt.de>

...

...

There is not much special about my library. Like the gmp, this library uses expression templates to avoid the creation of temporary values, which when the values become large provide an increase in performance.

I sometimes wonder whether a bigint library that implements move semantics could not provide an additional significant efficiency gain. (Since I can avoid temporaries most of the time, my applications don't profit from expression templates that much.) I never performed experiments, though, this is only a conjecture.

Do you have any plans in this direction?

What would implementing move semantics look like? Do you mean that an expression like x = y * z where y and z aren't used after this expression can be implemented as a swap(x, y); x *= z? I'm not sure how to implement it, but if a method exists which provides a significant efficiency gain and does not interfere with the interface too much, then I'm certainly interested in implementing it.

The only proposal I ever toyed with was Andrei Alexandrescu's Mojo. But recently there were threads about two proposals by David Abrahams and Andrea Torsello (search the archive for subjects that contain "move semantics").

And look in the boost sandbox at libs/move/test/*. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

----- Original Message ----- From: "Paul A Bristow" <pbristow@hetp.u-net.com>

I am absolutely certain we need a big integer in Boost.

Your implementation, tests and documentation look fine, but I am unable to assess the relevant merits of your implementation and previous efforts, for example from Ronald Garcia.

Perhaps you can indicate your take on this to stimulate some discussion?

Well, the main difference between these two libraries are that my library uses expression templates to optimize out the use of (most) temporaries, in contrast to other libraries proposed here. I wanted to try out what the differences between these two attempts would be. So far, it resulted in a lot more code. The difference in documentation is that my documentation leaves the return type of operators unspecified to accomodate for expression objects. Another motivation for my library is to spice up the process of getting ANY big_integer library into boost. I'm perfectly happy if the ideas in this library are taken into another library which is to be incorporated into boost, or if it is decided that the trade-offs of expression templates are too large so that we can say 'well, this route is taken and proven to not be worthwile'. The big advantage of my library should be the performance gain from using expression templates. Unfortunately, as I haven't got efficient implementations of the underlying operators, I can't make fair comparisons yet. The c++ wrappers at gmp use expression templates, which is an indication that it is likely to provide a performance gain. The difference between the expression-template approach versus the normal approach is not purely implementation-related. There are cases where expression templates have to be taken into account, for example: template<class T> T add_one(T x) { T y; y = x; return y + 1; } ... add_one(a + b); When a and b are big_integers, the template parameter of add_one will have a weird type (something like expression<add_ex<big_integer, big_integer> >) which isn't useful for declaring y. Workarounds would be to use add_one<big_integer>(a + b) or add_one(big_integer(a + b)). I admit that this is ugly. Discussion here at boost must indicate whether this is a reasonable trade-off or not. This is not yet documented, and the expression class will be made non-copyable to avoid these kind of cases.

PS Can you say which compilers 'like' it? Do you want others to try it out?

I have tried it at vc7.1, gcc3.2 and gcc3.4. The example and test file compile and run successfully on all of them. Due to the use of partial specializations, it will not compile on vc7.0 and below and other compilers that do not support partial template specialization. I do not have access to other compilers, it would be great if you or other persons could test it on other compilers and give me feedback on the results. best regards, Richard Peters

On Thu, 29 Apr 2004 17:45:52 -0400 John Phillips <phillips@mps.ohio-state.edu> wrote:

Unimplemented C++ feature big_integer.hpp line 153

The portion in question is

template<class T> friend bool operator<(T lhs, const expression<Base>& rhs) { return rhs > lhs; }

which doesn't strike me as all that odd, but maybe I'm missing something. I'll try to look at it more, later and see if I can fix the problem.

Maybe something as simple as moving the definition... template<class T> friend bool operator<(T lhs, const expression<Base>& rhs); ... template<class T> bool operator<(T lhs, const expression<Base>& rhs) { return rhs > lhs; }

From: "Jody Hagins" <jody-boost-011304@atdesk.com>

...

Unimplemented C++ feature big_integer.hpp line 153

The portion in question is

template<class T> friend bool operator<(T lhs, const expression<Base>& rhs) { return rhs > lhs; }

which doesn't strike me as all that odd, but maybe I'm missing something. I'll try to look at it more, later and see if I can fix the problem.

Maybe something as simple as moving the definition...

template<class T> friend bool operator<(T lhs, const expression<Base>& rhs);

...

template<class T> bool operator<(T lhs, const expression<Base>& rhs) { return rhs > lhs; }

After trying a few things, completely removing the template friend declaration and defining the function outside of the class seems to work. I'll implement the changes and upload the code as soon as possible. vc7.1 does not like template friends to be defined outside the class. The problem is that it is not a member, but there are two template parameters. Two seperate lists of template parameters are not allowed, but vc7.1 chokes when the two parameters are declared in one list (template<class Base> template<class T> versus template<class Base, class T>) which seems kind of logical because the two templates are declared seperately in the class. Is there a correct way to have templated friends of a template class defined outside of the class? best regards, Richard Peters

-------- From: "Richard Peters" <r.a.peters@student.tue.nl>

I have removed all template friends, so those shouldn't give problems anymore. I have also managed to speed up the division algorithm, which possibly makes Joel Young's test code run a lot faster. The code is uploaded to the yahoogroups file section at http://groups.yahoo.com/group/boost/files/big_integer/, the files are named big_integer-0.2.zip and big_integer-0.2.tar.gz.

There are still order of multiple order of magnitude differences in speed between rational<big_integer) and cln's cl_RA, but that doesn't matter because big_integer doesn't seem to be converting correctly unless I am completely missing something. This program /////////////////////////////////////////////////////////////// #include <iostream> #include "boost/big_integer.hpp" #include "boost/rational.hpp" int main(int argc, char* argv[]) { { typedef long long unsigned int data_t; data_t a(9); std::cerr << a << '\n'; data_t n1 = data_t(1200144) * data_t(1000000) + data_t(722375); std::cerr << n1 << '\n'; } { typedef boost::big_integer data_t; data_t a(9); std::cerr << a << '\n'; data_t n1 = data_t(1200144) * data_t(1000000) + data_t(722375); std::cerr << n1 << '\n'; } } /////////////////////////////////////////////////////////////// produces: 9 1200144722375 11 21355614624707 as output using g++ (GCC) 3.3.2 20031022 (Red Hat Linux 3.3.2-1) Why? Joel

Richard, I just downloaded the new version of the library, and the changes you made cleared up the "unimplemented feature" error. However, I am now seeing a cascade from an overload resolution problem. The function template<class IntegerType> inline expression<big_integer_impl>::expression(IntegerType x, typename enable_if<is_integral<IntegerType> >::type* dummy) : big_integer_impl(x) {} in big_integer.hpp is getting an "illegal overload" error. I don't see an obvious reason for this so I'll try and look into it. John