"Andras Erdei" <aerdei@gmail.com> wrote in message news:7fe28deb0605310758v59be5dbex545b04a8f7a08ce3@mail.gmail.com...
On 5/30/06, Rene Rivera <grafik.list@redshift-software.com> wrote:
const integer get_sub( size_type startbit, size_type nbits ) const; Complexity: O(N)
There are a few problems with using those for "binary" access:
* It is not optimal. Using the above would result in an O(N^2) algo for something that most of the time would be an O(1) operation (depending on the internal representation, at worse would be O(N)).
* The representation that get_sub, highest_bit, lowest_bit, operate on is not defined. I don't see such a definition in the document either, AFAICT. So one couldn't even use the faster "int x = to_int(I.get_sub(0,16));"
I don't care that much what the form of access looks like. The important aspect is having a *defined representation* that users can convert to and from. For example other access methods might be:
What can that defined representation be? I think it's the same question as: How would one represent an integer internally? (Earlier in this thread you mentioned that you would like to have this kind of access for performance reasons: eficiently implementing operations not supported by a stock integer.)
For a high performance assembly implementation on an intel uP it can be a block of 32 bit words.
For a resonably portable C++ implementation targeting the same uP it would be the same, except that only 31 bits are used, because in C(++) you do not have access to the carry flag, so you pay with memory for speed.
For a portable implementation we can use unsigned int 32-bit access, and use the 64-bit unsigned long long or unsigned __int64 and use these to have a 32-bit additive or multiplicative carry. This assumes of course that a 32-bit and 64-bit unsigned are available, which must be checked somehow during compilation. This is of course slower than assembler.
Chosing any of these as the standardized one would force the other to create an O(N) interface for your "implementation access".
If your operations are complex enough, and you can live with the above O(N) functions, let's go further:
How about a negabinary (base -2 instead of base 2) representation? How about a non-binary representation with O(M(N)*logn(N)) access? How about a non positional representation with O(N^3) access?
Either you seriously restrict the range of representations, and possibly render the best ones non-standard, or you end up with an "implementation access" that is unusable for your purpose.
The requirement is only that the sign and the binary representation of the absolute value are stored separately so that bit access (get_sub) has uniquely defined behaviour. So the binary representation will never be negative. Indeed this restricts the range of representations to this one.
// Iterators, like std::string::data:
std::pair<word_type const *, word_type const *> integer::data() const;
This also raises memory handling issues: i suppose the pair would contain an begin and an end pointer -- who would own the memory? What about integers with user-defined allocators?
br, andras _______________________________________________ Unsubscribe & other changes: