bigint-2010.04.30
[bigint/bigint.git] / ChangeLog
1                                    Change Log
2
3 These entries tell you what was added, fixed, or improved in each version as
4 compared to the previous one.  In case you haven't noticed, a version number
5 roughly corresponds to the release date of that version in `YYYY.MM.DD[.N]'
6 format, where `.N' goes `.2', `.3', etc. if there are multiple versions on the
7 same day.  The topmost version listed is the one you have.
8
9 2010.04.30
10 ----------
11 - Strengthen the advice about build/IDE configuration in the README.
12
13 2009.05.03
14 ----------
15 - BigUnsigned::{get,set}Bit: Change two remaining `1 <<' to `Blk(1) <<' to work
16   on systems where sizeof(unsigned int) != sizeof(Blk).  Bug reported by Brad
17   Spencer.
18 - dataToBigInteger: Change a `delete' to `delete []' to avoid leaking memory.
19   Bug reported by Nicol├ís Carrasco.
20
21 2009.03.26
22 ----------
23 - BigUnsignedInABase(std::string) Reject digits too big for the base.
24   Bug reported by Niakam Kazemi.
25
26 2008.07.20
27 ----------
28 Dennis Yew pointed out serious problems with ambiguities and unwanted
29 conversions when mixing BigInteger/BigUnsigned and primitive integers.  To fix
30 these, I removed the implicit conversions from BigInteger/BigUnsigned to
31 primitive integers and from BigInteger to BigUnsigned.  Removing the
32 BigInteger-to-BigUnsigned conversion required changing BigInteger to have a
33 BigUnsigned field instead of inheriting from it; this was a complex task but
34 ultimately gave a saner design.  At the same time, I went through the entire
35 codebase, making the formatting and comments prettier and reworking anything I
36 thought was unclear.  I also added a testsuite (currently for 32-bit systems
37 only); it doesn't yet cover the entire library but should help to ensure that
38 things work the way they should.
39
40 A number of changes from version 2007.07.07 break compatibility with existing
41 code that uses the library, but updating that code should be pretty easy:
42 - BigInteger can no longer be implicitly converted to BigUnsigned.  Use
43   getMagnitude() instead.
44 - BigUnsigned and BigInteger can no longer be implicitly converted to primitive
45   integers.  Use the toInt() family of functions instead.
46 - The easy* functions have been renamed to more mature names:
47   bigUnsignedToString, bigIntegerToString, stringToBigUnsigned,
48   stringToBigInteger, dataToBigInteger.
49 - BigInteger no longer supports bitwise operations.  Get the magnitude with
50   getMagnitude() and operate on that instead.
51 - The old {BigUnsigned,BigInteger}::{divide,modulo} copy-less options have been
52   removed.  Use divideWithRemainder instead.
53 - Added a base argument to BigUnsignedInABase's digit-array constructor.  I
54   ope no one used that constructor in its broken state anyway.
55
56 Other notable changes:
57 - Added BigUnsigned functions setBlock, bitLength, getBit, setBit.
58 - The bit-shifting operations now support negative shift amounts, which shift in
59   the other direction.
60 - Added some big-integer algorithms in BigIntegerAlgorithms.hh: gcd,
61   extendedEuclidean, modinv, modexp.
62
63 2007.07.07
64 ----------
65 Update the "Running the sample program produces this output:" comment in
66 sample.cc for the bitwise operators.
67
68 2007.06.14
69 ----------
70 - Implement << and >> for BigUnsigned in response to email from Marco Schulze.
71 - Fix name: DOTR_ALIASED -> DTRT_ALIASED.
72 - Demonstrate all bitwise operators (&, |, ^, <<, >>) in sample.cc.
73
74 2007.02.16
75 ----------
76 Boris Dessy pointed out that the library threw an exception on "a *= a", so I changed all the put-here operations to handle aliased calls correctly using a temporary copy instead of throwing exceptions.
77
78 2006.08.14
79 ----------
80 In BigUnsigned::bitXor, change allocate(b2->len) to allocate(a2->len): we should allocate enough space for the longer number, not the shorter one!  Thanks to Sriram Sankararaman for pointing this out.
81
82 2006.05.03
83 ----------
84 I ran the sample program using valgrind and discovered a `delete s' that should be `delete [] s' and a `len++' before an `allocateAndCopy(len)' that should have been after an `allocateAndCopy(len + 1)'.  I fixed both.  Yay for valgrind!
85
86 2006.05.01
87 ----------
88 I fixed incorrect results reported by Mohand Mezmaz and related memory corruption on platforms where Blk is bigger than int.  I replaced (1 << x) with (Blk(1) << x) in two places in BigUnsigned.cc.
89
90 2006.04.24
91 ----------
92 Two bug fixes: BigUnsigned "++x" no longer segfaults when x grows in length, and BigUnsigned == and != are now redeclared so as to be usable.  I redid the Makefile: I removed the *.tag mechanism and hard-coded the library's header dependencies, I added comments, and I made the Makefile more useful for building one's own programs instead of just the sample.
93
94 2006.02.26
95 ----------
96 A few tweaks in preparation for a group to distribute the library.  The project Web site has moved; I updated the references.  I fixed a typo and added a missing function in NumberlikeArray.hh.  I'm using Eclipse now, so you get Eclipse project files.
97
98 2005.03.30
99 ----------
100 Sam Larkin found a bug in `BigInteger::subtract'; I fixed it.
101
102 2005.01.18
103 ----------
104 I fixed some problems with `easyDataToBI'.  Due to some multiply declared variables, this function would not compile.  However, it is a template function, so the compiler parses it and doesn't compile the parsed representation until something uses the function; this is how I missed the problems.  I also removed debugging output from this function.
105
106 2005.01.17
107 ----------
108 A fix to some out-of-bounds accesses reported by Milan Tomic (see the comment under `BigUnsigned::divideWithRemainder').  `BigUnsigned::multiply' and `BigUnsigned::divideWithRemainder' implementations neatened up a bit with the help of a function `getShiftedBlock'.  I (finally!) introduced a constant `BigUnsigned::N', the number of bits in a `BigUnsigned::Blk', which varies depending on machine word size.  In both code and comments, it replaces the much clunkier `8*sizeof(Blk)'.  Numerous other small changes.  There's a new conversion routine `easyDataToBI' that will convert almost any format of binary data to a `BigInteger'.
109
110 I have inserted a significant number of new comments.  Most explain unobvious aspects of the code.
111
112 2005.01.06
113 ----------
114 Some changes to the way zero-length arrays are handled by `NumberlikeArray', which fixed a memory leak reported by Milan Tomic.
115
116 2004.12.24.2
117 ------------
118 I tied down a couple of loose ends involving division/modulo.  I added an explanation of put-here vs. overloaded operators in the sample program; this has confused too many people.  Miscellaneous other improvements.
119
120 I believe that, at this point, the Big Integer Library makes no assumptions about the word size of the machine it is using.  `BigUnsigned::Blk' is always an `unsigned long', whatever that may be, and its size is computed with `sizeof' when necessary.  However, just in case, I would be interested to have someone test the library on a non-32-bit machine to see if it works.
121
122 2004.12.24
123 ----------
124 This is a _major_ upgrade to the library.  Among the things that have changed:
125
126 I wrote the original version of the library, particularly the four ``classical algorithms'' in `BigUnsigned.cc', using array indexing.  Then I rewrote it to use pointers because I thought that would be faster.  But recently, I revisited the code in `BigUnsigned.cc' and found that I could not begin to understand what it was doing.
127
128 I have decided that the drawbacks of pointers, increased coding difficulty and reduced code readability, far outweigh their speed benefits.  Plus, any modern optimizing compiler should produce fast code either way.  Therefore, I rewrote the library to use array indexing again.  (Thank goodness for regular-expression find-and-replace.  It saved me a lot of time.)
129
130 The put-here operations `divide' and `modulo' of each of `BigUnsigned' and `BigInteger' have been supplanted by a single operation `divideWithRemainder'.  Read the profuse comments for more information on its exact behavior.
131
132 There is a new class `BigUnsignedInABase' that is like `BigUnsigned' but uses a user-specified, small base instead of `256 ^ sizeof(unsigned long)'.  Much of the code common to the two has been factored out into `NumberlikeArray'.
133
134 `BigUnsignedInABase' facilitates conversion between `BigUnsigned's and digit-by-digit string representations using `std::string'.  Convenience routines to do this conversion are in `BigIntegerUtils.hh'.  `iostream' compatibility has been improved.
135
136 I would like to thank Chris Morbitzer for the e-mail message that catalyzed this major upgrade.  He wanted a way to convert a string to a BigInteger.  One thing just led to another, roughly in reverse order from how they are listed here.
137
138 2004.1216
139 ---------
140 Brad Spencer pointed out a memory leak in `BigUnsigned::divide'.  It is fixed in the December 16, 2004 version.
141
142 2004.1205
143 ---------
144 After months of inactivity, I fixed a bug in the `BigInteger' division routine; thanks to David Allen for reporting the bug.  I also added simple routines for decimal output to `std::ostream's, and there is a demo that prints out powers of 3.
145
146 ~~~~