Re: [boost] Infinite precision integer draft

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-05-27 14:36:33

Jarrad,
Thanks for your comments.
There is no downloadable implementation yet
because for obvious reasons I would like to wait
until the design is finished.
The is_odd() is kept, but the is_even() is deleted
as it is equivalent to ! is_odd().
String constructor and converter are added for
a radix up to 36, like itoa:
explicit integer( const std::string &arg, unsigned int radix );
const std::string to_string( const integer &arg, unsigned int radix );
where 2<=radix<=36, otherwise other string constructor
or converter is assumed.
No unsigned char is used because some day some notation
for any radix > 256 may be invented.
The arguments of get_sub are integers, because the bit
factor 8 is not theoretical with current memory sizes.
Users may also use integers to hold bit patterns
of any size and use only shift and bitwise operators,
in combination perhaps with your get_sub!
The performance hit will be negligible, because
making the result will cost much more.
But in the design decisions I state that implementations
may add overloads (for example to your unsigned long),
though this is not required.
The division method that does / and % at the same
time is present, see divrem under arithmetic
non-member functions, and is indeed used for
reading and writing integers.
Creating integers with variable size on the stack,
that is in any case something that I will not
specify, but users that want to use these tricks
can just override the integer_allocator.
About performance of signed and unsigned
integers: my guess is that there will not be much
difference. Users can derive integer to make an
unsigned_integer, but they can also decide
to use integer and let the values never get negative.
The last option is of course a little faster.
About windows and GMP and boost:
in my opinion there has to be a good interface
first, and in any case you help reaching that point.
Regards, Maarten.

"Jarrad Waterloo" <jwaterloo_at_[hidden]> wrote in message
news:20060526133837.D30D42708024_at_dqmail.dynamicquest.com...
> 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!
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>