1

I'm going to write a class library for .NET which provide an implementation of arbitrary precision arithmetic for integer, rational and maybe complex numbers. What best known approaches should I become familiar with?

I tried to start with Knuth's TAOCP Vol.2 (Seminumerical Algorithms, Chapter 4 – Arithmetic) but it's too complicated. At least I couldn't get the ideas in a relatively short period of time.

Improve this question
10
  • 3
    "At least I couldn't get the ideas in a relatively short period of time". Not surprising. Keep working at it. It's not simple. There is no Royal Road.
    – S.Lott
    Feb 11, 2012 at 13:27
  • Sure. I agree. I mean that the way how Knuth describes something is overcomplicated. Maybe you can recommend me some other source of knowledge which is simpler in its explanations?
    – Igor Soloydenko
    Feb 11, 2012 at 13:34
  • 2
    The book "Java Number Crunchers" might be of interest to you. The translation from Java to .NET should be easy.
    – dmeister
    Feb 11, 2012 at 13:50
  • 2
    "Knuth describes something is overcomplicated". False. It's exactly the right level of complication. This is not simple.
    – S.Lott
    Feb 12, 2012 at 17:20
  • 2
    Arithmetic is simple to describe, but difficult to implement in an efficient way. You can always use a naive algorithm, but it won't necessarily be fast.
    – Robert Harvey
    Feb 12, 2012 at 20:46

2 Answers 2

Reset to default
2

If you are using C# 4.0 or later, then you already have a BigInteger class. Starting from here and creating your own Rational class will save you a lot of time.

If you want to build everything yourself, then you will have to implement some complex algorithms, especially for multiplication. You could start with the naive multiplication algorithm that has time complexity O(n²). A lot of other algorithms will depend on multiplication (division, modular exponentiation, gcd, square roots, etc.). If you have have everything working and a solid set of unit tests, then you can replace the naive multiplication algorithm for something like 3-way Toom-Cook multiplication or an even more advanced algorithm.

Improve this answer
2
  • I have already thought of almost all what you say. I know about BigInteger and I wonder, why Microsoft didn't implement BigDecimal or BigReal type. Well, I decided to start with naive implementation as you and Robert Harvey advice. I had already written about two dozens of test methods by the time I asked this question so the idea seems to be good. Thank you.
    – Igor Soloydenko
    Feb 13, 2012 at 6:24
  • 2
    @keykeeper: BigDecimal is a BigInteger with an offset.
    – Zan Lynx
    Sep 7, 2012 at 17:36
2

Addressing the question about why there's BigInteger but not BigReal, etc.: this has to do with the arbitrary nature of floating point representation. The IEEE standard for 64-bit floating point sets aside some of the bits for the exponent ("characteristic") and the "whole" number part ("mantissa"). There is a standard for extended precision floating point but it seems general: http://en.wikipedia.org/wiki/IEEE_754-2008#Extended_and_extendable_precision_formats.

So, extending floating point requires arbitrary decisions about how large to make the parts of the number whereas extension of integers is straightforward: just keep adding high-order digits as necessary. For this reason, it makes sense to look at rationals (a ratio of extended-precision integers) rather than floating point. Take a look here - http://www.jsoftware.com/jwiki/Essays/Extended%20Precision%20Functions - for some high-level considerations on this.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.