[SoC] multi precision arithmetic library proposal.
Hi, I would like to participate in summer of code 2006. I was very surprised that boost doesn't have multi precision arithmetic, and since I'm quite algorithm/C++ concerned, I wish to propose/make it as a SoC project. I'll appreciate any response about that idea, what do you feel about that etc. Best regards, Mateusz Rukowicz.
On Sun, 30 Apr 2006 17:56:46 +0200, Mateusz Rukowicz wrote
Hi,
I would like to participate in summer of code 2006. I was very surprised that boost doesn't have multi precision arithmetic, and since I'm quite algorithm/C++ concerned, I wish to propose/make it as a SoC project. I'll appreciate any response about that idea, what do you feel about that etc.
Hi Mateusz, Yes, I think there would be a positive response to an SOC proposal in this area. You are correct, there is no multiprecision arithmetic support in Boost now. However, be aware that there is some prior work already in the boost sandbox. You might want to have a look at these links: http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/boost/bigint.hpp?rev=1.28&view=auto http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/libs/bigin... This was put together by Ron Garcia @ Univ of Indiana. Also, Richard Peters was apparently was doing some work in this space. Try out this query to look at some of the posts in 2005 about bigint: http://tinyurl.com/lpsma Before going to far down this path you might want to get in contact with them and see if there is a way to extend/finish their work. Also on a mathmatical track, there is a need for someone to develop TR1 math special functions. Specifically have a look at: http://engineering.meta-comm.com/resources/cs-win32_metacomm/doc/html/boost_... This might be another possibility if the BigInt direction doesn't work out. John Maddock and Paul Bristow have been the folks most involved Finally, I'll mention that another possible project in this area would be to build a Boost implementation for the Decimal Arithmetic proposal. This is a proposal that IBM is making before the standard committee. That latest draft is at: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1977.html It would be fabulous to have a Boost implementation of this proposal available. I've gone ahead and added this set of ideas to the Wiki page: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summer... Look forward to your proposal! Jeff
Yes, I think there would be a positive response to an SOC proposal in this area. You are correct, there is no multiprecision arithmetic support in Boost now. However, be aware that there is some prior work already in the boost sandbox. You might want to have a look at these links:
A big int should be too hard, an arbitary precision floating point arithmetc type would be very welcome too. That's harder as it needs std lib support to be useful (exp, pow, log trig functions etc), so it's rather more work, but then again the student has all summer right ? :-) The existing lib's in this area all have downsides: NTL is very reliable, but is the most thread-unsafe code I've ever seen. Lydia looks good but is licence constrained, and doesn't really build on Win32. Any others?
Also on a mathmatical track, there is a need for someone to develop TR1 math special functions. Specifically have a look at:
http://engineering.meta-comm.com/resources/cs-win32_metacomm/doc/html/boost_...
This might be another possibility if the BigInt direction doesn't work out. John Maddock and Paul Bristow have been the folks most involved
Funnily enough I was tempted to suggest that. It's rather hard work though, for both student and mentor.
Finally, I'll mention that another possible project in this area would be to build a Boost implementation for the Decimal Arithmetic proposal. This is a proposal that IBM is making before the standard committee. That latest draft is at:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1977.html
It would be fabulous to have a Boost implementation of this proposal available.
Very fabuluous indeed, but have you read the spec? It make me quiver just to think about it! Maybe as in all things familiarity would simplify things somewhat. John.
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of John Maddock | Sent: 01 May 2006 10:42 | To: boost@lists.boost.org | Subject: Re: [boost] [SoC] multi precision arithmetic library | proposal. | | > Yes, I think there would be a positive response to an SOC | proposal in | > this area. You are correct, there is no multiprecision | > arithmetic support in Boost now. However, be aware that | there is some | > prior work already in the boost sandbox. You might want to have a | > look at these links: | > Finally, I'll mention that another possible project in this area | > would be to build a Boost implementation for the Decimal Arithmetic | > proposal. This is a proposal that IBM is making before the standard | > committee. That latest draft is at: | > | > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1977.html | > | > It would be fabulous to have a Boost implementation of this proposal | > available. | | Very fabuluous indeed, but have you read the spec? | It make me quiver just to think about it! Since 'the student has all summer', I think that decimal is just a little ambitious! I think just getting infinite precision integers (and perhaps rationals too) in Boost would be a good achieveable target. I find it most diappointing that we have had several implementations in the sandbox but none have survived a review. I am uncertain what higher precision floating-point would be most useful in Boost. An exact (infinite precision) real like http://keithbriggs.info/xrc.html or a defined precision (typically several hundred decimal digits) like NTL RR, or just a higher (128-bit) precision like NTL quad_float, (potentially of interest to MSVC users who are limited to 64-bit doubles == long doubles without even an 80-bit option). Some 'not-so-nice' features of quad_float have popped-up recently - funny epsilon, thread-unsafe... (NB Also I believe NTL is GPL not Boost licence). It may be that these tools are mainly used once only to calculate coefficients, as John Maddock is doing for 'proper' math functions? And so there is less need for these in Boost? Potential users views? Paul -- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB Phone and SMS text +44 1539 561830, Mobile and SMS text +44 7714 330204 mailto: pbristow@hetp.u-net.com http://www.hetp.u-net.com/index.html http://www.hetp.u-net.com/Paul%20A%20Bristow%20info.html
Paul A Bristow wrote:
It may be that these tools are mainly used once only to calculate coefficients, as John Maddock is doing for 'proper' math functions? And so there is less need for these in Boost?
Potential users views?
These types are essential for financial calculations and in/in combination with databases. From my experience, any types with fixed scale and/or length wouldn't be useful at all. IBM and IEEE furthermore try standardize some (special) decimal floating point types for future hardware support (see n1977!), but from what I've heard, this seems to be rather chaotic and controversial in IEEE. Stefan
Le lundi 01 mai 2006 à 13:42 +0200, Stefan Slapeta a écrit :
IBM and IEEE furthermore try standardize some (special) decimal floating point types for future hardware support (see n1977!), but from what I've heard, this seems to be rather chaotic and controversial in IEEE.
The situation is not as bad as it may seem. Formats, arithmetic operators, rounding modes are already defined, are not controversial, and will be part of the revision of IEEE-754 standard. So a library can be written now without risking from becoming unusable once the standard is published. The only controversial point at the moment is the binary low-level encoding of the numbers (a hardware-efficient encoding would be really inefficient for pure software implementations). So from a library point of view, the only difference between the various proposals lies in the accessor functions: reading/writing mantissas/exponents of decimal floating-point numbers. Best regards, Guillaume
John Maddock wrote:
A big int should be too hard, an arbitary precision floating point arithmetc type would be very welcome too. That's harder as it needs std lib support to be useful (exp, pow, log trig functions etc), so it's rather more work, but then again the student has all summer right ? :-)
IMO a big int would be the most welcome as it would provide the _base_ for an arbitrary-length floating point type.
Very fabuluous indeed, but have you read the spec? It make me quiver just to think about it! Maybe as in all things familiarity would simplify things somewhat.
I don't think so. Integer arithmetics is a well-described field and there is a lot of good material about it, all well listed under http://www2.hursley.ibm.com/decimal. It's not necessary to provide a full-optimized implementation with fourier transformations for multiplication etc. - this can be added later as well. A type that does the basic operations and maybe some of exp/pow/log would be very helpful, too, to start with! I'm rather afraid that the design of such a type could become quite complex, as you have to provide a good separation of interface and actual calculation: this is the only possibility to use the same one later for n1977 as well - but this is also a great chance! Stefan
Le lundi 01 mai 2006 à 10:41 +0100, John Maddock a écrit :
Yes, I think there would be a positive response to an SOC proposal in this area. You are correct, there is no multiprecision arithmetic support in Boost now. However, be aware that there is some prior work already in the boost sandbox. You might want to have a look at these links:
A big int should be too hard, an arbitary precision floating point arithmetc type would be very welcome too. That's harder as it needs std lib support to be useful (exp, pow, log trig functions etc), so it's rather more work, but then again the student has all summer right ? :-)
I am not sure what you mean by "arbitrary precision floating-point arithmetic". There are two different approaches: arbitrary precision arithmetic (accuracy-driven implementations) and multi-precision floating-point arithmetic (precision-driven implementations). NTL falls in the second category.
The existing lib's in this area all have downsides: NTL is very reliable, but is the most thread-unsafe code I've ever seen. Lydia looks good but is licence constrained, and doesn't really build on Win32. Any others?
MPFR is a C multi-precision floating-point library. IRRAM and Reallib are C++ arbitrary precision libraries. Best regards, Guillaume
Hi Mateusz & Boost community / moderators, Mateusz Rukowicz wrote:
Hi,
I would like to participate in summer of code 2006. I was very surprised that boost doesn't have multi precision arithmetic, and since I'm quite algorithm/C++ concerned, I wish to propose/make it as a SoC project.
I did some work in this area which I was planning to eventually boostify some day. In fact, I thought about SoC participation with this very project but decided that it would be too much for my schedule. Since I put a lot of thought into the design, I hereby volunteer to (maybe co-)mentor this project. Here is a quick overview of what I have, so far: 1. a tested draft set of fairly efficient algorithms for arbitrary precision arithmetic on natural numbers 2. an allocation scheme that allows to have one allocation per operation, worst case 3. the concept of an expression template framework that allows: - truly intuitive conversion rules (e.g. division of two integers assigned to a rational gives a correct, non-truncated result), - exploiting destructibility of temporaries to reduce copying/allocation, and - allocation of temporaries on the stack. I'd like to sustain in-depth technical discussion until the organizational things are cleared up. Given that the Boost moderators find myself worthy for the job, my next step would be investigation of previous work in this field and a summary for the Wiki page. Best regards, Tobias
Tobias Schwinger wrote:
Hi Mateusz & Boost community / moderators,
Mateusz Rukowicz wrote:
Hi,
I would like to participate in summer of code 2006. I was very surprised that boost doesn't have multi precision arithmetic, and since I'm quite algorithm/C++ concerned, I wish to propose/make it as a SoC project.
I did some work in this area which I was planning to eventually boostify some day. In fact, I thought about SoC participation with this very project but decided that it would be too much for my schedule.
Since I put a lot of thought into the design, I hereby volunteer to (maybe co-)mentor this project.
--- Excerpt from private correspondence: Mateusz Rukowicz wrote:
Tobias Schwinger wrote:
Tobias Schwinger wrote:
Mateusz Rukowicz wrote:
Hi,
A couple of days ago, I posted ond boost mail-list proposal of arbitrary arithmetic lib. You wrote that you would like to mentor this project, I have a few questions regarding that. First - I would like to say in my application that you would mentor this project - are you ok with that?
You're talking about the application to Google, right? Fine with me -- but AFAIK it still needs a blessing from the Boost moderators.
Feel free to forward this mail to the list/mods.
On second thought: probably /I/ should... Mind if I do?
Well, I think that if I'll mention that you said you would like to mentor this in my soc application, they would consider that, and contact you. It also might be good idea to post it on boost mailing-list.
---
Whoever thinks about arbitrary precision arithmetic, please take a look at M.J. Kronenburg's proposal for TR2, which has been briefly discussed at the last WG21 meeting: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1692.pdf Please also look at NTL: http://www.shoup.net/ntl/ IMHO, NTL is one of the best and most complete library on the market, it would be very desirable (and maybe not even very difficult) to "boostify" it. Thanks -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished.
Gerhard Wesp wrote:
Whoever thinks about arbitrary precision arithmetic, please take a look at M.J. Kronenburg's proposal for TR2, which has been briefly discussed at the last WG21 meeting:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1692.pdf
Read it already. I also agree that it seems the most appropriate paper to influence the SoC work.
Please also look at NTL: http://www.shoup.net/ntl/ IMHO, NTL is one of the best and most complete library on the market, it would be very desirable (and maybe not even very difficult) to "boostify" it.
Certainly! Unfortunately, the license is incompatible for "in-place boostification". A reimplementation of that functional range is far beyond the scope of an SoC project. Anyway, you might find it interesting that my current SoC proposal http://tinyurl.com/qtyhh (still incomplete) would provide a solid fundament for algorithms like implemented by NTL (without requiring a procedural interface for maximum efficiency). Thank you for your comments! Regards, Tobias
On http://tinyurl.com/qtyhh, you write: rational c = a / b // where a and b are integers a=1 b=2 integer d = a / b // c is one half, d is zero [...] rational e = convert(a / b) // e is zero I guess this can be achieved by some clever expression template magic, but do you really want to go there? I've always tried to stick to the "do it as the ints" philosophy, which does have the problems you describe, but has the advantage of being consistent with the rest of the language. Regards, -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished.
Gerhard Wesp wrote:
On http://tinyurl.com/qtyhh, you write:
rational c = a / b // where a and b are integers a=1 b=2 integer d = a / b // c is one half, d is zero [...] rational e = convert(a / b) // e is zero
I guess this can be achieved by some clever expression template magic, but do you really want to go there?
It's like math with pen-and-paper, which still feels more intuitive to me than whatever type-safe programming languages came up with, so far. The code is more readable and more flexible. You don't have to be afraid to break things when you change the type of a varaible, it either just works or the problem is caught at compile time plus you don't have to change around casts (as there usually are none required). Expression templates are needed anyway to optimize away temporaries (the paper you referenced in your previous post also mentions this opportunity). Otherwise we end up with a "high performance interface" which makes our optimized code look like as if we were coding in assembler (this aspect of NTL is rather ugly, IMO).
I've always tried to stick to the "do it as the ints" philosophy, which does have the problems you describe, but has the advantage of being consistent with the rest of the language.
The framework I propose is most certainly consistent with the language - it just has its own conversion rules that are free of machine-centric considerations ;-). The inherent loose coupling of the classes that implement the domains makes it very easy to extend the library (easier than what it takes to implement proper conversion otherwise, I guess). Further we can't really "do it as the ints", unfortunately -- temporary ints can usually be optimized away while we can't teach our optimizers to generally remove temporary "heavyweights" (we have to teach our compilers, instead)... Regards, Tobias
On Tue, May 09, 2006 at 06:04:31PM +0200, Tobias Schwinger wrote:
The code is more readable and more flexible. You don't have to be afraid to break things when you change the type of a varaible, it either just I'm not convinced. What if you change a and b from "heavyweight" integer to built-in integer? Then the semantics of the your example change:
rational c = a / b // where a and b are integers a=1 b=2 c will then be zero. Regards, -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished.
Gerhard Wesp wrote:
On Tue, May 09, 2006 at 06:04:31PM +0200, Tobias Schwinger wrote:
The code is more readable and more flexible. You don't have to be afraid to break things when you change the type of a varaible, it either just
I'm not convinced. What if you change a and b from "heavyweight" integer to built-in integer? Then the semantics of the your example change:
rational c = a / b // where a and b are integers a=1 b=2
c will then be zero.
Well, if you change the type to 'boost::path', the semantics change too... Granted, in the case you mention you'll have to know what you're doing. The aim is, however, to make things so efficient that you wouldn't want to do it ;-). If you can foresee that a or b might both be builtin types (e.g. in a template function) you can write: rational c = convert(a) / b Regards, Tobias
On Tue, May 09, 2006 at 07:06:56PM +0200, Tobias Schwinger wrote:
rational c = convert(a) / b
Do you already have possible overloads and return types for convert() in mind? Regards, -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished.
Gerhard Wesp wrote:
On Tue, May 09, 2006 at 07:06:56PM +0200, Tobias Schwinger wrote:
rational c = convert(a) / b
Do you already have possible overloads and return types for convert() in mind?
Sure: 'convert' returns an expression, just like any other operator. That expression will be something like a reference wrapper for the argument. When the full compound expression is evaluated the convert expression protects its component expression from result type propagation. Best case, it's all it does -- the evaluation machinery can view the result of the evaluation as a value of the expected domain. For narrowing conversions and for builtins the appropriate algorithm has is invoked to perform the actual conversion. Regards, Tobias
Tobias Schwinger wrote:
Gerhard Wesp wrote:
On Tue, May 09, 2006 at 07:06:56PM +0200, Tobias Schwinger wrote:
rational c = convert(a) / b
Do you already have possible overloads and return types for convert() in mind?
Sure: 'convert' returns an expression, just like any other operator. That expression will be something like a reference wrapper for the argument.
When the full compound expression is evaluated the convert expression protects its component expression from result type propagation.
Best case, it's all it does -- the evaluation machinery can view the result of the evaluation as a value of the expected domain.
For narrowing conversions and for builtins (*) the appropriate algorithm has is invoked to perform the actual conversion.
(*) actually not only for builtins but for types that are not "first class citizens" of the framework...
On 5/9/06, Tobias Schwinger <tschwinger@neoscientists.org> wrote:
Do you already have possible overloads and return types for convert() in mind?
Sure: 'convert' returns an expression, just like any other operator. That expression will be something like a reference wrapper for the argument.
When the full compound expression is evaluated the convert expression protects its component expression from result type propagation.
Best case, it's all it does -- the evaluation machinery can view the result of the evaluation as a value of the expected domain.
void f( rational const & ) ; void f( integer const & ) ; integer a , b ; f( convert( a ) / b ) ; what is going to happen ? or do you expect end-users to provide overloads like void f( integer_expression_stub const & ) ; ? then they are bound to a particular implementation of integer. am i missing something? *** i am also not convinced the proposed evaluation mechanism is really useful: it may look better than rational r = rdiv( a , b ) ; to some, but looks worse for others, and it goes against existing practice; but maybe i'm just too conservative br, andras
Andras Erdei wrote:
On 5/9/06, Tobias Schwinger <tschwinger@neoscientists.org> wrote:
Do you already have possible overloads and return types for convert() in mind?
Sure: 'convert' returns an expression, just like any other operator. That expression will be something like a reference wrapper for the argument.
When the full compound expression is evaluated the convert expression protects its component expression from result type propagation.
Best case, it's all it does -- the evaluation machinery can view the result of the evaluation as a value of the expected domain.
void f( rational const & ) ; void f( integer const & ) ; integer a , b ; f( convert( a ) / b ) ;
what is going to happen ?
Overload resolution is ambiguous. And it makes perfect sense: an expression (talking pen-and-paper math) without a target domain is just an expression...
or do you expect end-users to provide overloads like void f( integer_expression_stub const & ) ; ? then they are bound to a particular implementation of integer.
No - use a template. This way the expression can be used for further optimization within the algorithm. Note that the most efficient usage has the simplest interface.
am i missing something?
My explanation is certainly still missing one important case to be complete: what if you need a separate translation unit? Well, I propose a function template - let's call it 'promote' - that enforces to the worst case domain within the expression. f( promote(convert(a) / b) ) // constructs a temporary of b's domain . An explicit conversion would work as well... Note that unlike with converting constructors, here is no (maybe costworthy) magic behind the scenes -- the user has to explicitly request an operation, which is in fact a good thing. As a library developer you can, of course, put the invocation of 'promote' into an inline function template in your header to enable implicit promotion.
i am also not convinced the proposed evaluation mechanism is really useful: it may look better than
rational r = rdiv(a , b) ;
To come anywhere remotely close, performance-wise (and without expression templates) it would have to be: rdiv(r,a,b); Which is not arguable to be inconvenient. Further we would need manifold overloads (on a per-argument basis) that essentially do the same thing but for different input domains -- a maintainance nightmare on the implementor's side. To be equally efficient we would finally need variants for some input arguments to be destructible (we can't use overloading so it makes the interface even uglier). All construction of temporaries would be spelled out by the user and clutter problem-specific code with manual optimization -- a maintainance nightmare on the client's side.
to some, but looks worse for others,
Now, after "correcting" the equivalent non-ET interface I find it hard to imagine that there's a single soul on this planet who seriously prefers it...
and it goes against existing practice;
Well, AFAIK math *is* existing practice. In fact, it has even been there first!
but maybe i'm just too conservative
Careful comparison with more conservative approaches is required to find out whether a new way is superior or not... Thanks, Tobias
Tobias Schwinger wrote:
Gerhard Wesp wrote:
Whoever thinks about arbitrary precision arithmetic, please take a look at M.J. Kronenburg's proposal for TR2, which has been briefly discussed at the last WG21 meeting:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1692.pdf
Read it already. I also agree that it seems the most appropriate paper to influence the SoC work.
Yes and no. There are so many aspects in the implementation (some of them I mentioned in earlier) that make any approach completely useless if they're not considered and thought about very deeply. And: I'm afraid that are very complicated things. Sorry to say that, but creating 'something' that is influenced a WG21 proposal by isn't the right way here, it's *really* just waste of time! As I tried to explain before, the only useful thing to do in this field I can imagine is an arbitrary length integer implementation that can later be used to implement a decimal class. I promise, it will be complex enough to encapsulate the integer encoding for all platforms, and once when such aspects are resolved, any other work is welcome, too! Stefan
Stefan Slapeta wrote:
As I tried to explain before, the only useful thing to do in this field I can imagine is an arbitrary length integer implementation that can later be used to implement a decimal class.
Please refer to my proposal rather than inspiration material. It *is* supposed to handle arbitrary number systems. Regards, Tobias
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Tobias Schwinger | Sent: 09 May 2006 14:24 | To: boost@lists.boost.org | Subject: Re: [boost] [SoC] multi precision arithmetic | library,mentoring request | | > Please also look at NTL: http://www.shoup.net/ntl/ | > IMHO, NTL is one of the best and most complete library on | the market, it | > would be very desirable (and maybe not even very difficult) to | > "boostify" it. | | Certainly! Unfortunately, the license is incompatible for | "in-place boostification". Wuld it be worth asking the author if he would change the licence terms to Boost licence? Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS
Tobias Schwinger <tschwinger@neoscientists.org> writes:
Tobias Schwinger wrote:
Hi Mateusz & Boost community / moderators, ...
A message that's entirely forwarded, with no introduction, does not communicate much. What do you want us to get from/do with this? -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Tobias Schwinger <tschwinger@neoscientists.org> writes:
Tobias Schwinger wrote:
Hi Mateusz & Boost community / moderators, ...
A message that's entirely forwarded, with no introduction, does not communicate much.
I inserted the forwarded message into quoted previous post according to the context. You have my apologies in case it caused confusion.
What do you want us to get from/do with this?
The intent was to keep organizational stuff public. Regards, Tobias
Tobias Schwinger <tschwinger@neoscientists.org> writes:
David Abrahams wrote:
What do you want us to get from/do with this?
The intent was to keep organizational stuff public.
Well, for what it's worth, it didn't communicate anything to me that I could understand, and I still don't know what it means. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Tobias Schwinger <tschwinger@neoscientists.org> writes:
David Abrahams wrote:
What do you want us to get from/do with this?
The intent was to keep organizational stuff public.
Well, for what it's worth, it didn't communicate anything to me that I could understand, and I still don't know what it means.
Mateusz contacted me in private, asking whether he should mention my name in his application as the mentor for this project. Well, my request has neither been accepted nor rejected, so far. After telling Mateusz, he suggested mentioning me as a potential mentor. I figured it would be best to document this conversation publicly, so there are no surprises on the Boost-side and also to remind you of pending mentoring acceptance and to indicate activity on this front. Does this clarification work for you? Regards, Tobias
"Mateusz Rukowicz" <mateusz.rukowicz@vp.pl> wrote in message news:4454DE3E.5000701@vp.pl...
Hi,
I would like to participate in summer of code 2006. I was very surprised that boost doesn't have multi precision arithmetic, and since I'm quite algorithm/C++ concerned, I wish to propose/make it as a SoC project. I'll appreciate any response about that idea, what do you feel about that etc.
At the Berlin C++ committee meeting earlier this month the LWG decided expressed interest in getting a further proposal for infinite precision arithmetic for TR2 based on http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1718.pdf Maarten Kronenburg is now working on putting together a further proposal for the standards committee. I asked him a few days ago if he was interested in submitting his reference implementation to Boost, and he replied that his underlying computational functions are written in X86 assembler. Thus for Boost a portable C++ implementation would be needed, switching over to the assembler version for supported platforms. You might want to email Maarten to see if he would like help with a portable C++ version and with getting a proposal ready for Boost submission. --Beman
Beman Dawes wrote:
"Mateusz Rukowicz" <mateusz.rukowicz@vp.pl> wrote in message news:4454DE3E.5000701@vp.pl...
Hi,
I would like to participate in summer of code 2006. I was very surprised that boost doesn't have multi precision arithmetic, and since I'm quite algorithm/C++ concerned, I wish to propose/make it as a SoC project. I'll appreciate any response about that idea, what do you feel about that etc.
At the Berlin C++ committee meeting earlier this month the LWG decided expressed interest in getting a further proposal for infinite precision arithmetic for TR2 based on http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1718.pdf
One aspect that isn't address by that paper, and non of the others I've seen references to, is use of infinite precision integer in the cryptography domain. There are a few aspects in that domain that make the proposals I've seen useless. There are two aspects which must be addressed: 1. Security of memory allocation. 2. Access to normalized representation. Aspect #2 is needed for extraction and injection (IO but not iostream). In crypto there are a variety of ways to represent such numbers as required by certificates, keys, protocols, etc. So a documented access to the representation is essential for implementing such translation efficiently. Aspect #1; Crypto needs to make specific guarantees for the memory it uses for computation. For C++ this usually means that all the code needs to work with some for a special secure allocator. The way that Botan <http://botan.randombit.net/> (this is the lib I use for the crypto uses I have) is to implement secure versions of some containers, and use those in its BigInt implementation. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
On Tue, May 09, 2006 at 11:03:02PM -0500, Rene Rivera wrote:
the proposals I've seen useless. There are two aspects which must be addressed:
1. Security of memory allocation. Should be solved on a memory management/OS level. Adding allocator
"Useless" is a strong word. parameters may be the way to go. But it may be easier to ask the OS to erase the memory once the process dies. Are there OSes that support this?
2. Access to normalized representation. Define "normalized representation".
I do think that the type should support all the conversions defined for the built-in types, including conversion to hexadecimal.
required by certificates, keys, protocols, etc. So a documented access to the representation is essential for implementing such translation efficiently.
Can you give an example of a translation that would require this access? Regards, -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished.
Gerhard Wesp wrote:
On Tue, May 09, 2006 at 11:03:02PM -0500, Rene Rivera wrote:
the proposals I've seen useless. There are two aspects which must be addressed:
"Useless" is a strong word.
But I think it applies. The problem with the crypto domain is that if any single part is insecure the whole is insecure.
1. Security of memory allocation.
Should be solved on a memory management/OS level. Adding allocator parameters may be the way to go. But it may be easier to ask the OS to erase the memory once the process dies. Are there OSes that support this?
OpenBSD, which is what I run on my server :-), does that and also supports encrypted pages. But having the OS handle it doesn't help C++ all that much. Since most stdlib implementations allocate from a larger preallocated memory segment, the OS will never clear the small part you would be using for the smaller bigint instance. Now you could just make a bigint implementation that does additional work of clearing memory but that will impact efficiency for other domains. Hence the need to provide a way to control how the memory is maintained in a domain specific manner.
2. Access to normalized representation. Define "normalized representation".
In this particular case, a representation that is compact but is not necessarily the one used internally. Ideally it would be the one used internally to minimize translation time. For integers this might be a 2s complement array, and for floats it might be individual sign, exponent, and mantissa as bigints (and hence as 2s complement arrays).
I do think that the type should support all the conversions defined for the built-in types, including conversion to hexadecimal.
I can agree with that for symmetry. But at least in the crypto domain conversion to built-in types would never be used. The logic goes... If one is using a bigint one is expecting the number to not fit within any built-in type, hence one would never convert to those types. That logic is likely to apply to other domains, but since one wants conversion from built-in types it seems reasonable to provide the other conversions.
required by certificates, keys, protocols, etc. So a documented access to the representation is essential for implementing such translation efficiently.
Can you give an example of a translation that would require this access?
* SSH uses Base64 encoding to store keys. This is common as the most compact representation is desired for transmittal through things like email. * If one is implementing a key exchange protocol, for example I use a Diffie Hellman key exchange <http://en.wikipedia.org/wiki/Diffie-Hellman>, sending a binary representation would be preferred to save on bandwidth. The Java BigInt provides a toByteArray() conversion with a defined representation <http://tinyurl.com/fghkk>, with a matching constructor. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
participants (12)
-
Andras Erdei -
Beman Dawes -
David Abrahams -
Gerhard Wesp -
Guillaume Melquiond -
Jeff Garland -
John Maddock -
Mateusz Rukowicz -
Paul A Bristow -
Rene Rivera -
Stefan Slapeta -
Tobias Schwinger