John, Chris, and anyone else interested,
<snip>
In conclusion, it is obvious that we are in agreement that support for arbitrary sized integers for C++ is required. I still believe that Boost.LargeInt is a good contender. It is has both the above points and an elegant design (even if I do say so myself), and would just need improvements to its integral division and multiplication. Unfortunately, that is beyond my expertise, hence the current "simple but it works" solution.
Thank you for your detailed post, Michael. In my opinion, medium integers from 64 through, say, 1024 or 2048 bits are a niche needing explicit treatment. This is not in conflict with the proposed Boost.Multiprecision, rather an extension of a potential functionality of boost. The trick is finding the right architecture, granularity, interoperability and performance in order to knit these together in a cohesive big-number implementation. First off, we need to sort out the potential Boost.Multiprecision, as I believe this is headed in the right direction. Then we need to understand how to address the high performance needs of medium-sized integers.
If you have any suggestions on how this could be improved or merged into existing work, I would be more than happy to collaborate. Any further questions or comments would of course be appreciated.
For medium sized integers, build the integer type from four 32-bit radix-2 components. Do not use allocation. Use naive multiply, etc. Use the Knuth algorithm for long division. Add and sub are linear in the limb count. Mul-by-long-long and div-by-long-long are of linear complexity. But you will do no more than repeat what John did for his cpp_int back ends. He even got the performance more than up-to-par with move semantics and expression templates. Well, If we ever want to get bad-assed performance, we would have to team up in a coalition of programmers. I include a bibliography below. Nonetheless, nobody can roll this one alone---Nobody! For your interests, the first order of business would be to make a dedicated medium integer library with the desired interoperability that significantly beats the performance of Boost.Multiprecision off-the-rack and matches the performance of GMP. The second (and much larger goal) is to package everything in a palatable form for everyone---no small task. Here, I mean medium sized integers, multiprecision integers, rationals and floats, as well as fixed-point in a sensible standardized form for all users. This is a massive task. I'm booked right now---solid, booked out 'till autumn. I encourage you to keep going. In my opinion, though, we really need to clear up the potential Boost.Multiprecision now and find out how to deal with medium integers thereafter. Best regards, Chris. P.S. Somebody will nag on you about so-called "top-posting" soon. Just like they nagged me on it in the beginning. Bibliography from anothe post: Here is the Bibliography for much of my R&D on big numbs. Best regards, Chris J. Arndt and C. Haenel "Pi Unleashed" Springer, Heidelberg, 2001 ISBN 3-540-66572-2 F. Bornemann, D. Laurie, S. Wagon and J. Waldvogel, "The SIAM 100-Digit Challenge: A Study in High-Accuracy Numerical Computing" Society for Industrial and Applied Mathematics SIAM (TM), Philadelphia, 2004. ISBN 0-898-71561-X J. M. Borwein and P. Borwein "Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity" John Wiley, New York, 1998 ISBN 0-471-83138-7, Paperback R. Brent and P. Zimmermann "Modern Computer Arithmetic" Cambridge University Press, Cambridge, 2011 ISBN 978-0-521-19469-3 L. Fousse, G. Hanrot, V. Lefevre, P. Pelissier and P. Zimmermann "MPFR: A Multiple-Precision Binary Floating-Point Library With Correct Rounding" ACM ACM Trans. Math. Soft., Vol. 33, Issue 2 ACM, 2007 A. Gil, J. Segura and N. M. Temme, "Numerical Methods for Special Functions" Society for Industrial and Applied Mathematics SIAM (TM), Philadelphia, 2007 ISBN 978-0-898-71634-4 J. M. Muller "Elementary Functions: Algorithms and Implementation", 2nd Edn. Birkhaeuser, Boston, 2006 ISBN 978-0-817-64372-0 J. M. Muller, N. Brisebarre, F. de Dinechin, C. M. Jeannerod, V. Lefevre, G. Melquiond, N. Revol, D. Stehle and T. Torres "Handbook of Floating-Point Arithmetic" Birkhaeuser, Boston, 2010 ISBN 978-0-817-64704-9 C. M. Kormanyos "Algorithm 910: A Portable C++ Multiple-Precision System for Special-Function Calculations" ACM ACM Trans. Math. Soft., Vol. 37, Issue 4 ACM, 2011 D. E. Knuth "The Art of Computer Programming, Volume 3 Seminumerical Algorithms", 3rd edn. Addison Wesley, 1998