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.

Hungry Blue Dev
  • 179
  • 10
  • 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](https://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE144.HTM) 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. – rwong Mar 26 '17 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. – rwong Mar 26 '17 at 16:38
  • @rwong Yes definitely. An integer first. Then the rest. And I do intend to take a symbolic approach for commonly used Mathematical constants. I thought of an expression tree for representing Reals that can be constructed from a combination of operations. – Hungry Blue Dev Mar 26 '17 at 16:45
  • 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. – Robert Harvey Mar 26 '17 at 17:22
  • 1
    why not C? it's more reasonable language overall, and certainly not handicapped in speed compared to C++ – Display Name Mar 26 '17 at 18:01
  • @SargeBorsch Yes I suppose that's not a bad idea. However, coming from a Java background, I'm a bit used to OOP. Maybe I need to change that. – Hungry Blue Dev Mar 26 '17 at 18:05
  • @Astrobleme OOP in C++ is a bloody joke. Avoid it if you can. – Display Name Mar 26 '17 at 18:06
  • Heck, even OOP in C is more sane than in C++ – Display Name Mar 26 '17 at 18:07
  • @SargeBorsch LOL. Then I'll stick to C I think. I know the basics. I just need to organise. – Hungry Blue Dev Mar 26 '17 at 18:08
  • 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?](https://softwareengineering.meta.stackexchange.com/q/6961). 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.” – amon Mar 26 '17 at 18:54
  • @amon It's okay. I understand. You may close it. I'll spend some time thinking about the architecture. Then I'll post a more focussed question. – Hungry Blue Dev Mar 26 '17 at 18:59
  • be aware that SargeBorsch's opinions on C++ are by no means universal.One thing C++ will allow you do is overload operators so you can write x + y rather than add (x, y) – Nick Keighley Mar 27 '17 at 10:41
  • @Nick Yes I'm aware of that fact. It's one of the cool features that led me to consider C++ in the first place. – Hungry Blue Dev Mar 27 '17 at 12:30
  • C++ Is not a joke if you know how to use it. One of the powerful features of C++ is the ability to create templates and to do meta template programming to keep everything generic, reusable and even portable if you know what you are doing. – Francis Cugler Apr 12 '18 at 01:18

1 Answers1

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.

Christophe
  • 74,672
  • 10
  • 115
  • 187