3. Logarithmus oder lookup table fuer Templates zur Compiletime?

Logarithmus oder lookup table fuer Templates zur Compiletime?

  • I

    hmmm... wenn ich allerdings eine float konstante eintrage bei der berechnung, rechnet er mit dieser floating point konstante bsp:

    static int const foo = 10 / 1.5;

    foo = 6.

    Ich dachte da waere etwas möglich.... 😕

    0

  • Hm.
    Müsste sich lösen lassen indem du über ein Rekursives Template den minimalen/maximalen Wert des Typs so oft durch Radix dividierst bis irgendwann 0 rauskommt.
    Wobei der minimale/maximale Wert nicht so einfach zu bekommen ist, da numeric_limits<T>::min() und max() ja leider Funktionen und keine Konstanten sind.

    0
  • I

    hustbaer schrieb:

    Hm.
    Müsste sich lösen lassen indem du über ein Rekursives Template den minimalen/maximalen Wert des Typs so oft durch Radix dividierst bis irgendwann 0 rauskommt.
    Wobei der minimale/maximale Wert nicht so einfach zu bekommen ist, da numeric_limits<T>::min() und max() ja leider Funktionen und keine Konstanten sind.

    Sprich bitte weiter 🙂
    numeric_limits<T>::max() funktioniert auf jeden fall in const expressions.
    Wie kann ich denn rekursiv mit templates dividieren?

    0
  • M

    Um den maximalen Wert rauszukriegen, gibt es Boost.IntegerTraits. Ich sehe allerdings noch ein anderes Problem: Wenn value > numeric_limits<int>::max() ist, gibts nen Überlauf.

    Edit: Oh, es geht ja um die Anzahl der Stellen. Die wird wahrscheinlich in ein int reinpassen 😉

    0
  • M

    Ne grobe Idee wäre sowas (mir fällt nix Besseres ein):

    #include <iostream>
#include <limits>
#include <boost/integer_traits.hpp>
using namespace std;
using namespace boost;

typedef unsigned long long greatest_integral_type;

template<greatest_integral_type n, int base>
struct tmp_log
{
	static const int value = 1 + tmp_log<n/base, base>::value;
};

template<int base>
struct tmp_log<1, base>
{
	static const int value = 0;
};

template<int base>
struct tmp_log<0, base>
{
	static const int value = 0;
};

template<typename T, int base, int run = 1>
struct digits
{
	static const int value = 
		numeric_limits<T>::digits <= run * numeric_limits<greatest_integral_type>::digits ?
			(run - 1) * tmp_log<integer_traits<greatest_integral_type>::const_max, base>::value
				+ tmp_log<(integer_traits<T>::const_max >> ((run - 1) * numeric_limits<greatest_integral_type>::digits)), base>::value
		:
			digits<T, base, run + 1>::value;
};

int main()
{
	cout << digits<int, 2>::value;
}

    Leider schmiert mir der VC2008 dabei ab 😞 So ganz passt das auch noch nicht, aber ich denke, die Idee sollte man extrahieren können.

    Edit: Vielleicht hast du ja Lust, den größten Ganzzahltypen von Hand zu setzen. Dann löst sich der komplizierte Teil des Templates in Wohlgefallen auf.

    0

  • Ike schrieb:

    hustbaer schrieb:

    Hm.
    Müsste sich lösen lassen indem du über ein Rekursives Template den minimalen/maximalen Wert des Typs so oft durch Radix dividierst bis irgendwann 0 rauskommt.
    Wobei der minimale/maximale Wert nicht so einfach zu bekommen ist, da numeric_limits<T>::min() und max() ja leider Funktionen und keine Konstanten sind.

    Sprich bitte weiter 🙂
    numeric_limits<T>::max() funktioniert auf jeden fall in const expressions.

    Mit nem C++0x bewaffneten compiler schon, ja. Mit C++ 03 nicht.

    Wie kann ich denn rekursiv mit templates dividieren?

    Na so:

    #include <iostream>
#include <boost/static_assert.hpp>

// brauchen wir dann gleich
template <class T, T n, T base, bool n_greater_or_equal_base>
struct static_log_impl;

// unsere tolle TMP (template meta-programming) log funktion
template <class T, T n, T base>
struct static_log
{
	BOOST_STATIC_ASSERT(base > 1);
	BOOST_STATIC_ASSERT(n > 0);

	// log(n, base) ist...
	//    wenn n < base dann      0
	//    wenn n >= base dann     1 + log(n / base, base)
	//
	// in TMP-speak sieht das so aus:
	// (erstmal der "wenn" teil, der "dann" teil folgt sogleich)

