AMDG On 06/30/2012 12:47 PM, Michael Tryhorn wrote:
Dear all,
Some responses to questions asked so far:
That can't be right. Addition of two n-bit numbers requires processing all n bits and is therefore O(n). The fastest known algorithm for multiplying two n-bit numbers is slower than O(n).
I may be wrong, but my understanding was that at least for an addition operation, while certainly implemented via adders in hardware (and hence O(n)), we would not call it so in algorithms that use it. Let me give an example. If I wrote a function thus:
int add_these(int a, int b) { return a+b; }
I would expect that rather than converting my '+' to a loop, the compiler would turn it into assembly 'LOAD/ADD/STORE'. My evaluation of the complexity of the above algorithm itself (if we can call it such) would be to label it 'O(1)' rather than 'O(n)'. For reference, let me quote the code from large_int::operator+= :
large_int<T, U>& large_int<T, U>::operator+= (const this_type& val) { // Take a copy of *this, to modify this_type ret(*this);
// Perform the addition ret.m_lo += val.m_lo; ret.m_hi += val.m_hi; if( ret.m_lo < m_lo ) { ++ret.m_hi; }
// Commit the result return( *this = ret ); }
Although a little more complex, additions should only ever perform a single pass of this function. As for multiplication, the operator*= implementation uses a for loop which loops at most 'n' times, where 'n' is the number of binary bits in the integer, making use of += (above) and the shift operators.
You're being inconsistent about whether the number of bits is a constant. The number of operations is O(d) where d is the number of built-in integers in the argument after expanding large_int recursively. Since the number of bits in a built-in integer type is a constant, O(d) = O(n). In Christ, Steven Watanabe