
Boost : 
From: james.jones_at_[hidden]
Date: 20070212 12:18:35
From: Alec Ross <alec_at_[hidden]>
>In message <7384990EC1040E4C8BC31CADFFDD428001C2A304_at_cedarrapids>,
>james.jones_at_[hidden] writes
>>From: Andreas Harnack <ah.boost.02_at_[hidden]>
>...
>>> You're right, there is a computational limit, but I wouldn't expect to
>>> a see a dimension with the power of 31. Exponends of 4 are about the
>>> highest I've ever seen, and (2*3*5*7*11*13*17)^3 still fits in 57 bits,
>>> so we might want to use long or even long long unsigned ints, but that
>>> should be fine for most situations.
>>
>>If exponents of 4 are the highest you've seen, shouldn't you consider
>>the size of (2*3*5*7*11*13*17)^4, which requires 76 bits?
>
>But ISTM that this information could be given by a sequence of powers
>for each prime in the sequence: ie 4 bits * 7 in this second example.
>What am I missing?
Then why use primes at all? In this case, we're just storing a pattern of bits that represents a list. The purpose of storing the product is that the values can be manipulated using ordinary arithmetic, i.e. the calculation (m/s^2) * (kg/m) = kg/s^2 would be represented as (for example) 3/2^2 * 5/3 = 5/2^2. (I should note that at least some of the computational advantages of this scheme over lists are lost when it becomes necessary to compute the l.c.d. and reduce the fractions. No idea whether this is a deal breaker, though.)
If you store the exponents as bit patterns, then you can certainly be more spaceefficient, but then the manipulations don't use ordinary arithmetic. However, considering that this scheme has the same disadvantage (less flexibility) as using primes, and seems to be more spaceefficient... and also *might* be more timeefficient, maybe it should be considered as a possible alternative implementation, at least for benchmarking purposes.
Alec, want to implement this?

James Jones Administrative Data Mgmt.
Webmaster 375 Raritan Center Pkwy, Suite A
Data Architect Edison, NJ 08837
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk