[boost] Infinite precision integer draft

From: Jarrad Waterloo (jwaterloo_at_[hidden])
Date: 2006-05-26 09:47:19

Thank you for considering sub integers. Do you have a downloadable
implementation of integer ready for people to play with? Where?
Here are some final thoughts to consider?

Revisions:

> 1) The ability to extract sub integers out of an integer such as the
integer
> at bit offset 3 and length of 4. This is especially helpful in the area of
> RFID where large unsigned integers are partitioned into smaller integers.
>> As a response for a request for sub integers,
>> in the document I will delete the is_even
>> and is_odd member functions, and add:
>> const integer highest_bit() const;
>> const integer lowest_bit() const;
>> const integer get_sub( const integer &, const integer & ) const;

I would keep is_even and is_odd for performance and ease of use reasons
because if highest_bit and lowest_bit represents a single bit than logically
it should return a bool. Further, get_sub should have the following more
frequently used overload.
const integer get_sub( const unsigned long &, const unsigned long & ) const;
This function is easier to use with constants, faster because of no
conversions to heavier objects and the most commonly used case because even
though infinite precision integers can have infinity of bits it is very
unlikely that generally users will have a sub integer at offset 4 billion of
length 4 billion. What number would that reprensent! Doesn't the number of
atoms in the known universal end before 256 bits! Anyway my point repeated
throughout is ease of use to the user of the library with the best speed
using the least memory even if it means making a library slightly more
complex with extra commonly used methods or objects.

> 2) The ability to convert integer to bases other than base 10; any 
> really from base 2-36
>> The iostreams of the compilers I know only alow bases 8, 10 and 16,
>> see also [lib.std.manip] setbase manipulator.
>> The bases 2, 4, 5 can be easily converted from these bases.
>> The other bases don't seem to have a useful application; they are
>> also not supported for base type int, and not supported by printf
>> formats or stream manipulators.

itoa does take radix at runtime instead of a enumeration compile time
constant. As such I was hoping the following methods were added.
const std::string to string(const integer & arg, const unsigned char radix)
{
// the implementation could use the algorithm where
// the value is divided by the radix
// the remained is pushed onto a stack of characters
// and the dividend is fed back into this process until it is 0
}
Obviously it would be nice to have a constructor that could reverse this
process. This method may perform better if there was a division method that
does / and % at the same time. Whether or not these methods should be member
functions instead of external or both is something I leave to be debated
among OOP experts.

> 3) An implementation of a fixed sized stack version of the 
> integer_allocator. This may be useful for performance when someone is 
> not working with an infinite precision integer but a very large one 
> such as 512 or 1024 bits.
>> Users can implement such an allocator by deriving from integer_allocator,
>> override and implement allocate, reallocate and deallocate,
>> and activate it.

Yes users can do this themselves but if this is something that would be
frequently considered or built by users than it might be better to go ahead
and make this library even more robust by providing it up front. Further if
this library is to behave like native int that can be created on the stack
and the heap than it would still be part of your architecture to allow
integer to be created on the stack and heap.

> 4) An unsigned version of the integer class that benefits from the 
> higher performance of unsigned operations
>> Users can implement an unsigned_integer by deriving from integer,
>> but this will not give any performance gain.
>> By the way I think base type unsigned int is also not faster
>> than base type int.

Yes users can do this themselves but if this is something that would be
frequently considered or built by users than it might be better to go ahead
and make this library even more robust by providing it up front.
Secondly, I had thought that a CPU processes unsigned faster than signed and
having evaluated the code of other C++ integer libraries the code for
unsigned was less than for signed. However, I am no expert so I could be
wrong on this performance question. As my first thought, people are in need
of this library now as a boost library or a preliminary boost library
because most other libraries have awful license or is too difficult to build
in a windows environment as is the case of GMP. Help!