Boost logo

Boost :

Subject: Re: [boost] Large Integer Library
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-06-30 11:02:42


AMDG

On 06/30/2012 07:44 AM, Michael Tryhorn wrote:
> John/everyone,
>
> I have a few other features and benefits of the Boost.LargeInt library,
> which may preempt some questions. I'm not sure how Boost.Multiprecision
> compares on these specifically, but I thought they would help:
>
> * All logical, arithmetic and bitwise operators in Boost.LargeInt
> have constant, O(1) complexity; except for multiplication ('*'),
> division ('/') and modulus ('%') which are O(n) on the number
> of bits in the respective large_int type. Hence support for non
> power-of-2 large_ints of 96bits, 160bits or otherwise may
> be used to improve calculation performance.
>

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

In Christ,
Steven Watanabe


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk