From: Daryle Walker (darylew_at_[hidden])
Date: 2006-11-26 17:55:09
On 11/26/06 8:58 AM, "Tobias Schwinger" <tschwinger_at_[hidden]>
> 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.
> Very cool!
>> 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?
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 ]
> 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
-- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk