infinite precision compile time arithmetic



  • camper schrieb:

    Schönheitsfehler: bei der constexpr-Variante liegen die Ergebnisse nicht als Strings im Executable vor, wird also offenbar erst zur Laufzeit berechnet.

    Stimmt - cout << kann nicht zur Compilierzeit ausgeführt werden. Mit

    constexpr auto c = a+b;
      std::cout << c  << '\n';
    

    ist das Ergebnis c im executable sichtbar (Ergebnisende HEX-String 04 02 04 02 01 suchen, nicht char annehmen). Allerdings hat das nur mit clang++ 5.0 funktioniert, mit g++ 7.1 ist nichts im Executable zu sehen.


  • Mod

    Falls jemand spielen will. Die Compilierzeiten sind gar nicht mal so schlecht. Aber wie richtiger Templatecode sieht das auch nicht mehr aus, selbst ein Anfänger könnte den Code verstehen... 🤡



  • Könntest du deine Erkenntnisse irgendwo zusammentragen? Das wär durchaus interessant.


  • Mod

    Neue Erkenntnise habe ich nicht. Wenn die Geschwindigkeit und der Speicherverbrauch beim Compilieren wichtig sind, gilt im Grunde nur eine wichtige Regel: möglichst wenige Templateinstantiierungen durchführen.
    Unwichtige Beobachtung: gcc merkt sich die Ergebnisse von constexpr-Funktionen, clang tut das nicht. gcc compiliert daher i.Allg. schneller als clang, wenn die Auswertung solcher Funktionen dominiert.


  • Mod

    Ich finde deinen Ansatz interessant, weil er--wie von dir gewohnt--durch den Einsatz von rekursiven Instantiierungen funktionaler Natur ist. Bspw. das case splitting durch partielle Spezialisierungen ist hübsch, weil der Compiler schon erkennt welche Spezialisierungen "spezieller" sind, was die verschachtelten if -Statements erübrigt.

    Der Nachteil ist natürlich die Performance. Wie schon von Richard Smith erwähnt (der wahrscheinlich Hand an Clang's Implementierung gelegt hat), ist die Art und Weise wie Templateargument-Listen dargestellt werden grundsätzlich nicht für TMP geeignet. Und sobald man anfängt, clevere Tricks einzusetzen um die Instantiierungstiefen bestimmter Funktionen logarithmisch zu begrenzen, verkompliziert sich der Code wiederum. Ich halte deinen Ansatz deswegen für impraktikabel.

    camper schrieb:

    Unwichtige Beobachtung: gcc merkt sich die Ergebnisse von constexpr-Funktionen, clang tut das nicht. gcc compiliert daher i.Allg. schneller als clang, wenn die Auswertung solcher Funktionen dominiert.

    Dazu fällt mir etwas ein. Siehe diese Frage und meine Antwort dazu:

    https://stackoverflow.com/q/42233729/3647361

    Der Clang report zeigt auf, dass der Performance-Defizit schon signifikant sein muss. Allerdings führt diese Optimierung eben zu ein paar Bugs.

    Hier mein "Roman", für den ich meine Constainer Bibliothek zugezogen habe (kompiliert mit der aktuell stabilen GCC version):

    #include "Algorithms.hxx"
    #include "FlatMap.hxx"
    #include "String.hxx"
    
    #include <array>
    #include <bitset>
    #include <iostream>
    #include <limits>
    
    #include <climits>
    
    namespace BigInt {
    
    using limb_t = std::uint32_t;
    using double_limb_t = std::uint64_t;
    using size_type = std::size_t;
    
    constexpr size_type bits_per_limb = sizeof(limb_t) * CHAR_BIT;
    
    constexpr auto base = (double_limb_t)std::numeric_limits<limb_t>::max() + 1;
    
    template <size_type Limbs>
    struct Int
    {
    	static_assert(Limbs > 0);
    
    	bool negative = false;
    	limb_t limbs[Limbs]{};
    
    	constexpr size_type limb_number() const noexcept {
    		return Limbs;
    	}
    
    	constexpr Int() noexcept = default;
    
    	template <typename IntType>
    	constexpr Int(IntType u) noexcept {
    		if (u < 0)
    			negative = true;
    		for (size_type i = 0; u; ++i) {
    			if (i == Limbs)
    				return;
    			limbs[i] = u % base;
    			u /= base;
    		}
    	}
    
    	template <size_type OtherLimbs>
    	constexpr Int(Int<OtherLimbs> const& other) noexcept
    		: negative(other.negative) {
    		for (size_type i = 0; i < Limbs && i < OtherLimbs; ++i)
    			limbs[i] = other.limbs[i];
    	}
    
    	template <size_type OtherLimbs>
    	constexpr Int& operator=(Int<OtherLimbs> const& other) noexcept {
    		negative = other.negative;
    		for (size_type i = 0; i < Limbs; ++i)
    			limbs[i] = other.get_underlying(i);
            return *this;
    	}
    
    	template <typename IntType>
    	explicit constexpr operator IntType() const noexcept {
    		IntType r = 0;
    		for (size_type i = (sizeof(r) + sizeof(limb_t))/sizeof(limb_t); i--;) {
    			r *= base;
    			r += get_underlying(i);
    		}
    		return negative? -r : r;
    	}
    
    	constexpr limb_t get_underlying(size_type index) const noexcept {
    		return index < Limbs? limbs[index] : 0;
    	}
    
    	constexpr Int& operator<<=(size_type i) noexcept {
    		auto q = i / bits_per_limb,
    		     r = i % bits_per_limb;
    
    		if (q >= Limbs)
    			return *this = 0;
    
    		if (r == 0)
    			for (size_type i = Limbs-1; i >= q && i < Limbs; --i)
    				limbs[i] = limbs[i-q];
    		else {
    			for (size_type i = Limbs-1; i >= q+1; --i)
    				limbs[i] = (limbs[i-q] << r)
    				         | (limbs[i-q-1] >> bits_per_limb - r);
    
    			limbs[q] = limbs[0] << r;
    		}
    
    		Constainer::fill(limbs, limbs+q, 0);
    
    		return *this;
    	}
    	constexpr Int operator<<(size_type i) const noexcept {
    		Int r = *this;
    		r <<= i;
    		return r;
    	}
    
    	constexpr Int& operator>>=(size_type i) noexcept {
    		auto q = i / bits_per_limb,
    		     r = i % bits_per_limb;
    
    		if (q >= Limbs)
    			return *this = 0;
    
    		if (r == 0)
    			for (size_type i = 0; i < Limbs - q; ++i)
    				limbs[i] = limbs[i+q];
    		else {
    			for (size_type i = 0; i < Limbs - q - 1; ++i)
    				limbs[i] = (limbs[i+q] >> r)
    				         | (limbs[i+q+1] << bits_per_limb - r);
    
    			limbs[Limbs-q-1] = limbs[Limbs-1] >> r;
    		}
    
    		Constainer::fill(limbs+Limbs-q, limbs+Limbs, 0);
    
    		return *this;
    	}
    	constexpr Int operator>>(size_type i) const noexcept {
    		Int r = *this;
    		r >>= i;
    		return r;
    	}
    
    	constexpr Int operator-() const noexcept {
    		auto i = *this;
    		i.negative = !i.negative;
    		return i;
    	}
    	constexpr Int operator+() const noexcept {
    		return *this;
    	}
    	constexpr Int& operator--() noexcept {
    		return *this -= 1;
    	}
    	constexpr Int& operator++() noexcept {
    		return *this += 1;
    	}
    	constexpr Int operator--(int) noexcept {
    		auto x = *this;
    		*this;
    		return x;
    	}
    	constexpr Int operator++(int) noexcept {
    		auto x = *this;
    		++*this;
    		return x;
    	}
    
    	void dump_binary() const {
    		for (int i = Limbs; --i >= 0; )
    			std::cout << std::bitset<bits_per_limb>(limbs[i]).to_string();
    		std::cout << '\n';
    	}
    };
    
    template <typename T>
    Int(T) -> Int<(sizeof(T)+sizeof(limb_t)-1)/sizeof(limb_t)>;
    
    template <size_type Limbs>
    constexpr auto abs(Int<Limbs> i) noexcept {
    	i.negative = false;
    	return i;
    }
    
    template <size_type Limbs>
    constexpr size_type clz(Int<Limbs> const& x) noexcept {
    	size_type res = 0;
    	auto i = Limbs-1;
    	for(; i > 0 && x.limbs[i] == 0; --i) {
    		res += bits_per_limb;
    	}
    	static_assert(sizeof(limb_t) == sizeof(unsigned), "This function employs __builtin_clz");
    	return res + __builtin_clz(x.limbs[i]);
    }
    template <size_type Limbs>
    constexpr size_type log2(Int<Limbs> const& x) noexcept {
    	auto l = Limbs * bits_per_limb - clz(x);
    	return l>0? l-1 : 0;
    }
    
    #define DEFINE_HETEROGENOUS_ASS_OP(OP)                                 \
    template <size_type Limbs1, size_type Limbs2>                          \
    constexpr auto                                                         \
      operator OP##=(Int<Limbs1>& lhs, Int<Limbs2> const& rhs) noexcept {  \
    	return lhs = lhs OP rhs;}                                            \
    template <size_type Limbs1, typename Arithmetic>                       \
    constexpr auto                                                         \
      operator OP##=(Int<Limbs1>& lhs, Arithmetic rhs) noexcept {          \
    	return lhs OP##= Int(rhs);}
    
    #define DEFINE_HETEROGENOUS_OP(OP)                               \
    template <size_type Limbs1, typename Arithmetic>                 \
    constexpr decltype(auto)                                         \
      operator OP(Int<Limbs1> const& lhs, Arithmetic rhs) noexcept { \
    	return lhs OP Int(rhs);}                                       \
    template <size_type Limbs1, typename Arithmetic>                 \
    constexpr decltype(auto)                                         \
      operator OP(Arithmetic lhs, Int<Limbs1> const& rhs) noexcept { \
    	return Int(lhs) OP rhs;}
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr bool operator==(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	bool is_zero = true;
    	size_type i = 0;
    	for (auto end = std::min(Limbs1, Limbs2); i < end; ++i)
    		if (lhs.limbs[i] != rhs.limbs[i])
    			return false;
    		else if (lhs.limbs[i] != 0)
    			is_zero = false;
    	for (; i < Limbs1; ++i)
    		if (lhs.limbs[i] != 0)
    			return false;
    	for (; i < Limbs2; ++i)
    		if (rhs.limbs[i] != 0)
    			return false;
    
    	return lhs.negative == rhs.negative || is_zero;
    }
    DEFINE_HETEROGENOUS_OP(==)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr bool operator!=(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	return !(lhs == rhs);}
    DEFINE_HETEROGENOUS_OP(!=)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr bool operator<(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	if (lhs.negative)
    		if (!rhs.negative)
    			return lhs != 0 || rhs != 0;
    		else
    			return -rhs < -lhs;
    	else if (rhs.negative)
    		return false; // lhs >= 0, rhs <= 0
    	if constexpr (Limbs1 > Limbs2) {
    		if (Constainer::find_if(lhs.limbs + Limbs2, lhs.limbs + Limbs1,
    		                        [] (auto x) {return x != 0;}))
    			return false;
    	}
    	else if constexpr (Limbs2 > Limbs1) {
    		if (Constainer::find_if(rhs.limbs + Limbs1, rhs.limbs + Limbs2,
    		                        [] (auto x) {return x != 0;}))
    			return true;
    	}
    	for (auto i = std::min(Limbs1, Limbs2); i--;)
    		if (lhs.limbs[i] < rhs.limbs[i])
    			return true;
    		else if (lhs.limbs[i] > rhs.limbs[i])
    			return false;
    
    	return false;
    }
    DEFINE_HETEROGENOUS_OP(<)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr bool operator>(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	return rhs < lhs;
    }
    DEFINE_HETEROGENOUS_OP(>)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr bool operator<=(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	return !(lhs > rhs);
    }
    DEFINE_HETEROGENOUS_OP(<=)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr bool operator>=(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	return rhs <= lhs;
    }
    DEFINE_HETEROGENOUS_OP(>=)
    
    template <size_type Limbs1, size_type Limbs2>
    struct DivT {
    	Int<Limbs1> quot;
    	Int<Limbs2> rem;
    };
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr DivT<Limbs1, Limbs2> div(Int<Limbs1> dividend, Int<Limbs2> const& _divisor) {
    	if (_divisor == 0)
    		throw std::invalid_argument{"Int.div(0)"};
    
    	Int<Limbs1> divisor = _divisor; // we need this variable to be large enough
    	bool divid_neg = dividend.negative,
    	     divis_neg = divisor.negative;
    	dividend.negative = divisor.negative = false;
    
    	auto shift_amount = clz(divisor) - clz(dividend);
    	divisor <<= shift_amount;
    	if (divisor > dividend) {
    		divisor >>= 1;
    		--shift_amount;
    	}
    	auto counter = Int<Limbs1>{1} << shift_amount;
    
    	DivT<Limbs1, Limbs2> result;
    	auto remainder = dividend;
    	while (counter != 0) {
    		if (divisor <= remainder) {
    			remainder -= divisor;
    			result.quot += counter;
    		}
    		divisor >>= 1;
    		counter >>= 1;
    	}
    
    	result.rem = remainder;
    	result.rem.negative = divid_neg; // remainder same sign as dividend
    	result.quot.negative = divid_neg ^ divis_neg;
    	return result;
    }
    template <size_type Limbs1, typename Arithmetic>
    constexpr auto div(Int<Limbs1> dividend, Arithmetic divisor) {
        return div(dividend, Int(divisor));
    }
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr Int<Limbs1> operator/(Int<Limbs1> const& dividend, Int<Limbs2> const& divisor) {
    	return div(dividend, divisor).quot;
    }
    DEFINE_HETEROGENOUS_OP( / )
    DEFINE_HETEROGENOUS_ASS_OP( / )
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr Int<Limbs2> operator%(Int<Limbs1> const& dividend, Int<Limbs2> const& divisor) {
    	return div(dividend, divisor).rem;
    }
    DEFINE_HETEROGENOUS_OP( % )
    DEFINE_HETEROGENOUS_ASS_OP( % )
    
    template <size_type ResultLimbs, size_type Limbs1, size_type Limbs2>
    constexpr auto multiply(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	Int<ResultLimbs> result, addend = rhs;
    	for (auto x : lhs.limbs)
    		if (x == 0)
    			addend <<= bits_per_limb;
    		else
    			for (int i = 0; i < bits_per_limb; ++i) {
    				if (x & 1)
    					result += addend;
    				x >>= 1;
    				addend <<= 1;
    			}
    
    	result.negative = lhs.negative ^ rhs.negative;
    	return result;
    }
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto operator*(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	return multiply<Limbs1 + Limbs2>(lhs, rhs);
    }
    DEFINE_HETEROGENOUS_OP( * )
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto& operator*=(Int<Limbs1>& lhs, Int<Limbs2> const& rhs) noexcept {
    	return lhs = multiply<Limbs1>(lhs, rhs);
    }
    template <size_type Limbs1, typename Arithmetic>
    constexpr auto& operator*=(Int<Limbs1>& lhs, Arithmetic rhs) noexcept {
    	return lhs *= Int(rhs);
    }
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto addUnsigned(Int<Limbs1> const& lhs,
                               Int<Limbs2> const& rhs, int carry = 0) noexcept {
    	Int<std::max(Limbs1, Limbs2)> result;
    	size_type i = 0;
    	for (auto end = std::min(Limbs1, Limbs2); i < end; ++i){
    		auto add = carry + (double_limb_t)lhs.limbs[i] + rhs.limbs[i];
    		result.limbs[i] = add;
    		carry = (add != result.limbs[i]);
    	}
    	if constexpr(Limbs1 < Limbs2) {
    		for (; i < Limbs2; ++i){
    			auto add = carry + (double_limb_t)rhs.limbs[i];
    			result.limbs[i] = add;
    			carry = (add != result.limbs[i]);
    		}
    	} else {
    		for (; i < Limbs1; ++i){
    			auto add = carry + (double_limb_t)lhs.limbs[i];
    			result.limbs[i] = add;
    			carry = (add != result.limbs[i]);
    		}
    	}
    	return result;
    }
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr Int<std::max(Limbs1, Limbs2)>
      subtractUnsigned(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	if (abs(lhs) < abs(rhs)) {
    		auto r = subtractUnsigned(rhs, lhs);
    		r.negative = true;
    		return r;
    	}
    
    	Int<std::max(Limbs1, Limbs2)> result;
    	std::make_signed_t<double_limb_t> borrow = 0;
    	for (size_type i = 0, end = std::max(Limbs1, Limbs2); i < end; ++i) {
    		auto diff = (i >= Limbs1? 0 : lhs.limbs[i]) - borrow
    		          - (i >= Limbs2? 0 : rhs.limbs[i]);
    		result.limbs[i] = diff;
    		borrow = (diff < 0);
    	}
    	return result;
    }
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto operator+(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) {
    	if (lhs.negative)
    		if (rhs.negative) {
    			auto res = addUnsigned(lhs, rhs);
    			res.negative = true;
    			return res;
    		}
    		else
    			return subtractUnsigned(rhs, lhs);
    	else if (rhs.negative)
    		return subtractUnsigned(lhs, rhs);
    	return addUnsigned(lhs, rhs);
    }
    DEFINE_HETEROGENOUS_OP(+)
    DEFINE_HETEROGENOUS_ASS_OP(+)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto operator-(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) {
    	return lhs + -rhs;
    }
    DEFINE_HETEROGENOUS_OP(-)
    DEFINE_HETEROGENOUS_ASS_OP(-)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto operator&(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	Int<std::max(Limbs1, Limbs2)> res;
    	for (size_type i = 0; i < res.limb_number(); ++i)
    		res.limbs[i] = lhs.get_underlying(i) & rhs.get_underlying(i);
    	return res;
    }
    DEFINE_HETEROGENOUS_OP(&)
    DEFINE_HETEROGENOUS_ASS_OP(&)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto operator|(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	Int<std::max(Limbs1, Limbs2)> res;
    	for (size_type i = 0; i < res.limb_number(); ++i)
    		res.limbs[i] = lhs.get_underlying(i) & rhs.get_underlying(i);
    	return res;
    }
    DEFINE_HETEROGENOUS_OP(|)
    DEFINE_HETEROGENOUS_ASS_OP(|)
    
    template <size_type Limbs1, size_type Limbs2>
    constexpr auto operator^(Int<Limbs1> const& lhs, Int<Limbs2> const& rhs) noexcept {
    	Int<std::max(Limbs1, Limbs2)> res;
    	for (size_type i = 0; i < res.limb_number(); ++i)
    		res.limbs[i] = lhs.get_underlying(i) ^ rhs.get_underlying(i);
    	return res;
    }
    DEFINE_HETEROGENOUS_OP(^)
    DEFINE_HETEROGENOUS_ASS_OP(^)
    
    template <char... ch>
    constexpr auto operator"" _int() noexcept {
    	// constexpr fails here with GCC. Cannot test with Clang but believe it's a
    	// bug
    	const Constainer::FlatMap<char, int> digit_map{
    		{'0', 0}, {'1', 1}, {'2', 2},
    		{'3', 3}, {'4', 4}, {'5', 5},
    		{'6', 6}, {'7', 7}, {'8', 8}, {'9', 9},
    		{'a', 10}, {'A', 10},
    		{'b', 11}, {'B', 11},
    		{'c', 12}, {'C', 12},
    		{'d', 13}, {'D', 13},
    		{'e', 14}, {'E', 14},
    		{'f', 15}, {'F', 15}
    	};
    
    	Constainer::BasicString<char, sizeof...(ch)> str{ch...};
    	Int<(size_type)(sizeof...(ch)*4+31)/32> res;
    	typename decltype(str)::size_type i = 0;
    	if (str[i] == '-') {
    		res.negative = true;
    		++i;
    	}
    
    	int base = 10;
    	if (str[i] == '0')
    		if (Constainer::toupper(str[++i]) == 'X') {
    			base = 16;
    			++i;
    		}
    		else if (Constainer::toupper(str[i]) == 'B') {
    			base = 2;
    			++i;
    		}
    		else
    			base = 8;
    
    	for (; i < str.length(); ++i) {
    		res *= base;
    		res += digit_map.at(str[i]);
    	}
    	return res;
    }
    
    template <size_type C>
    std::ostream& operator<<(std::ostream& os, Int<C> i) {
    	std::ostream::sentry sentry(os);
    	if (!sentry)
    		return os;
    
    	Constainer::BasicString<char, C*bits_per_limb> str;
    
    	bool uppercase  = (os.flags() & std::ios::uppercase),
    	     showpos    = (os.flags() & std::ios::showpos),
    	     showbase   = (os.flags() & std::ios::showbase);
    
    	bool sign_written = true;
    	if (i.negative)
    		str += '-';
    	else if (showpos)
    		str += '+';
    	else
    		sign_written = false;
    
    	int base = os.flags() & os.hex? 16
    	         : os.flags() & os.oct? 8
    	         : 10;
    
    	char const* const digits = uppercase? "0123456789ABCDEFX"
    	                                    : "0123456789abcdefx";
    
    	if (showbase)
    		if (base == 16)
    			str.append({'0', digits[16]});
    		else if (base == 8)
    			str += '0';
    
    	auto start_iter = str.length();
    
    	auto& facet = std::use_facet<std::numpunct<char>>(os.getloc());
    	auto sep      = facet.thousands_sep();
    	auto grouping = facet.grouping();
    
    	decltype(div(i, base)) remquot{i};
    	std::size_t grouping_index = 0;
    	char to_jump = grouping.empty()? -1 : grouping[0];
    	do {
    		remquot = div(remquot.quot, base);
    		str += digits[(std::size_t)abs(remquot.rem)];
    		if (to_jump > 0 && to_jump != CHAR_MAX)
    			--to_jump;
    		if (to_jump == 0) {
    			str += sep;
    			++grouping_index;
    			to_jump = grouping.empty()? -1 : grouping[std::min(grouping_index, grouping.size()-1)];
    		}
    	} while (remquot.quot != 0);
    
    	Constainer::reverse(str.begin() + start_iter, str.end());
    
    	if (str.size() < (size_t)os.width()) {
    		auto adjustfield = (os.flags() & std::ios::adjustfield);
    		std::size_t pos;
    		switch (adjustfield) {
    			case std::ios::left:
    				pos = str.size();
    			break;
    			default: case std::ios::right:
    				pos = 0;
    			break;
    			case std::ios::internal:
    				if (sign_written)
    					pos = 1;
    				else if (showbase && base==16)
    					pos = 2;
    				else
    					pos = 0;
    			break;
    		};
    		str.insert(pos, os.width()-str.size(), os.fill());
    	}
    	os.width(0);
    
    	return os << str.data();
    }
    
    template <size_type C>
    constexpr auto to_string(Int<C> const& i) noexcept {
    	Constainer::BasicString<char, C*sizeof(limb_t)*4> str;
    	decltype(div(i, 1'000'000'000'000'000'000)) rq{i};
    	while (rq.quot != 0) {
    		rq = div(rq.quot, 1'000'000'000'000'000'000);
    		auto rem = rq.rem.limbs[1] * base + rq.rem.limbs[0];
    		if (rq.quot == 0)
    			while (rem != 0) {
    				str += '0' + rem % 10;
    				rem /= 10;
    			}
    		else for (int j = 0; j < 18; ++j) {
    			str += '0' + rem % 10;
    			rem /= 10;
    		}
    	}
    	if (i.negative)
    		str += '-';
    	Constainer::reverse(begin(str), end(str));
    	return str;
    }
    } // end namespace BigInt
    
    //! Test:
    
    struct GroupingFacet : std::numpunct<char>
    {
        char do_thousands_sep() const { return '\''; }
        std::string do_grouping() const { return "\3"; }
    };
    
    #include <iomanip>
    #include <iostream>
    int main() {
    	using BigInt::operator""_int;
    	constexpr auto a = 4242424242424242424242424242424242424242424242424242424242424242424242424242_int;
    	constexpr auto b = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999_int;
    	std::cout.imbue(std::locale(std::cout.getloc(), new GroupingFacet));
    	std::cout << std::internal << std::setw(130) << a+b << '\n'
    	                           << std::setw(130) << b+b << '\n'
    	                           << std::setw(130) << a-b << '\n'
    	                           << std::setw(130) << a-a << '\n';
    }
    

    Praktisch ungetestet! Ich habe geschrieben bis dein Beispiel einwandfrei lief. Die Formatierung ist wahrscheinlich auch im Eimer, weil ich zum Ende hin einige Bezeichner umbenannt habe.

    Ich habe hier eine constexpr inkompatible String-Konvertierung fabriziert, die dafür mit den IO-Manipulatoren interagiert. Ich könnte allerdings auch eine Integration für meine Static Printf Facility schreiben, das Endresultat wäre cool 🙂

    Performance ist definitiv noch verbesserbar, die Divisions-Funktion bspw. dürfte deutlich effizienter zu implementieren sein, diese Shifts in jedem Durchlauf sehen teuer aus. Allgemein scheint mir der Bitweise Ansatz verkehrt zu sein, weil wir nicht wirklich ausnutzen, dass die Maschine arithmetische Operationen für die Limbs bereitstellt...

    Edit: Exception-Handling für insertion operator ergänzt.
    Edit^2: Verbuggter operator* gefixt.


  • Mod

    Arcoth schrieb:

    Allerdings führt diese Optimierung eben zu ein paar Bugs.

    Soweit ich sehe, treten Probleme auf, sobald Referenzen im Spiel sind. Interessanterweise brauche ich ja gar keine constexpr Funktionen, weil die gesamte Information in den Typen der Argumente kodiert ist. Im Prinzip lässt sich alles ganz mechanisch in eine Form, die Klassentemplates verwendet überführen (dabei geht nat. die schöne Syntax verloren). Aber in Klassentemplates gibt es leider keine Schleifen, und jede hinreichend komplexe Operation führt zwangsläufig zu rekursiven Instantiierungsorgien. Was bedeutet, das jede noch so fehlerhafte constexpr-Optimierung von gcc zumindest in diesem Fall wahrscheinlich trotzdem für alle Inputs zum richtigen Ergebnis führt.

    ...
    

    BigInt ist langweilig 😉

    Das Vorzeichen ist nicht Teil von Integerliteralen (und bei floats kann es nur als Teil des Exponenten auftreten).

    Arcoth schrieb:

    Performance ist definitiv noch verbesserbar, die Divisions-Funktion bspw. dürfte deutlich effizienter zu implementieren sein, diese Shifts in jedem Durchlauf sehen teuer aus. Allgemein scheint mir der Bitweise Ansatz verkehrt zu sein, weil wir nicht wirklich ausnutzen, dass die Maschine arithmetische Operationen für die Limbs bereitstellt...

    Schwierig. Bitschift ist jedenfalls einfach zu implementieren. Mir fällt dazu nur die Möglichkeit ein zwei Testdivisionen durchzuführen, bei denen jeweils nur 2 Stellen des Dividenten und eine Stelle des Divisors betrachten werden (wofür wir direkte Unterstüttzung durch die Maschine haben): Wenn
    - aufgerundeter Divident durch abgerundeten Divisor, und
    - abgerundenter Divident durch aufgerundeten Divisor
    jeweils das gleiche Ergebnis bringen, haben wir sofort eine Stelle des Ergebnisses ermittelt. Ist das nicht der Fall, sehe ich nicht, wie die vorhandene Divisionsfunktion unmitelbar benutzt werden kann. Anderseits habe ich von numerischen Verfahren keine Ahnung und kann mich nur erinnern, wie man schriftlich dividiert...
    Wer Dividiert und Geschwindigkeit erwartet macht sowieso etwas falsch.


  • Mod

    camper schrieb:

    ...
    

    BigInt ist langweilig 😉

    Wie, der Name? Namen sind Ansichtssache. Deinen Namen könnte man auch einfallslos finden, aber für jemanden der Stunden um Stunden auf TLPDs wartet hat er eine Bedeutung.

    Das Vorzeichen ist nicht Teil von Integerliteralen (und bei floats kann es nur als Teil des Exponenten auftreten).

    Tatsächlich.

    Bitschift ist jedenfalls einfach zu implementieren.

    Wie, mit views? Wie soll man dann effizient addieren (und somit multiplizieren) in dem man limbs addiert?
    Edit:^3 hatte "einfach" als "einfacher" gelesen.

    Edit: Geiler Server. Wollte einen unsinnigen, unvollständigen Satz aus meiner Antwort löschen, und erstmal gibt's nen Gateway timeout.
    Edit^2: Wtf? 13 Edits. Wir brauchen eine ordentliche Forensoftware. 😮


  • Mod

    Arcoth schrieb:

    camper schrieb:

    ...
    

    BigInt ist langweilig 😉

    Wie, der Name?

    Nein. Das Problem ist, dass der benötigte Speicherplatz nicht vom repräsentierten Wert abhängt und ziemlich schnell explodiert. Das schränkt die Menge der lösbaren Problem ein.


  • Mod

    Warum soll der Speicher explodieren?

    Edit: Ich denke, unsere Implementierungen sind für verschiedene Anwendungen konzipiert. Deine kann man nicht in Schleifen einsetzen. Meine schon, dafür ist sie potenziell(!) nicht praktisch wenn man komplexere Ausdrücke auswertet, da die Größe des Typs nicht den Werten entsprechend skalieren kann; entweder man begrenzt die Domäne (was zu Fehlern führt), oder man lässt die Ergebnisse in einem entsprechend vergrößerten Typ zurückgeben.


  • Mod

    Arcoth schrieb:

    Deine kann man nicht in Schleifen einsetzen. Meine schon

    Wie? Das geht ja nur dann, wenn die Typen des Ergebnisses sich nicht ändern. Das ist im Allgemeinen nicht garantiert (nebenbei: dein unsigned add ignoriert potentielle Überläufe; die Summe zweier einstelliger Zahlen kann auch mal zweistellig sein).

    Wie würdest du z.B. ein pow-Funktion implementieren (nicht als Teil der Bibliothek sondern als Anwender derselben)?
    Bei mir sieht das ungefähr so aus (ganz naiv):

    template <typename T, typename U>
    constexpr auto big_pow(T base, U exponent) {
        static_assert(base != 0_int || exponent != 0_int, "pow(0,0) is undefined!");
        if constexpr (base == 0_int || exponent < 0_int) {
            return 0_int;
        } else if constexpr (abs(base) == 1_int) {
            if constexpr (base < 0_int && abs(exponent) % 2_int == 1_int) {
                return -1_int;
            } else {
                return 1_int;
            }
        } else if constexpr (exponent == 0_int) {
            return 1_int;
        } else if constexpr (exponent == 1_int) {
            return base;
        } else {
            return big_pow(base, exponent / 2_int) * big_pow(base, (exponent + 1_int) / 2_int);
        }
    }
    
    #include <iostream>
    int main() {
        std::cout << big_pow(3_int, 2000_int) << '\n';
    }
    

  • Mod

    camper schrieb:

    Das ist im Allgemeinen nicht garantiert (nebenbei: dein unsigned add ignoriert potentielle Überläufe; die Summe zweier einstelliger Zahlen kann auch mal zweistellig sein).

    Das ist mir klar. Ich hatte auch ursprünglich eine +1 an die Limb Zahl gehängt, aber das hatte zyklische Instantiierungsprobleme mit sich gebracht.

    pow kann ich für Int s nicht allgemein implementieren, aber ich muss schließlich nur zeigen, dass meine Lösung so mächtig ist wie deine, und das ist ziemlich simpel. Denn deine Lösung nimmt per Design an, dass die Werte der Argumente quasi constant expressions sind. Darf ich also auch, auch wenn es seine Kosmetik-Probleme mit sich bringt.

    template <BigInt::size_type ResSize, BigInt::size_type BaseLimbs>
    constexpr auto big_pow(BigInt::Int<BaseLimbs> const& base, std::uint64_t exp) noexcept {
    	BigInt::Int<ResSize> res = 1, addend = base;
    	while (exp) {
    		if (exp & 1)
    			res *= addend;
    		addend *= addend;
    		exp >>= 1;
    	}
    	return res;
    }
    #define POW(BASE, EXP) ([]{                                              \
      constexpr auto _b = BASE; constexpr ::std::uint64_t _e = EXP;          \
      return big_pow<((log2(_b)+1)*_e + ::BigInt::bits_per_limb - 1)         \
                  / ::BigInt::bits_per_limb>(_b, _e);                        \
    }())
    
    #include <iomanip>
    #include <iostream>
    int main() {
    	using BigInt::operator""_int;
    	constexpr auto str = to_string(POW(3_int, 2000));
    }
    

    Merkwürdigerweise ist mein Code wahnsinnig langsam in compile-time Ausführung. Ich vermute, dass dafür die Sandbox-Maschinerie hinter der constexpr Auswertung verantwortlich ist (ich habe auch probiert, Clang SVN zu testen, mit dessen ExprConstant.cpp ich sogar halbwegs vertraut bin, aber es ist irgendwie in die Hose gegangen das überhaupt zu builden, mache ich demnächst mal). Für einen to_string Aufruf, der <40ms in gewöhnlicher Ausführung benötigt, ist die Kompilierung nicht in Sicht. 😮 Aber das PoC sieht man ja.

    Edit: Clang hat ein paar miese Bugs in der constexpr suite. Das wird man so schnell nicht testen können.



  • Sehe ich das richtig, dass du zur Basis 10 rechnest? Warum nicht zur Basis 2^64?


  • Mod

    Arcoth schrieb:

    ...

    All Hail The Mighty Preprocessor! 🙂
    Der Ansatz lässt sich ganz gut verallgemeinern: Im Grunde muss jede Operation zweimal implementiert werden, wobei eine Version nur den benörigten Platz des Ergebnisses berechnet. Das Schreiben komplexer Algorithmen wird damit nat. relativ schwierig: Rekursion oder irgendwelche anderen Funktionsaufrufe, die ihrerseits Berechnungen ausführen, sind ausgeschlossen. Damit verbleibt nur die Möglichkeit, riesige Spaghettifunktionen zu schreiben - ohne goto versteht sich.

    Ich hatte die Aufgabe primär gestellt, um zu demonstrieren, wieso mein Design so ausfiel wegen einer Präferenz für bestimmte Implementierungstechniken (abgesehen devon, dass der Präprozessor nach Möglichkeit nicht zum Einsatz kommen sollte), sondern unmittelbar Folge der Anforderungen ist, die ich gestellt habe:
    Berechnungsergebnis können (fast) beliebig groß werden; abder der Ergebnistyp einer Funktion kann ja nur von den Typen der Argumente abhängen, nicht von den Werten der Argumente. Anderseits steht mir bei der Auswertung konstanter Ausdrücke dynamischer Speicher natürlich nicht zur Verfügung. Damit verbleibt letzlich nur die Option, alle Daten allein durch den Typ zu repräsentieren (wenn man nicht deinen Cheat benutzen will, bei dem die Argumente noch vor dem eigenlichen Funktionsaufruf abgefangen und untersucht werden).


Anmelden zum Antworten