Re: [boost] Yet another bignum type

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2006-11-26 08:58:45

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!

> 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 ;-).

> 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

?

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). 

The ET approach could also be used to implement interesting syntactic properties. I once wrote a Wiki page about it:

    http://tinyurl.com/qtyhh

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

> 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.

Regards,

Tobias