Re: [boost] Yet another bignum type

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2006-11-27 18:14:11

Daryle Walker wrote:
>>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).

I see.

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

It's the Curiously Recurring Template Pattern (some code attached). 

You can make a base class know its dervied class by specializing a base class template with the derived type. This way you can use static_cast to downcast the 'this' pointer and implement compile time polymorphism. I gave a code example in reply to Maarten Kronenburg.

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

> Natural logarithm and/or any base?  

log_Radix is there already and it's called digit_count(), isn't it?

Base N where N is an integer would be useful (e.g. to deal with tree structures larger than main memory).

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

Well, I don't have a really cool algorithm in my pocket. What follows is possibly amateurish intuitive guessing - there are probably better algorithms around (probably even in Knuth's TAOCP). Anyway, I'll give it a try:

Let's first look at cases where things are easy:

    Given Radix = pow(b_r,n), where b_r,n are integers 
    log_b_r(x) = log_Radix(x)*n + log_b_r(most_significant_digit(x))

Example:
    Radix = 256
    b_r = 2, n = 8
    log_2(550) = 1*8 + 1 = 9

For some Radix/base combination things can be put to work real smoothly. 
BTW. it seems possible to calculate b_r and n at compile time.

Another good thing to check is probably b > x in this case we can just return 0.

For other cases (and for the single digit, above) we pick a rather lame algorithm:

    int log(int b, int x)
    {
        int r = 0; for (int y = 1; y < x; y *= b, ++r);
        return r;
    }

Now the question is: "Can we estimate a value less than the result so we can let (r,y) start at (r_0,pow(b,r_0))?"

It might work to use the least base logarithm we have a special case for (called log_b_r, above - that would be log_Radix, worst case) to do the estimation. Basically the log_a(x) = log_b(x) / log_b(a) sort of thing, while we have to make sure we never over-estimate the result.

<snip>

[ ... Spirit code ... ]

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

It's just a number parser (it matches strings such as "42", "0xcafe" or "077"). It should work with any radix for the destination, but there will be a conversion, of course. Since you mentioned Serialization, I figured that the only IO left would be initialization from human readable form...

Regards,

Tobias


template<typename Derived>
struct base
{
  void caller
  {
    static_cast<Derived*>(this)->compile_time_polymorphic();
  }

  void compile_time_polymorphic() 
  {
    // default implementation
  }
}

struct derived : base<derived>
{
  void compile_time_polymorphic()
  {
    // override
  }
}


#include <iostream>

template<class Derived> 
struct crtp_base
{ 
  Derived & derived() 
  { return *static_cast<Derived*>(this); }

  Derived const & derived() const
  { return *static_cast<Derived const *>(this); }
};

class concrete_class
  : public crtp_base<concrete_class>
{ 
  int val_state;
public:
  concrete_class(int v)
    : val_state(v)
  { }

  int get_state() const 
  { return val_state; }
};

template<class Derived>
void func(crtp_base<Derived> const & arg)
{
  std::cout << "value == " << arg.derived().get_state() << std::endl;
}

int main()
{
  func( concrete_class(42) );
  return 0;
};