Kevin wrote:

there is no such library in the boost tree yet. I'm working on one and since this library hasn't been proposed for review yet, I'd suggest to factor this dependency out as a template parameter in your source if that is possible in a convenient way.

It is easy for me to make the high precision data type a member of coordinate_traits that defaults to same type as is used to store the result of an area computation, but can be specialized to any user defined data type. That would factor the dependency out, as you say. Perhaps I should provide meta-function for this instead of traits.... I took a look at your linked source and there were quite a few files there. Which ones pertain to large integer types. mp_int.h appeared to be the class that provides high precision integer arithmetic, providing infinite/variable precision arithmetic on an array of digit values, with support for negative numbers. Can your digit_type be 64 bit unsigned integer? If so you have pretty much the ideal variable precision integer. --snip-- private: digit_type* digits_; size_type used_, capacity_; int sign_; }; --end snip-- Why not simply use std::vector<digit_type, Allocator> instead of managing your own array? mp_int is actually overkill for my immediate problem, but would certainly do the job and allow me to make a general solution. It looks like something we need in a place like boost. I managed to solve my immediate problem by distributing division and recovering the lost precision due to truncation with modulus operations. I had to use 64 bit unsigned integers with associated sign stored in a separate integer to perform hastily hacked up 65 bit signed arithmetic. I used this to compute the product of deltas between signed 32 bit integers and work with those values to eventually compute the intersection of two line segments in a way that is robust to overflow and truncates the result minimally and predictably. When do you think your mp_int library will be ready for review? I have to provide a solution internally within a month or so and plan to submit the geometry library to boost once completed, probably around end of year. Luke _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Luke wrote:

...

Can your digit_type be 64 bit unsigned integer? If so you have pretty much the ideal variable precision integer.

Kevin wrote:

It can, but only if you have a 128 bit word type (necessary for intermediate results in the calculations) or if all important calculations were coded in assembler. Then I could take advantage of add with carry instructions etc and handle carries in place.

Ah, I see. 32 bit is certainly good enough. Speaking of assembler and platform specific stuff, do you know how to trap integer overflow events in C++ to handle them as exceptions? It would be a big performance advantage to try a calculation that might overflow, catch the overflow exception thrown by the event handler and then execute high precision/complex calculations instead to get the correct answer. This would need to coexist with code that doesn't catch overflow, so the event handler would need to inspect a dynamic policy that informs it whether to ignore or throw in it's currently context. overflow_policy.push(THROW); try { a = b * c * d; } catch overthrow_exception { a = foo(b, c, d); }; overflow_policy.pop(); Kevin wrote:

So what you actually need is a fixed precision integer that lives on the stack. mp_int involves memory allocation and algorithms designed for very large integers which is probably overkill.

Yes, I was originally thinking a parameterized fixed precision integer that lives on the stack. Something like: template <int bit_width> class integer { static const int word_length = bit_width / word_width + 1; word_type vals_[bit_width / word_width + 1]; int sign_; public: ... }; where word_width and word_type would be platform dependent. At which point you could do many of the same things with &vals_ that you do with your array of digits, but would have to overflow instead of reallocating when the size of vals_ becomes insufficient. I can look at any arithmetic operation and quickly tell exactly how many bits I need to represent it. That was how I knew I needed 65 bits to compute the line segment intersection. (I brought it down of 96 bits with algebra, but couldn't reduce the sum of products term...) Instead of adaptive precision, I would like to be able to specify how much space I need at compile time. After looking at your mp_int data structure this sounds like something you could implement quite easily by reusing a large portion of your existing code. Luke