The history of the package Big_Number
Last revised : July 8, 2001
Back to my home page
Why this package?
In 1986, I was working on a Pascal program which allows to solve a system of linear equations with integer coefficients. It works well in some particular situations, but there was a bug due to the fact that overflows were not detected with my compiler, so the program ends with false reported results. I was then working on assembly procedures to detect this overflows, but I had no way to work with real "big" integers. Then I stopped the development of this program.
Between 1994 and 1996, I was student in medicine but, during my leisure time, I got some lessons concerning the Ada programming langage.
I am very interested in Ada, because this langage has many features which are missing in Pascal, for example genericity and exceptions.
Then, in 1996, I begun my work on a package which could allow to work with large integers.
At that time, because of my poor knowledge concerning this kind of numerical algorithms, the development of this package was very slow.
Particularly, I had some problems in writing the algorithm of division. The first version that I considered to be "acceptable" (version 0.00) was dated May 1, 1998, but, by now, I still think that the actual version (0.21) can be improved.
Back to the top of this page
The different versions of this package
Version 0.00
This first beta version has not been released (May 1, 1998)
Version 0.01
This version is dated May 24, 1998 and was the first I released to some of my friends. There were a few minor speed optimizations.
After its release, I discovered that there was an error during the computation of the number PI, but the bugs were identified and corrected
only in the version 0.03.
Back to the top of this page
Version 0.02
This version 0.02, dated June 23, 1998, contains modifications of some algorithms (mainly functions "+", "-" and Big_Div, in the package
Unsigned_Number), in order to improve the speed.
This version has not been released because the bugs (discovered during the computation of the number PI) were not
corrected.
Back to the top of this page
Version 0.03
This version was dated August 30, 1999. I corrected the two bugs in the procedure Big_Div and some other minor bugs
(then, the number PI seems to be well computed). There are important speed optimizations in the "-" function of the
package Unsigned_Number (minor speed optimizations in some other algorithms).
I have added all the procedures for I/O in text files. Big_Unsigned and Big_Signed numbers can't be converted
to STRINGs (like in older versions of this package) because of size limitations of this type, but they can be converted
to UNBOUNDED_STRING. For all the I/O procedures, I use UNBOUNDED_STRINGs instead of STRINGs.
The function Float_in_UString2Fraction has been added in the package Fraction : it allows to convert a real number
(contained in an INBOUNDED_STRING) to a fraction.
Back to the top of this page
Version 0.04
This version was dated September 26, 1999. The types Big_Signed, Big_Unsigned and Fraction are now private : it allows a better security,
by avoiding some illegal operations on these types.
As the variables of these three types can't be modified outside of the body of this package, all the redundant calls to the function Simplify_Fraction have been eliminated in the other functions of the "sub-package" Big_Fraction : this results in speed improvement.
There is a minor speed optimization in the function "/"(x, y : IN Fraction), and I started working on the package Big_Unsigned_Random
(which was included as comments).
Back to the top of this page
Version 0.05
This version was dated November 6, 1999 and was the first version released on Internet.
I made some speed optimizations in the procedure Big_Div(x, y : IN Big_Unsigned; Quot, Remainder : OUT Big_Unsigned) and in the function
"-"(x, y : IN Big_Unsigned) RETURN Big_Unsigned.
The function "+"(x, y : IN Fraction) has been rewritten and improved.
Back to the top of this page
Version 0.06
This version, dated December 22, 1999, was released while I was working on version 0.07.
It contains important speed optimizations in the procedure Big_Div(x, y : IN Big_Unsigned; Quot, Remainder : OUT Big_Unsigned).
Speed improvements have been done in the procedures Inc(x : IN OUT Big_Unsigned) and Dec(x : IN OUT Big_Unsigned), and
the procedures Inc(x : IN OUT Big_Signed) and Dec(x : IN OUT Big_Signed) have been added.
Back to the top of this page
Version 0.07
This version, dated February 20, 2000, provides speed optimizations in the functions "*"(x,y : IN Big_Unsigned) and "<"(x,y : IN Big_Signed).
A bug in the function "+"(x,y : IN Big_Unsigned) has been corrected.
In the procedure Big_Div(x, y : IN Big_Unsigned; Quot, Remainder : OUT Big_Unsigned), the algorithm of the function Guess has been
completely rewritten and is now smarter (there are no more intermediate computations on float numbers).
There are minor speed optimization in the functions "/"(x : IN Fraction; y : IN Big_Unsigned) RETURN Fraction and
"*"(x : IN Fraction; y : IN Big_Unsigned) RETURN Fraction.
I realized that the math packages concerning predefined float types was not necessary, so it has been removed.
The package Strings have been removed and its function Del_Spaces have been imported in Big_Number.String_Conversion :
all the other function from the package Strings were unnecessary. This allows shorter executables and faster compilation times with
my compiler (GNAT version 3.12).
There are new MAKEFILEs optimized for the different distributions of the GNAT compiler : this allow a better installation of this package
on different platforms.
In the examples, improvement of the third method to calculate the number PI.
Back to the top of this page
Version 0.08
This version, dated March 4, 2000, has been released since I have corrected a bug in the functions of conversion of STRING
and UNBOUNDED_STRING to Big_Unsigned and Big_Signed.
In the versions 0.04 to 0.07, there was a random number generator for Big_Unsigned which was only included as comments, because
I didn't tested it. It is now available, since I have corrected some bugs in it. I can't guarantee that the generated numbers are randomly
distributed.
I added the functions "AND"(x,y : IN Big_Unsigned) RETURN Big_Unsigned and "XOR"(x,y : IN Big_Unsigned) RETURN
Big_Unsigned.
Back to the top of this page
Version 0.09
This version, dated April 7, 2000, has been released since I have improved the portability of this package for different configurations (computer and/or compiler).
Back to the top of this page
Version 0.10
This version, dated April 22, 2000, has a correction in "-"(x, y : IN Big_Signed) RETURN Big_Signed : if x and y are equal and positive, the result is equal to 0 with a positive sign (in the previous version, the sign was negative, so the result was not equal to Big_Signed_Zero).
Back to the top of this page
Version 0.11
This version, dated April 25, 2000, has a corrected version of the function "<="(x, y : IN Big_Signed) RETURN BOOLEAN. Some errors in comments have been corrected.
Back to the top of this page
Version 0.12
In this version, dated May 7, 2000, there is a speed improvement of the procedure "Inc"(x : IN Big_Unsigned).
Back to the top of this page
Versions 0.13 and 0.14
These versions, dated respectively June 4, 2000 and June 11, 2000, provide some very minor speed improvement in the procedure Dec(x : IN OUT Big_Unsigned) and in the function "+"(x, y : IN Big_Unsigned) RETURN Big_Unsigned. I didn't released them because they were not tested completely.
Back to the top of this page
Version 0.15
In this version, dated July 17, 2000, I have corrected bugs in the function "**"(x : IN Fraction; y : IN My_Type) RETURN Fraction, in the procedures PUT(x : IN Fraction) and PUT(File : IN FILE_TYPE; x : Fraction), and in all the functions of the sub-package Generic_Conversion. An important speed improvement have been done in the function "**"(x : IN Fraction; y : IN Big_Unsigned) RETURN Fraction, and minor speed improvements have been done in the functions "/"(x : IN Fraction; y : Big_Signed) RETURN Fraction, Special_mul(x : IN Big_Unsigned; y : IN My_Type; Left_Shift : IN Index_Type) RETURN Big_Unsigned, "*"(x, y : IN Big_Unsigned) RETURN Big_Unsigned; Random(x : IN Big_Unsigned) RETURN Big_Unsigned; "<"(Left, Right : IN Fraction) RETURN BOOLEAN; "*"(x : IN Fraction; y : Big_Signed) RETURN Fraction; "+"(x, y : IN Fraction) RETURN Fraction; and "*"(x, y : IN Fraction) RETURN Fraction; and in the procedure Big_Div(x,y : IN Big_Unsigned; Quot,Remainder : OUT Big_Unsigned). The functions Opposite(x : IN Fraction) RETURN Fraction, Absolute(x : IN Fraction) RETURN Fraction and Is_Null(x : IN Fraction) RETURN BOOLEAN, and the procedures Get_Line(x : OUT Fraction) and Get_Line(File : IN FILE_TYPE; x : OUT Fraction) have been added, as some functions for statistics : NCR(x,y : IN Big_Unsigned) RETURN Big_Unsigned; NPR(x,y : IN Big_Unsigned) RETURN Big_Unsigned; and K(x,y : IN Big_Unsigned) RETURN Big_Unsigned.
Back to the top of this page
Version 0.16
In this version, dated August 21, 2000, I have not modified the package itself, but the three methods for calculating the number Pi have been improved a lot and are now much faster.
Back to the top of this page
Version 0.17
In this version, dated September 24, 2000, there are very small improvements in the functions "+"(x, y : IN Fraction) RETURN Fraction; and Short_Div(x : IN Big_Unsigned; y : IN My_Type; Quot : OUT Big_Unsigned; Remainder : OUT My_Type);.
Back to the top of this page
Version 0.18
This version, dated December 16, 2000 has a new function : Number_of_Bytes(x : IN Big_Unsigned) RETURN Largest_Unsigned.
Back to the top of this page
Version 0.19
In this version, dated December 29, 2000, there is a correction in the function Shift_Left(x : IN Big_Unsigned; Nb : IN Index_Type) RETURN Big_Unsigned.
Back to the top of this page
Version 0.20
In this version, dated January 24, 2001, there are corrections in the different methods to calculate the number Pi, where I added some missing files. I added the functions Number_of_bits(x : IN Big_Unsigned) RETURN Largest_Unsigned;, Number_of_bytes(x : IN Big_Signed) RETURN Largest_Unsigned; and Number_of_bits(x : IN Big_Signed) RETURN Largest_Unsigned;
Back to the top of this page
Version 0.21
In this version, dated March 4, 2001, there are corrections of 2 bugs in the function Float_in_UString2Fraction(). One was discovered and corrected by Young A.R., concerning an error about the sign of the result. I discovered and corrected the second one the same day, during the tests before the release : it was an error concerning the computation of the period of a float number.
Back to the top of this page
Version 0.22
In this version, dated March 12, 2001, I added a small improvement of the algorithm and a correction of a potential bug in the function Big_Div(x,y : IN Big_Unsigned; Quot,Remainder : OUT Big_Unsigned);.
Back to the top of this page
Version 0.23
In this version, dated April 14, 2001, I added an improvement of the speed, in some cases, of the algorithm of the function "<"(Left, Right : IN Fraction) RETURN BOOLEAN. The function Mod_Number2Big_Signed has been corrected : when the value is 0, the sign is always set to positive.
Back to the top of this page
Version 0.24
In this version, dated April 18, 2001, I added some new improvements of the speed of the algorithm of the function "<"(Left, Right : IN Fraction) RETURN BOOLEAN.
Back to the top of this page
Version 0.25
In this version, dated April 30, 2001, I added one modification of the algorithm of the function "<"(Left, Right : IN Fraction) RETURN BOOLEAN. I have corrected a bug in the functions Opposite(x : IN Big_Signed) RETURN Big_Signed; and Opposite(x : IN Fraction) RETURN Fraction;
Back to the top of this page
Version 0.26
In this version, dated June 16, 2001, I have simplified and optimized the algorithm of the function "-"(x, y : IN Big_Signed) RETURN Big_Signed. I have introduced a very small modification in the function "+"(x, y : IN Fraction) RETURN Fraction;
Back to the top of this page
Version 0.27
In this version, dated June 25, 2001, I have optimized the algorithm of the procedure Dec(x : IN OUT Big_Signed) and I have corrected 2 bugs in the procedure Inc(x : IN OUT Big_Signed);
Back to the top of this page
Version 0.28
In this version, dated July 8, 2001, I have added a very small optimization of the function "+"(x, y : IN Big_Signed) RETURN Big_Signed; and I have corrected 2 bugs in the function "<"(Left, Right : IN Big_Signed) RETURN BOOLEAN;
Back to the top of this page
What do I plan to do?
There are many things that could be done in this package. This includes, for example, new functions and procedures for cryptography, speed improvements, and smarter data structures : each instanciation of this package allows to use only one size for Big_Unsigned, Big_Signed or Fraction.
Back to the top of this page