	static int const value = static_log_impl<T, n, base, (n >= base)>::value;
};

template <class T, T n, T base>
struct static_log_impl<T, n, base, true>
{
	BOOST_STATIC_ASSERT(base > 1);
	BOOST_STATIC_ASSERT(n >= base);
	// hier kommen wir rein wenn n >= base. in dem fall rufen wir uns rekursiv auf:
	static int const value = 1 + static_log_impl<T, (n / base), base, ((n / base) >= base)>::value;
};

template <class T, T n, T base>
struct static_log_impl<T, n, base, false>
{
	BOOST_STATIC_ASSERT(base > 1);
	BOOST_STATIC_ASSERT(n > 0 && n < base);
	// hier kommen wir rein wenn base > n > 0. ergebnis ist dann trivial, nämlich 0.
	static int const value = 0;
};

// ein wenig testen:

#define TEST(type, base, n) \
	std::cout << "log" << type(base) << "(" << type(n) << ") = " << static_log<type, n, base>::value << "\n";

int main(int /*argc*/, char** /*argv*/)
{
//	TEST(int, 10, 0); // invalid, does not compile
//	TEST(int, 0, 10); // invalid, does not compile
//	TEST(int, 1, 10); // invalid, does not compile
	TEST(int, 10, 1);
	TEST(int, 10, 9);
	TEST(int, 10, 10);
	TEST(int, 10, 11);
	TEST(int, 10, 99);
	TEST(int, 10, 100);
	TEST(int, 10, 101);
	TEST(int, 10, 999);
	TEST(int, 10, 1000);
	TEST(int, 10, 1001);

	TEST(int, 2, 1);
	TEST(int, 2, 2);
	TEST(int, 2, 3);
	TEST(int, 2, 4);
	TEST(int, 2, 5);
	TEST(int, 2, 7);
	TEST(int, 2, 8);
	TEST(int, 2, 9);
	TEST(int, 2, 15);
	TEST(int, 2, 16);
	TEST(int, 2, 17);

	TEST(unsigned long long, 2, 1ull << 63ull);
	TEST(unsigned long long, 10, 1ull << 63ull);
}

    MSVC 2008 und 2010 fressen das und es kömmt sogar das richtige raus dabei.

    Das mit numeric_limits<>::max() zu verknüpfen überlasse ich dann mal dir.

    0

  • Wobei, wenn du nen C++0x compiler hast kannst du es gleich so schreiben:

    #include <iostream>

template <class T>
constexpr int my_log(T n, T base)
{
    return (n >= base) ?
        (1 + my_log(n / base, base))
        :
        0;
}

int main()
{
    static int const a = my_log(9999, 10);
    static int const b = my_log(10000, 10);
    std::cout << "log10(9999) = " << a << "\n";
    std::cout << "log10(10000) = " << b << "\n";
}

    MSVC 2010 frisst das (leider) noch nicht. GCC 4.5 mit den C++0x extensions dagegen schon.

    0
  • I

    vc++ unterstuetzt leider noch nicht constexpr. 😞

    dann könnte ich aber auch ein constexpr array anlegen mit den Werten von log2(x) fuer die Parameter die ich benoetige.
    (ob der array subscription operator wohl erlaubt ist in constexpr funktionen?)

    0

  • Dann weiss ich nicht was du mit "numeric_limits<T>::max() funktioniert auf jeden fall in const expressions" meinst.
    Probier's mal, es geht nicht:

    int foo[std::numeric_limits<char>::max()]; // error C2057: expected constant expression

    Aber du kannst ja auf boost::integer_traits ausweichen.

    int foo[boost::integer_traits<char>::const_max];
    0
  • E

    Kann 0x auch keine nicht-integralen Initialisierungen bzw. float als Rückgabewert für constexpr?

    0

  • Eisflamme schrieb:

    Kann 0x auch keine nicht-integralen Initialisierungen bzw. float als Rückgabewert für constexpr?

    Doch doch, das geht dann.

    0
  • T

    hustbaer schrieb:

    Eisflamme schrieb:

    Kann 0x auch keine nicht-integralen Initialisierungen bzw. float als Rückgabewert für constexpr?

    Doch doch, das geht dann.

    Wäre dann z.B. sowas wie int a[10 * std::sin(3.14159)] möglich? (Sinnhaftigkeit mal außen vor).

    0

  • Wenn std::sin() mit constexpr versehen wäre, dann ja. Ist es aber AFAIK nicht.

    0
  • E

    Na ja, man könnte sin halt durch Taylor-Reihen aufbauen, das sollte dann klappen.

    0
Anmelden zum Antworten