Boost logo

Boost :

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

    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.


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



template<typename Derived>
struct base
  void caller

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at