Huge Real

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa

Abstract:

This project is to create an arbitrary precision real number object. This is an important project because, in many areas of science, highly precise numbers are required to make any sort of concrete decisions. For example, astronomy and particle physics. The object will also handle extremely large numbers for uses in areas like cryptography.

Calendar:

No 'meetings'. I work on the project whenever I have the time. I've spent much time designing algorithms for the mathematical operations. The coding is simply translating those algorithms into C++.

Project Development:

In implementing an arbitrary precision real number, I've run into some snags with the mathematical operations. Particularly, I'm having problems with division. My approach was correct up until that point in the project, however, intuitive "elementary school" methods don't seem to be efficient enough for a generalized object. Some people from EUROPA have suggested using a 1024-excess (or more) format of a real, which is more like the way float and double are implemented. This will require me to change my representation completely. Also, I'm going to take more time on designing the abstract component and documenting to give myself a better frame from which to work.

06-17-02
I made specifications for the Huge_Real and Huge_Int types. Huge_Real is modeled after IEEE floating point numbers. Except I'll be using Huge_Int in the exponent and mantissa fields. I completed the boolean operations, all necessary protected operations, IO operations for base 10 and Add() and Sub() of Huge_Int are in the testing phase.

06-18-02
I finished Mul() and Div() for Huge_Int. I would prefer doing Div() without other kernel operations, but that may require a more complex algorithm. All that remains for the Huge_Int subproject is to test the object for large input. I added Inc() and Dec(). Also, I added Set_Value(preserves UCHAR* val) and Get_Val(preserves UCHAR* val) for ease of use by the client.

06-19-02
I wrote a new Div() algorithm that is much faster than my previous algorithm. It occured to me that integers are not a division ring. Therefore, Div() *should* be an extension, and my algorithm models that by not accessing the representation directly. I also finished up all preliminary coding (no testing or compiling) for Huge_Real except for input.

06-21-02
I wrote the input function for Huge_Real. It's still in its preliminary stages. I began testing for Huge_Real. I realized that my original modification of the IEEE floating point number wasn't quite correct. I was simulating bit shifting for Add/Sub by setting the exponent of the smaller exponent to that of the higher and then dividing the mantissa of the smaller exponent number by the radix to the power of the difference in the original exponents. The problem with this is that this division factor may be larger than the mantissa, and since I'm using Huge_Ints a larger division factor would result in a zero answer, which is not what I want (abstract algebra strikes again!). So, I have to set the larger exponent to that of the smaller and then multiply the mantissa of the number with the originally higher exponent by the radix to the power of the difference in the original exponents. After doing some examples on paper, I think I might have to do some sort of 'normalization' process.

07-11-02
I had been experiencing some problems with subtraction, but I realized that my approach was wrong and that I should modify the addition function for subtraction exactly the same way I modified the Huge_Int functions.

10-15-02
The normalization process (mentioned above) will probably have to be something very similar to long division, but I'll have to generalize the process of long division so shortcuts and such aren't part of the process.

10-30-02
Modeling the division algorithm on Euclid's Division algorithm seems the best way to go.

11-04-02
Brainstorming ways to precisely handle repeating decimals

01-10-03
I'm going to need a variable to indicate whether the number is repeating or not and an index into the mantissa to indicate where the repeating portion of the number begins. I should also ensure that exactly one period of the repeating portion is stored.

01-15-03
Preliminary division algorithm pseudo-code written.

01-21-03
Division algorithm needed some tuning (ok...a lot of tuning)

01-26-03
Wrote Div_Rem(x,y,R) for Huge_Int, which does the same thing as Div(), but it puts the remainder in R.

01-30-03
I decided that the representation for Huge_Int was too sloppy. So, I re-implemented it using a String of unsigned characters. Now, resizing the representation dynamically takes less time than before.

02-04-03
Did some testing today to make sure that all my non-division functions work. Unfortunately, they didn't. It turns out that the representation I was coding and the representation I was conceptualizing were not the same. The coded representation wasn't any less accurate. So, I just changes some parts of my code to reflect that new representation.

02-09-03
More testing on non-division functions. They seem to be working so far.

02-14-03
Some more work done coding the division function. The interruptions better end soon or this process is going to suffer from starvation. (Ok, it was a nerdy joke.)

02-20-03
Cleaned up the interface for Huge_Int. Add and Subtract now call Add_Body, with Subtract merely changing the sign of the second parameter. Also, Div_Body was made for Div and Div_Rem to use because Div_Rem was exactly the same as Div with some extra calculation on the end.

03-01-03
Almost done with the division function, but the quarter is ending and we all know what that means...

03-12-03
Despite being busy with classes, I finished the division function. All that remains is testing, corrections, optimizations, etc.

03-24-03
Began rigorous testing. Error found when subtracting numbers like 1000000 and 1 (result had non-digits) problem is probably in Huge_Int. Also, I think I'm going to implement a normalization function that will cut off the trailing zeros and increment the exponent accordingly. I also want it to force a single zero result, that is, zero will be represented by 0x10^0. This might require that I make Huge_Real a friend of Huge_Int (for efficiency reasons), or I suppose I could implement a Divide_By_Radix() function that would provide almost the efficiency I want.

03-25-03
The problem was, in fact, in Huge_Int. A simple sign error. I decided that a Div_By_Radix() function had less coupling than making Huge_Real a friend class, but I also need to 'see' the first digit of the mantissa, another function to implement in Huge_Int. Normalize for Huge_Real implemented. I also added to Huge_Real accessor functions to the exponent and mantissa components.

04-06-03
Most testing is complete. One problem I'm having is with repeating decimals that have leading zeros. I might need to change the index to a signed value so I can give negative values. (e.g. 1e0/77e-10 results in 12987e4 repeating index 0, which is wrong. The index should be -1, indicating the existence of a zero at the beginning. I don't anticipate this will be difficult to fix.
I also decided that I should add a function that will round to a particular decimal place. Another I need to add is functionality that will handle operations on repeating decimals. (e.g. How to add 0.3 repeating and 0.012987 repeating?) This might be non-trivial.

04-29-03
Indexing works properly now. I did some preliminary tests for timing. The results? Huge_Int multiplication is slow, but it could be improved by changing to Strassen's algorithm for fast multiplication, which is O(n^2.7) instead of O(n^3). I could also change back to my old representation instead of layering over String<T>. Also, the Huge_Real class could just include of different file with a different Huge_Int that has already been designed for fast computations. As long as the typical operations for integers are present, the Huge_Real implementation will still work. So, other than optimizations, the Huge_Real project is done.

Findings and Contributions:

So far...this project is bigger than it sounds is what I've found.

Representing a Huge_Real in a way that is similar to IEEE floating point numbers makes coding the operations much easier. All I need to have is a fully working Huge_Int class.

Since my Huge_Int class doesn't have "leading zeros", I'll have to do some modification to the IEEE methods of handling floating point numbers.

Modular arithmetic is underrated.

There's a big difference between O(n^2.7) and O(n^3).

Links and References:

<none>

  Return to Europa