3. Zur Laufzeit: Performant Zehnerpotenz berechnen

Zur Laufzeit: Performant Zehnerpotenz berechnen

  • K

    Dann schreibt man groessere Zahlen eben als Produkt von Zehnerpotenzen 🤡

    {1, 10, 100, 1000, 10*1000, 100*1000, 1000*1000, 10*1000*1000, 100*1000*1000, 1000*1000*1000}

    Natuerlich koennte man das jetzt noch mit einem Template generieren und dabei INT_MAX beruecksichtigen.

    Die Challenge ueberlass ich Hacker 🤡

    0
  • ?

    Kellerautomat schrieb:

    Dann schreibt man groessere Zahlen eben als Produkt von Zehnerpotenzen 🤡

    Mindestens ein

    constexpr int cpow(int base, int exp) { return exp==1 ? 1 : base*cpow(base, exp-1); }

{cpow(0), cpow(1), cpow(2), cpow(3), ...}

    sollte schon drinliegen.

    0
  • V

    templatebloatbeschwörer schrieb:

    Kellerautomat schrieb:

    Dann schreibt man groessere Zahlen eben als Produkt von Zehnerpotenzen 🤡

    Mindestens ein

    constexpr int cpow(int base, int exp) { return exp==1 ? 1 : base*cpow(base, exp-1); }

{cpow(0), cpow(1), cpow(2), cpow(3), ...}

    sollte schon drinliegen.

    Nö.
    Es ging um ipow10.
    Und das beschneidet man mit ipow10(int32_t) bzw ipow10(int64_t).

    0
  • Mod

    Kellerautomat schrieb:

    Die Challenge ueberlass ich Hacker 🤡

    Wer ist Hacker?

    Und eine Challenge war das nicht. Abgesehen davon, das Clang da nicht mitmacht. Gibt es schon einen Bug-Report für Compile-Time Integer-Division?

    template<unsigned ... args>
struct index_list
{
	using type = index_list;
};

template <typename, typename> struct multiply;
template <unsigned... indices, unsigned... tail>
struct multiply<index_list<indices...>,
		    index_list<tail...   >> : index_list<indices..., (sizeof...(indices)+indices)...,
										     (2*sizeof...(indices)+indices)...> {};
template <unsigned N>
struct make_index_list :
	multiply< typename make_index_list<N/2>::type,
		    typename make_index_list<N%2>::type > {};

template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

#include <limits>
template< typename T,
          T base >
static constexpr unsigned highest_exponent( unsigned counter = 0, T current = std::numeric_limits<T>::max() )
{
	return current ? highest_exponent<T,base>(counter+1, current/base) : counter ;
}

template< typename T,
          T base,
          typename = typename make_index_list<highest_exponent<T, base>()>::type >
struct pow_helper;

template< typename T,
          T base,
          unsigned ... indices >
struct pow_helper<T, base, index_list<indices...>>
{
	static_assert( base > 1, "Invalid base!" ); // Kann man erweitern (Edit: >= ist natürlich falsch!) (Edit²: > 0 ist natürlich ebenfalls falsch)

	static constexpr auto number = sizeof...(indices);

	static constexpr T pow( unsigned i )
	{
		return i ? pow(i-1) * base : 1;
	}

	static constexpr T array[]{ pow(indices)... };
};

template< typename T,
          T base,
          unsigned ... indices >
constexpr T pow_helper<T, base, index_list<indices...>>::array[];

#include <cassert>
template<typename T, T base>
T pow( unsigned exp )
{
	using helper = pow_helper<T, base>;
	assert( exp < helper::number );
	return helper::array[exp];
}

#include <iostream>
int main()
{
	std::cout << pow<int, 10>(3);
}

    https://ideone.com/YJuefl

    0
  • E

    Ich nehme doch die einfachere Lösung. 🤡

    0
  • O

    eventuell sollte man noch mit einem macro unterscheiden, ob int 32 oder 64 bit breit ist...

    0
  • Mod

    otze schrieb:

    eventuell sollte man noch mit einem macro unterscheiden, ob int 32 oder 64 bit breit ist...

    Daher ist die TMP-Lösung so flexibel.

    0
  • O

    Arcoth schrieb:

    otze schrieb:

    eventuell sollte man noch mit einem macro unterscheiden, ob int 32 oder 64 bit breit ist...

    Daher ist die TMP-Lösung so flexibel.

    aber ein macro sind 3 Zeilen die ein VC6 sogar noch versteht. Hast du eventuell nicht bemerkt, dass die Leute sich einen Scherz daraus gemacht haben, für sowas eine templatelösung zu fordern?

    0
  • C
    Mod

    Arcoth schrieb:

    Abgesehen davon, das Clang da nicht mitmacht. Gibt es schon einen Bug-Report für Compile-Time Integer-Division?

    Dein Code ist falsch (Zeile 11) und gcc ist nur etwas weniger streng (was ein bug bei gcc wäre, da das Programm so ill-formed ist).

    0
  • Mod

    otze schrieb:

    Arcoth schrieb:

    otze schrieb:

    eventuell sollte man noch mit einem macro unterscheiden, ob int 32 oder 64 bit breit ist...

    Daher ist die TMP-Lösung so flexibel.

    aber ein macro sind 3 Zeilen die ein VC6 sogar noch versteht. Hast du eventuell nicht bemerkt, dass die Leute sich einen Scherz daraus gemacht haben, für sowas eine templatelösung zu fordern?

    Nein, habe ich nicht. Zeige mal die Makro-Lösung, die dasselbe kann.
    Edit: Was meinst du eigentlich? Bei einer TMP-Version braucht man keine Unterscheidung von der Größe, alles geschieht automatisch.

    camper schrieb:

    Dein Code ist falsch (Zeile 11)

    Du hast Recht. Ich habe die Variante mit Vier (die ich in der Lib stehen hatte) gekürzt, dabei ist natürlich Blödsinn herausgekommen. Ein Flüchtigkeitsfehler.
    Es muss

    template <typename, typename> struct multiply;
template <unsigned... indices, unsigned... tail>
struct multiply<index_list<indices...>,
            index_list<tail...   >> : index_list<indices..., (sizeof...(indices)+indices)...> {};

    heißen, dann ist es richtig (und kompiliert natürlich auf Clang).

    Ich habe mich gewundert, wieso die Indexliste immer länger war als sie sein sollte... ich dachte, es liegt an dem Argument an make_index_list und nicht an der Erzeugung selbst... ich sollte in Zukunft immer alles betrachten... 👍

    0
  • C
    Mod

    Bist du sicher, dass du tail vergessen darfst?

    0
  • Mod

    camper schrieb:

    Bist du sicher, dass du tail vergessen darfst?

    Ich glaube, ich habe schlecht geschlafen.

    Also, jetzt höchste Präzision! 😋

    template <typename, typename> struct multiply;
template <unsigned... indices, unsigned... tail>
struct multiply<index_list<indices...>,
                index_list<tail...   >> :
	index_list<indices..., 
	           (sizeof...(indices)+indices)...,
	           (2*sizeof...(indices) + tail)...> {};

template <unsigned N>
struct make_index_list :
    multiply< typename make_index_list<N/2>::type,
              typename make_index_list<N%2>::type > {};

template <> struct make_index_list<1> : index_list<0> {};
template <> struct make_index_list<0> : index_list<> {};

    Ungetestet, sollte aber richtig sein.

    0
  • V

    otze schrieb:

    eventuell sollte man noch mit einem macro unterscheiden, ob int 32 oder 64 bit breit ist...

    Mit Überladung.

    0
Anmelden zum Antworten