0

I know I am reinventing the wheel. But I'm really interested in implementing arbitrary precision numbers (integers, rationals, complex, etc) in C or C++ and their algorithms. Please be patient.

My question: How should I approach the process of implementation (and testing) of arbitrary-precision numerical algorithms in C or C++? I don't want to dive right in without a strategy and ultimately see my project fail.

I'll appreciate advice on the following questions: What foundation to base my code on? What sort of structure should I try to apply to the project? Any other general advice for me?

Here are a few obvious questions out of the way:

Why C or C++? Why not stick to Java?

I want to make my implementations as fast as possible without sacrificing too much readability. I plan on keeping things modular and maintainable.

I wanted to be as close as possible to the machine so I plan to step out of my comfort zone: Java and learn C and/or C++ for a change. I have most of the syntax down, now I just need to pick up the best practices and conventions. I hope this project will help me to learn C and/or C++ as well.

Why do you want to do that? There are lots of libraries out there. Use them.

That's not really my objective. I want to gain experience in the field of implementation of numerical algorithms. I'll graduate high school this April and I want to be a researcher in the field of Computer Science. One of the things that have constantly fascinated me is the vast number algorithms for doing the most basic mathematic operations: basic general arithmetic. I want to get into the details of the algorithms. I am willing to mathematically analyse my implementations because I can and I want to.

It's not the destination; it's the journey I'm after.

Who is the end user of your project?

Anyone who wants to use a fast, safe and stable arbitrary precision library (for whatever purposes, from cryptography to language design). I'll make the project open source, so other people (researchers, developers) can refer to my implementation. I'm not planning to make money off of it (directly at least).

What are you planning to do after that?

I will build on my project, maybe try adding multi-threaded support for various operations. I will probably use this in my thesis (long way to go before that).

I don't think anyone else will be interested in this.

That's okay. I'll work on it alone.

Improve this question
14
  • The first step is to figure out whether you should implement an arbitrary precision integer library versus a floating-point library. Note that if you have neither, you should always begin with an integer one. You can't skip lessons in a course. This page covers some additional considerations for an integer library. Note that (1) your question is too broad for this site; (2) request for resources (educational resources or references) is out-of-topic on this site. Commented Mar 26, 2017 at 16:33
  • 4
    Keep in mind that, irrational numbers such as pi don't have a floating-point representation that can be stored in a finite number of digits. Your library would need to cut off somehow. Software applications that can carry the symbol of pi across equations and manipulations work because they manipulate mathematical expressions symbolically, not because they could use arbitrary-precision to get around the problem. Commented Mar 26, 2017 at 16:38
  • 2
    I don't want to dive right in without a strategy and ultimately see my project fail. -- Then copy the strategy that some other arbitrary-precision library uses. Failure is part of the learning process. Commented Mar 26, 2017 at 17:22
  • 1
    why not C? it's more reasonable language overall, and certainly not handicapped in speed compared to C++ Commented Mar 26, 2017 at 18:01
  • 1
    I'm voting to close this question as “too broad”. It's really cool that you want to write this library, but there are just too many equally valid approaches how this could be done. If possible, try something first, then ask a new question about a concrete problem you encountered. See also Green fields, blue skies – what is too broad?. With this question, you're also very likely to get opinions instead of facts – please disregard misleading statements and flame-war baits like “OOP in C++ is a bloody joke. Avoid it if you can.” Commented Mar 26, 2017 at 18:54

1 Answer 1

Reset to default
2

Base your code on the standard C++ library, and usual c++ conventions.

Preliminary thinking

Define the interface of your operations without thinking of the implementation. This includes conversions from and to your type (and conversion exceptions if your number is too large), and decision on whether or not allow mixed arithmetic with standard types.

Of course, you also have to decide whether the arbitrary precision is defined at compile time, or if it's to be determined as needed at runtime.

Avoid fundamental design issues

You could then make a first proof of concept, by implementing your type, but just using a private floating point.

This will allow you to start defining a test suite.

You might as well discover some flaws in your interface. At this stage, it's still easy to adjust it.

Complete the design

Then decide on a strategy on how to represent your numbers:

  • do you want to use a floating point approach (i.e. Arbitrary length mantissa and arbitrary length exponent) ?
  • do you want to use a fractional approach (i.e. Arbitrary length numerator and denominator) ?
  • do you want to code the digits including the sign and the comma (fir example as was done in the good old BCD approach ?

Verify, if you are clear on how the basis operations could be implemented, before going on. It's still inexpensive to change if you'd detect major issues.

Implement your design

Then you can fine tune your type's internals. Obviously you would have at least a string or a vector of digits (the digits are not necessary decimal digits: it could be any integer type), and certainly even two.

Your existing proven test suite can be used from the start of the implementation and will help you to quickly spot errors.

Once everything seems to work, you can extend your test suite with the really big precision numbers that you couldn't test with tour initial proof of concept.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.