On 11/26/06 8:58 AM, "Tobias Schwinger" <tschwinger@neoscientists.org> wrote:
Daryle Walker wrote:
This is something I've been working on for the past few months. It's in the Sandbox and I just uploaded it to the new Vault as "big_radix_whole.tar.bz2" under the "Math - Numerics" directory, i.e. <http://www.boost-consulting.com/vault/index.php?action=downloadfile&filenam e=big_radix_whole.tar.bz2&directory=Math%20-%20Numerics&>.
Very cool!
Thanks.
The only documentation right now is the Doxygen comments.
But most importantly the code reads nice. It would probably read even better without those comments ;-).
Theoretical purity was a consideration, so I tried to avoid being obscure. It also helps in portability concerns. The comments are there so I could make each function concrete in my mind before writing it. I don't have a rationale right now, so I didn't need separate documentation for the functions themselves if I used Doxygen. Later, I could reserve separate docs, probably with QuickBook, just for the rationale and user guide.
Many of the operations are repeated, each with optimized algorithms for the different sizes of the parameters. Since the traditional method of multiplication is actually a fused-add/multiply, member functions for such fused actions were added. There are many variants for shifting-up where additions/subtractions start since it's faster than doing a separate shifting operation first. And it saves memory, which was an important goal in all the algorithms, along with the strong exception guarantee.
Did you consider using expression templates to
- eliminate temporaries in expressions - detect temporaries to use in-place operations instead of copying ones, IOW exploiting destructibility of values - decorate the allocator for stack-based allocation during evaluation - replacing widening conversion operations with views
?
No. An type aided with expression templates eventually has to forward to some algorithms somewhere. I substituted for that by having member functions that combine operations together. Only operations that can be reasonably combined are done; operations that can interfere with each other aren't combined. That's why division and modulus don't combine with anything besides each other. However, a class like mine can be used as the implementation class for something that does use expression templates! Also, expression templates would interfere with presenting the code clearly (for educational purposes).
The last point of the above list can probably be implemented with a "hollow base", CRTP and deduce-from-base instead of ET (similar to polymorphism of parsers in Spirit).
What's CRTP stand for?
The ET approach could also be used to implement interesting syntactic properties. I once wrote a Wiki page about it:
I've read that page. I got some of my ideas from it (like the memory management at the end).
The information in the above section of my post is probably not too properly explained - please ask specific questions in case you are interested in something that seems mysterious.
... What other routines should be added?
Logarithm
Natural logarithm and/or any base? How can it be done, especially since I would be limited to integer arithmetic and results? I only have access to Knuth's _The Art of Computer Programming_ books, Wikipeida, plus occasional bignum pages I see on the web. I don't have access to the ACM/IEEE stuff, where I suspect a lot of "kewl" algorithms live.
Should there be Serialization?
Yes. Especially for Base64 encoding.
Could Spirit and/or Regex be used for the I/O routines?
Given these two alternatives I'd prefer Spirit for header-only code:
// schematic, untested code
typedef big_radix_whole<Rx,Al> value_type;
value_type result;
uint_parser< value_type, 10 > dec_ap; uint_parser< value_type, 16 > hex_ap; uint_parser< value_type, 8 > oct_ap; uint_parser< value_type, 2 > bin_ap;
if (! parse(first,last, // or some char* instead // this expression could be statically initialized // for optimization "0x" >> hex_ap [ var(result) = arg1 ] | "0b" >> bin_ap [ var(result) = arg1 ] | "0" >> oct_ap [ var(result) = arg1 ] | dec_ap [ var(result) = arg1 ] ).full) throw some_error;
But it might be faster to just hand-code the whole thing (in particular to avoid copying), I figure.
One key point of my type is that it specifies the radix at compile-time, to take full advantage of that, I/O is always done in that radix. This code here seems to be fixed at radix-8/10/16, probably using the appropriate I/O flags. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com