Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
1  
"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 '12 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? –  keykeeper Feb 11 '12 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 '12 at 13:50
    
@dmeister Thank you. I'll take a look on it. Hope it will help me. –  keykeeper Feb 11 '12 at 13:55
1  
"Knuth describes something is overcomplicated". False. It's exactly the right level of complication. This is not simple. –  S.Lott Feb 12 '12 at 17:20
show 5 more comments

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  keykeeper Feb 13 '12 at 6:24
1  
@keykeeper: BigDecimal is a BigInteger with an offset. –  Zan Lynx Sep 7 '12 at 17:36
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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