Re: [boost] Infinite precision integer draft

From: Rene Rivera (grafik.list_at_[hidden])
Date: 2006-06-01 22:20:27

Andras Erdei wrote:
> On 5/30/06, Rene Rivera <grafik.list_at_[hidden]> 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 don't really care. But it could be the same representation used by the 
machine architecture for the int type, but extended to fit the number. 
Like the Java BigInt produces for example 
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html#toByteArray()>. 
Or what Maarten suggests on some other post.

> I think it's the same question as: How would one represent an integer
> internally?

No at all.

> (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.)

I said "optimal". Which for most operations would be O(N), possible 
O(logN) at best. My point is that having an operation take O(N^2) 
because of a bad design is, well, bad design :-) For whatever 
representation is provided other would have to translate to/from it.

> // 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

That's what the above says.

> -- who would own the memory?

Just like string, the integer would own the memory. That's why I put 
"const" above. It's a standard idiom.

> What about
> integers with user-defined allocators?

Why would that matter? The allocator just manages memory. It's up to the 
integer to decide what to do with it. Again, look at std::string as an 
example.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo