Re: [boost] Yet another bignum type

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]>
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:
> 
>   http://tinyurl.com/qtyhh

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