|
|
Boost : |
Subject: Re: [boost] [xint] Boost.XInt formal review
From: k.inaba (kiki_at_[hidden])
Date: 2011-03-03 12:42:32
This is just a quick question, not meant to be a full review.
The documentation says that the complexity of multiplication is O(n^2).
But as far as I know, there are asymptotically better algorithms
such as Karatsuba method O(n^1.585) or FFT O(n log(n) log(log(n))), etc:
http://en.wikipedia.org/wiki/Multiplication_algorithm
Are there any reason that these methods aren't used in XInt?
For large numbers, they work much faster than the textbook multiplication,
and they can be implemented perfectly portably in C++.
Kazuhiro Inaba.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk