Re: [boost] Infinite precision integer draft

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-05-28 08:31:35

Jarrad,
Here is what I have added:

explicit integer( const std::string & arg,
   radix_type radix );
Effects: Constructs an object of class integer
  with the value of string arg.
  Notation with base radix is assumed,
  where 2<=radix<=36; otherwise the
  string constructor with no radix parameter
  is used. For radix > 10, the letters may be
  uppercase or lowercase.
Postconditions: to_string( integer( arg, radix ),
  radix ) == arg.
Throws: invalid_input_error when the string
  does not consist of only numbers (or letters)
  of base radix, possibly headed by a + or - sign.
Complexity: O(M(N)log(N))

const std::string to_string( const integer & arg,
  radix_type radix );
Returns: The value of arg converted to
  std::string. Notation with base radix is
  assumed, where 2<=radix<=36; otherwise
  decimal notation is assumed. For radix>10,
  the letters are lowercase.
Postconditions: integer( to_string( arg, radix ),
  radix ) == arg.
Complexity: O(D(N)log(N))

bool is_odd() const;
Returns: ( *this & 1 ) == 1
Complexity: O(1)
Notes: This is equivalent to lowest_bit() == 0

size_type highest_bit() const;
Returns: The bit number of the highest set bit.
Throws: invalid_argument_error when *this == 0
Remarks: The bit numbering starts with zero.
   The result is independent of sign.
Complexity: O(N)

size_type lowest_bit() const;
Returns: The bit number of the lowest set bit.
Throws: invalid_argument_error when *this == 0
Remarks: The bit numbering starts with zero.
  The result is independent of sign.
Complexity: O(N)

const integer get_sub( size_type startbit, size_type nbits ) const;
Returns: The sub integer with the nbits bits
   starting with bit number startbit.
Remarks: The bit numbering starts with zero.
   The result is independent of sign.
Complexity: O(N)
Notes: The return value is as if the integers are padded
   with zeros to infinity. This means that the result is 0
   when startbit > highest_bit().

Also I have replaced the rhs shift parameters of the
shift operators to size_type.

Let me know if there are any comments.
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
>