on 02.05.2010 at 20:48 Chad Nelson wrote :
I'm curious: Are you researching, or do you have plans to research, more efficient multiplication algorithms (Karatsuba's, FFT-based, etc.)? I believe these only become efficient at large integers, but I'm not sure how large...
Yes, I already have a description of the Karatsuba one to work from, for a later release. It's supposed to be more effective than the traditional version once you get past a certain size, but I don't know what that size is yet. Once that's added, I'll look into the others.
wikipedia says that kartsuba gains any advantage starting from ~10000 _decimal_ digits (that is roughly )
Okay, some questions regarding the arithmetic functions: It looks like you have named free functions for all the arithmetic operators which have identical functionality to the overloaded arithmetic operators. This was obviously deliberate. Can you comment on this decision, i.e., why have the named free functions at all?
Originally those were the functions that handled the internals. I had to move the internals down by another layer of abstraction in order to efficiently handle the fixed_integer types, and I just never thought to remove the free functions.
Do you have free functions that implement the low-level arithmetic operations for just pairs of pointers? [...]
Not pairs of pointers, but I do have lower-level functions (the ones in the detail namespace) that work on base_integer types.
? Okay this signature is probably not what you'd want, but
[...] more fundamentally my question is, have you separated the arithmetic/numeric algorithms from the memory management algorithms?
They're separated, in that the memory management is all done by the base_integer class, and the math is handled by the higher classes and free functions.
Can one build their own, e.g., stack-based integer class as just a wrapper around the arithmetic algorithms?
Maybe, if one wants to implement all the free functions for their type. :-) I hadn't considered that anyone might want to.
Also, I don't see any allocator template parameters anywhere. I'm guessing any consideration of acceptance into boost is conditional on allocator support.
<sigh> I wish someone had mentioned that before. Not that it makes that much difference... while trying to add the data-caching stuff to the fixed_integer types last night, I came to the conclusion that I needed something like that anyway.
Very nice work on the documentation. I'll have to continue to troll through it at my usually leisurely pace.
Thanks!
-- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out