infinite precision compile time arithmetic


  • Mod

    Heute mal zur Abwechslung wieder etwas Sinnloses...
    Endziel ist es später mal beliebige Berechnungen bequem beim Compilieren durchzuführen (Pi auf 1000000 Stellen o.ä.).
    Klein angefangen: Integer mit beliebiger Größe.
    Allerdings benötigt der Compiler bei mir schon für diesen kurzen Code recht lange (clang-4.0.0: ca. 8s, g++-7.1.0 ca. 10s).
    Hat jemand Ideen, wie das evtl. beschleunigt werden könnte?

    #include <algorithm>
    #include <cstdint>
    #include <type_traits>
    #include <utility>
    
    using u32 = std::uint32_t;
    using u64 = std::uint64_t;
    
    template <u32... I>
    using digit_sequence = std::integer_sequence<u32, I...>;
    
    template <u32... I, std::size_t... J>
    constexpr u32 at(std::size_t n, digit_sequence<I...>, std::index_sequence<J...>) {
        return (0 + ... + (n == J ? I : 0));
    }
    template <typename T>
    constexpr auto at(std::size_t n, T seq) {
        return at(n, seq, std::make_index_sequence<seq.size()>{});
    }
    
    template <typename... T>
    struct concat_impl;
    template <typename T, typename U, typename... V>
    struct concat_impl<T, U, V...>
      : concat_impl<typename concat_impl<T, U>::type, V...> {
    };
    template <u32... I, u32... J>
    struct concat_impl<digit_sequence<I...>, digit_sequence<J...>> {
        using type = digit_sequence<I..., J...>;
    };
    template <typename... T>
    using concat = typename concat_impl<T...>::type;
    
    template <typename T, typename = std::make_index_sequence<T::size()>>
    struct reverse_impl;
    template <u32... I, std::size_t... J>
    struct reverse_impl<digit_sequence<I...>, std::index_sequence<J...>> {
        using type = digit_sequence<at(sizeof...(I) - 1 - J, digit_sequence<I...>{})...>;
    };
    template <typename T>
    using reverse = typename reverse_impl<T>::type;
    
    template <typename T>
    struct trim_impl;
    template <u32... I>
    struct trim_impl<digit_sequence<I...>> {
        using type = digit_sequence<I...>;
    };
    template <u32... I>
    struct trim_impl<digit_sequence<0, I...>>
      : trim_impl<digit_sequence<I...>> {
    };
    template <typename T>
    using trim = reverse<typename trim_impl<reverse<T>>::type>;
    
    template <typename T>
    struct integer_value;
    template <u32... I>
    struct integer_value<digit_sequence<I...>>
    {
        static constexpr const char value[] = {"0123456789abcdefghijklmnopqrstuvwxyz-"[I]..., '\0'};
        constexpr operator decltype(value) &() const {
            return value;
        }
    };
    template <u32... I>
    constexpr const char integer_value<digit_sequence<I...>>::value[];
    struct empty {
    };
    template <u32 Radix, bool is_negative = false>
    struct prefix_impl {
        using type = std::integer_sequence<u32>;
    };
    template <u32 Radix>
    struct prefix_impl<Radix, true> {
        using type = concat<digit_sequence<sizeof("0123456789abcdefghijklmnopqrstuvwxyz-")-2>, typename prefix_impl<Radix>::type>;
    };
    template <>
    struct prefix_impl<2> {
        using type = std::integer_sequence<u32, 0, 'b' - 'a' + 10>;
    };
    template <>
    struct prefix_impl<8> {
        using type = std::integer_sequence<u32, 0>;
    };
    template <>
    struct prefix_impl<16> {
        using type = std::integer_sequence<u32, 0, 'x' - 'a' + 10>;
    };
    template <u32 Radix, bool is_negative>
    using prefix = typename prefix_impl<Radix, is_negative>::type;
    
    template <u32 Radix, bool is_negative, typename Digits>
    struct integer;
    template <u32 Radix, bool is_negative, u32... I>
    struct integer<Radix, is_negative, digit_sequence<I...>>
      : std::conditional_t<(Radix <= 36),
                           integer_value<concat<prefix<Radix, is_negative>,
                                                std::conditional_t<sizeof...(I) == 0, digit_sequence<0>, digit_sequence<>>,
                                                reverse<digit_sequence<I...>>>>,
                           empty> {
        constexpr u32 operator[](std::size_t n) const {
            return at(n, digit_sequence<I...>{});
        }
    };
    ///////// from literal
    template <typename T, char... C>
    struct literal2integer_impl;
    template <u32 Radix, u32... I>
    struct literal2integer_impl<integer<Radix, false, digit_sequence<I...>>> {
        using type = integer<Radix, false, trim<digit_sequence<I...>>>;
    };
    template <u32 Radix, u32... I, char X, char... C>
    struct literal2integer_impl<integer<Radix, false, digit_sequence<I...>>, X, C...>
     : literal2integer_impl<integer<Radix, false, digit_sequence<X - ( X == '.' ? '.'
                                                                     : X <= '9' ? '0'
                                                                     : X <= 'Z' ? 'A' - 10
                                                                     : 'a' - 10 ), I...>>, C...> {
        static_assert( X != '.', "floating point literal not allowed when creating integer type" );
    };
    template <u32 Radix, u32... I, char... C>
    struct literal2integer_impl<integer<Radix, false, digit_sequence<I...>>, '\'', C...>
      : literal2integer_impl<integer<Radix, false, digit_sequence<I...>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, C...>
      : literal2integer_impl<integer<10, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', C...>
      : literal2integer_impl<integer<8, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'b', C...>
      : literal2integer_impl<integer<2, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'B', C...>
      : literal2integer_impl<integer<2, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'x', C...>
      : literal2integer_impl<integer<16, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'X', C...>
      : literal2integer_impl<integer<16, false, digit_sequence<>>, C...> {
    };
    template <>
    struct literal2integer_impl<void, '0'>
      : literal2integer_impl<integer<10, false, digit_sequence<>>> {
    };
    
    template <char... C>
    using literal2integer = typename literal2integer_impl<void, C...>::type;
    
    template <char... C>
    constexpr auto operator""_int() {
        return literal2integer<C...>{};
    }
    //////////
    // unary op
    template <u32 Radix, bool is_negative, u32... I>
    constexpr auto operator+(integer<Radix, is_negative, digit_sequence<I...>>) {
        return integer<Radix, is_negative, digit_sequence<I...>>{};
    }
    template <u32 Radix, bool is_negative, u32... I>
    constexpr auto operator-(integer<Radix, is_negative, digit_sequence<I...>>) {
        return integer<Radix, !is_negative && sizeof...(I) != 0, digit_sequence<I...>>{};
    }
    // comparison
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator==(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) {
        return std::is_same<decltype(lhs), decltype(rhs)>{};
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator!=(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) {
        return !std::is_same<decltype(lhs), decltype(rhs)>{};
    }
    
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator<(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) {
        if constexpr (lhs_is_negative != rhs_is_negative) {
            return lhs_is_negative;
        } else if constexpr (lhs_is_negative) {
            return -rhs < -lhs;
        } else if constexpr (sizeof...(I) != sizeof...(J)) {
            return sizeof...(I) < sizeof...(J);
        } else {
            for (auto i = sizeof...(I); i-- != 0; ) {
                if ( lhs[i] != rhs[i] ) {
                    return lhs[i] < rhs[i];
                }
            }
            return false;
        }
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator>(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) {
        return rhs < lhs;
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator<=(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) {
        return !( rhs < lhs );
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator>=(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) {
        return !( lhs < rhs );
    }
    //
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator+(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs);
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator-(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs);
    // addition
    template <u32 Radix, u32... I, u32... J, std::size_t... K>
    constexpr auto add(integer<Radix, false, digit_sequence<I...>> lhs,
                       integer<Radix, false, digit_sequence<J...>> rhs,
                       std::index_sequence<K...> indexes) {
        using sum_proto = digit_sequence<(at(K, digit_sequence<I...>{}) + at(K, digit_sequence<J...>{})) % Radix...>;
        using carry = trim<digit_sequence<0, (at(K, digit_sequence<I...>{}) + at(K, digit_sequence<J...>{})) >= Radix...>>;
        if constexpr (std::is_same<carry, digit_sequence<>>{}) {
            return integer<Radix, false, trim<sum_proto>>{};
        } else {
            return add(integer<Radix, false, sum_proto>{}, integer<Radix, false, carry>{}, indexes);
        }
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator+(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs)
    {
        if constexpr (lhs_is_negative) {
            return -( -lhs + -rhs );
        } else if constexpr (rhs_is_negative) {
            return lhs - -rhs;
        } else {
            return add(lhs, rhs, std::make_index_sequence<std::max(sizeof...(I), sizeof...(J))+1>{});
        }
    }
    // subtraction
    template <u32 Radix, u32... I, u32... J, std::size_t... K>
    constexpr auto sub(integer<Radix, false, digit_sequence<I...>> lhs,
                       integer<Radix, false, digit_sequence<J...>> rhs,
                       std::index_sequence<K...> indexes) {
        using difference_proto = digit_sequence<(Radix + at(K, digit_sequence<I...>{}) - at(K, digit_sequence<J...>{})) % Radix...>;
        using carry = trim<digit_sequence<0, (at(K,digit_sequence<I...>{}) < at(K, digit_sequence<J...>{}))...>>;
        if constexpr (std::is_same<carry, digit_sequence<>>{}) {
            return integer<Radix, false, trim<difference_proto>>{};
        } else {
            return sub(integer<Radix, false, difference_proto>{}, integer<Radix, false, carry>{}, indexes);
        }
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator-(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs)
    {
        if constexpr (lhs_is_negative) {
            return -( -lhs - -rhs );
        } else if constexpr (rhs_is_negative) {
            return lhs + -rhs;
        } else if constexpr (lhs < rhs) {
            return -( rhs - lhs );
        } else {
            return sub(lhs, rhs, std::make_index_sequence<sizeof...(I)>{});
        }
    }
    
    #include <iostream>
    int main() {
        auto a = 4242424242424242424242424242424242424242424242424242424242424242424242424242_int;
        auto b = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999_int;
        std::cout << a+b << ' ' << b+b << ' ' << a-b << ' ' << a-a << '\n';
    }
    


  • Hi

    Ich vermute, das Ganze wird deutlich deutlich schneller, wenn du die Zahlen wie Bignums ablegst und nicht wie BCDs. Ich versuch mich vll. auch noch dran und poste dann hier.

    LG

    PS: C++-Code-Tags wären besser geeignet. 🙂

    PPS: Wenn wir schon bei Sinnlosem sind; mein compile-time Mandelbrot-Renderer: https://github.com/Fytch/TemplMandel


  • Mod

    Fytch schrieb:

    Ich vermute, das Ganze wird deutlich deutlich schneller, wenn du die Zahlen wie Bignums ablegst und nicht wie BCDs. Ich versuch mich vll. auch noch dran und poste dann hier.

    Das ist durchaus schon angelegt (u32 statt char als Elementtyp), sollte aber bei den kleinen Werten gegenwärtig keine Rolle spielen. An irgendeinener Stelle will ich ja dann auch wieder einen ordentlichen String in Dezimaldarstellung haben, und dafür ist dann jede Menge Division erforderlich.

    Eine Verbesserung habe ich gefunden:

    //In add:
        using carry = trim<digit_sequence<0, (at(K, digit_sequence<I...>{}) + at(K, digit_sequence<J...>{})) >= Radix...>>;
        if constexpr (std::is_same<carry, digit_sequence<>>{}) {
    // --->
        using carry = digit_sequence<0, (at(K, digit_sequence<I...>{}) + at(K, digit_sequence<J...>{})) >= Radix...>;
        if constexpr (std::is_same<carry, digit_sequence<0, ((void)K, 0)...>>{}) {
    // sub analog
    

    g++ jetzt runter auf 3.5s, clang immer noch bei 7s - da kann nat. auch einiges an startup-Overhead dabei sein. Tendentiell passt es allerdings zu meinen Beobachtungen, die ich vor einigen Jahren gemacht habe (siehe TMP-Brainfuck) in Hinblick auf die Art und Weise, wie die Compiler variadische Templates intern repräsentieren und verarbeiten

    Fytch schrieb:

    PS: C++-Code-Tags wären besser geeignet. 🙂

    Sind da. Forensoftware spinnt mal wieder, evtl. ist auch bloß der Code zu lang.


  • Mod

    Noch ein bisschen dran gearbeitet. gcc jetzt runter auf 1.0s, clang bei 1.3s - dabei nur ein paar subtile Änderungen...

    #include <algorithm>
    #include <cstdint>
    #include <type_traits>
    #include <utility>
    
    using u32 = std::uint32_t;
    using u64 = std::uint64_t;
    
    template <u32... I>
    struct digit_sequence {
        using value_type = u32;
        static constexpr size_t size() noexcept { return sizeof...(I); }
        static constexpr const u32 data[sizeof...(I)+1] = { I... };
    };
    
    template <typename T>
    constexpr auto at(std::size_t n, T seq) noexcept {
        return n < T::size() ? T::data[n] : 0;
    }
    
    template <typename... T>
    struct concat;
    template <u32... I, u32... J>
    struct concat<digit_sequence<I...>, digit_sequence<J...>> {
        using type = digit_sequence<I..., J...>;
    };
    template <u32... I, u32... J, u32... K>
    struct concat<digit_sequence<I...>, digit_sequence<J...>, digit_sequence<K...>> {
        using type = digit_sequence<I..., J..., K...>;
    };
    template <typename... T>
    using concat_t = typename concat<T...>::type;
    
    template <typename T, typename = std::make_index_sequence<T::size()>>
    struct reverse;
    template <u32... I, std::size_t... J>
    struct reverse<digit_sequence<I...>, std::integer_sequence<std::size_t, J...>> {
        using type = digit_sequence<at(sizeof...(I) - 1 - J, digit_sequence<I...>{})...>;
    };
    template <typename T>
    using reverse_t = typename reverse<T>::type;
    
    template <u32... I, std::size_t... J>
    constexpr auto trim_helper(digit_sequence<I...> seq, std::integer_sequence<std::size_t, J...>) {
        return digit_sequence<seq.data[J]...>{};
    }
    template <u32... I>
    constexpr std::size_t trim_helper2(digit_sequence<I...> seq) {
        for (auto i = sizeof...(I); i-- != 0; ) {
            if (seq.data[i] != 0) {
                return i + 1;
            }
        }
        return 0;
    }
    template <u32... I>
    constexpr auto trim(digit_sequence<I...> seq) {
        return trim_helper(seq, std::make_index_sequence<trim_helper2(seq)>{});
    }
    template <typename T>
    using trim_t = decltype(trim(T{}));
    
    template <typename T>
    struct integer_value;
    template <u32... I>
    struct integer_value<digit_sequence<I...>>
    {
        static constexpr const char value[sizeof...(I)+1] = {"0123456789abcdefghijklmnopqrstuvwxyz-"[I]..., '\0'};
    };
    template <u32... I>
    constexpr const char integer_value<digit_sequence<I...>>::value[sizeof...(I)+1];
    struct empty {
    };
    template <u32 Radix, bool is_negative = false>
    struct prefix {
        using type = digit_sequence<>;
    };
    template <u32 Radix, bool is_negative = false>
    using prefix_t = typename prefix<Radix, is_negative>::type;
    template <u32 Radix>
    struct prefix<Radix, true> {
        using type = concat_t<digit_sequence<sizeof("0123456789abcdefghijklmnopqrstuvwxyz-")-2>, prefix_t<Radix>>;
    };
    template <>
    struct prefix<2> {
        using type = digit_sequence<0, 'b' - 'a' + 10>;
    };
    template <>
    struct prefix<8> {
        using type = digit_sequence<0>;
    };
    template <>
    struct prefix<16> {
        using type = digit_sequence<0, 'x' - 'a' + 10>;
    };
    
    template <u32 Radix, bool is_negative, typename Digits>
    struct integer;
    template <u32 Radix, bool is_negative, u32... I>
    struct integer<Radix, is_negative, digit_sequence<I...>> {
        constexpr u32 operator[](std::size_t n) const noexcept {
            return at(n, digit_sequence<I...>{});
        }
        constexpr operator const char*() const {
            return std::conditional_t<(Radix <= 36),
                           integer_value<concat_t<prefix_t<Radix, is_negative>,
                                                  std::conditional_t<sizeof...(I) == 0, digit_sequence<0>, digit_sequence<>>,
                                                  reverse_t<digit_sequence<I...>>>>,
                           empty>::value;
        }
    
    };
    ///////// from literal
    template <typename T, char... C>
    struct literal2integer_impl;
    template <u32 Radix, u32... I>
    struct literal2integer_impl<integer<Radix, false, digit_sequence<I...>>> {
        using type = integer<Radix, false, trim_t<digit_sequence<I...>>>;
    };
    template <u32 Radix, u32... I, char X, char... C>
    struct literal2integer_impl<integer<Radix, false, digit_sequence<I...>>, X, C...>
     : literal2integer_impl<integer<Radix, false, digit_sequence<X - ( X == '.' ? '.'
                                                                     : X <= '9' ? '0'
                                                                     : X <= 'Z' ? 'A' - 10
                                                                     : 'a' - 10 ), I...>>, C...> {
        static_assert( X != '.', "floating point literal not allowed when creating integer type" );
    };
    template <u32 Radix, u32... I, char... C>
    struct literal2integer_impl<integer<Radix, false, digit_sequence<I...>>, '\'', C...>
      : literal2integer_impl<integer<Radix, false, digit_sequence<I...>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, C...>
      : literal2integer_impl<integer<10, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', C...>
      : literal2integer_impl<integer<8, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'b', C...>
      : literal2integer_impl<integer<2, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'B', C...>
      : literal2integer_impl<integer<2, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'x', C...>
      : literal2integer_impl<integer<16, false, digit_sequence<>>, C...> {
    };
    template <char... C>
    struct literal2integer_impl<void, '0', 'X', C...>
      : literal2integer_impl<integer<16, false, digit_sequence<>>, C...> {
    };
    template <>
    struct literal2integer_impl<void, '0'>
      : literal2integer_impl<integer<10, false, digit_sequence<>>> {
    };
    
    template <char... C>
    using literal2integer_t = typename literal2integer_impl<void, C...>::type;
    
    template <char... C>
    constexpr auto operator""_int() noexcept {
        return literal2integer_t<C...>{};
    }
    //////////
    // unary op
    template <u32 Radix, bool is_negative, u32... I>
    constexpr auto operator+(integer<Radix, is_negative, digit_sequence<I...>>) noexcept {
        return integer<Radix, is_negative, digit_sequence<I...>>{};
    }
    template <u32 Radix, bool is_negative, u32... I>
    constexpr auto operator-(integer<Radix, is_negative, digit_sequence<I...>>) noexcept {
        return integer<Radix, !is_negative && sizeof...(I) != 0, digit_sequence<I...>>{};
    }
    // comparison
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator==(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept {
        return std::is_same<decltype(lhs), decltype(rhs)>{};
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator!=(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept {
        return !std::is_same<decltype(lhs), decltype(rhs)>{};
    }
    
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator<(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept {
        if constexpr (lhs_is_negative != rhs_is_negative) {
            return lhs_is_negative;
        } else if constexpr (lhs_is_negative) {
            return -rhs < -lhs;
        } else if constexpr (sizeof...(I) != sizeof...(J)) {
            return sizeof...(I) < sizeof...(J);
        } else {
            for (auto i = sizeof...(I); i-- != 0; ) {
                if ( lhs[i] != rhs[i] ) {
                    return lhs[i] < rhs[i];
                }
            }
            return false;
        }
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator>(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept {
        return rhs < lhs;
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator<=(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept {
        return !( rhs < lhs );
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr bool operator>=(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                              integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept {
        return !( lhs < rhs );
    }
    //
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator+(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept;
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator-(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept;
    // addition
    template <u32 Radix, u32... I, u32... J, std::size_t... K>
    constexpr auto add(integer<Radix, false, digit_sequence<I...>> lhs,
                       integer<Radix, false, digit_sequence<J...>> rhs,
                       std::integer_sequence<std::size_t, K...> indexes) noexcept {
        using sum_proto = digit_sequence<(lhs[K] + rhs[K]) % Radix...>;
        using carry = trim_t<digit_sequence<0, (lhs[K] + rhs[K]) >= Radix...>>;
        if constexpr (carry::size() == 0) {
            return integer<Radix, false, trim_t<sum_proto>>{};
        } else {
            return add(integer<Radix, false, sum_proto>{}, integer<Radix, false, carry>{}, indexes);
        }
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator+(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept
    {
        if constexpr (lhs_is_negative) {
            return -( -lhs + -rhs );
        } else if constexpr (rhs_is_negative) {
            return lhs - -rhs;
        } else {
            return add(lhs, rhs, std::make_index_sequence<std::max(sizeof...(I), sizeof...(J))+1>{});
        }
    }
    // subtraction
    template <u32 Radix, u32... I, u32... J, std::size_t... K>
    constexpr auto sub(integer<Radix, false, digit_sequence<I...>> lhs,
                       integer<Radix, false, digit_sequence<J...>> rhs,
                       std::integer_sequence<std::size_t, K...> indexes) noexcept {
        using difference_proto = digit_sequence<(Radix + lhs[K] - rhs[K]) % Radix...>;
        using carry = trim_t<digit_sequence<0, (lhs[K] < rhs[K])...>>;
        if constexpr (carry::size() == 0) {
            return integer<Radix, false, trim_t<difference_proto>>{};
        } else {
            return sub(integer<Radix, false, difference_proto>{}, integer<Radix, false, carry>{}, indexes);
        }
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator-(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept
    {
        if constexpr (lhs_is_negative) {
            return -( -lhs - -rhs );
        } else if constexpr (rhs_is_negative) {
            return lhs + -rhs;
        } else if constexpr (lhs < rhs) {
            return -( rhs - lhs );
        } else {
            return sub(lhs, rhs, std::make_index_sequence<sizeof...(I)>{});
        }
    }
    
    #include <iostream>
    int main() {
        auto a = 4242424242424242424242424242424242424242424242424242424242424242424242424242_int;
        auto b = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999_int;
        std::cout << a+b << ' ' << b+b << ' ' << a-b << ' ' << a-a << '\n';
    }
    

    Ein paar allgemeine Beobachtungen, die die Geschwindigkeit beeinflussen:
    - Aliastemplates als Parameter in Funktionstemplates oder Templateparameterlisten partieller Spezialisierungen kosten extra (ich hatte eigentlich angenommen, dass der Compiler diese bereits bei der Definition der jeweiligen Entität substituiert). Daher die Verwendung von std::integer_sequence<std::size_t, ... an Stelle von std::index_sequence<...
    - werden die Zwischenwerte nicht gebraucht, kann es zweckmäßig sein, tiefe Instantiierungsrekursion von Klassentemplates durch constexpr-Funktionen zu ersetzen, weil das Ergebnis des Funktionsaufrufes nicht gespeichert werden muss.



  • constexpr statt der aufwendigen template-maschinerie compiliert sehr schnell und erzeugt kleinere asm- und executables. Nur schlichte Addition implementiert:

    #include <array>
    #include <cstddef>
    #include <iostream>
    #include <stdexcept>
    
    constexpr auto constexpr_strlen(const char* str) { 
      std::size_t anzahl = 0;
      while(*str++) { ++anzahl; }
      return anzahl;
    }
    
    class BigInt {
    public:
      static constexpr std::size_t SIZE {1000};
    
      constexpr void set(std::size_t i, char c) {
        arr[i] = c - '0';
      }
      constexpr auto get(std::size_t i) const {
        return arr[i];
      }
      constexpr auto size() const {
        return size_;
      }
      constexpr void size(std::size_t s) {
        size_ = s;
      }
    
      constexpr BigInt& operator+=(const BigInt& b) {
        if(size_ < b.size()) {
          size_ = b.size();
        }
        auto ende = BigInt::SIZE - size_ -1;
        for(auto i = BigInt::SIZE -1; i > ende; --i) {
          auto sum = arr[i] + b.arr[i];
          auto carry = sum > 9;
          if(carry) {
            sum -= 10;
            ++arr[i-1];
          }
          arr[i] = sum;
        }
        if(arr[ende] > 0) {
          ++size_;
        }
        return *this;
      }
    private:
      std::array<char, SIZE> arr {0};
      std::size_t size_ {0};
    };
    
    constexpr auto operator+(BigInt a, const BigInt& b) {
      return a += b;
    }
    
    std::ostream& operator<<(std::ostream& os, const BigInt& b) {
      for(auto i = BigInt::SIZE - b.size(); i < BigInt::SIZE; ++i) {
        os << static_cast<char>(b.get(i) + '0');
      }
      return os;
    }
    
    constexpr auto operator"" _int(const char* digits) {
      BigInt b;
      b.size(constexpr_strlen(digits));
      auto i = b.size();
      while (*digits) {
        // schlägt ggf. bereits bei der Compilation fehl!
        if (*digits < '0' || *digits > '9') {
          throw std::runtime_error("unerlaubtes Zeichen im String");
        }
        b.set(BigInt::SIZE - i--, *digits++);
      }
      return b;
    }
    
    int main() {
      constexpr auto a = 4242424242424242424242424242424242424242424242424242424242424242424242424242_int;
      constexpr auto b = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999_int;
      std::cout << a+b << ' ' << b+b << '\n';
    }
    

    Einschränkung: SIZE muss vorher als Maximale Stellenzahl festgelegt werden.


  • Mod

    constexpr warum nicht schrieb:

    constexpr statt der aufwendigen template-maschinerie compiliert sehr schnell und erzeugt kleinere asm- und executables.

    Kann ich nicht uneingeschränkt bestatigen.
    Das die Asm- und Objektdateien kleiner werden, ist zu erwarten, weil die TMP-Variante mehr und längere Bezeichner benötigt.
    Wenn ich bei beiden Varianten die gleiche Main

    auto a = 4242424242424242424242424242424242424242424242424242424242424242424242424242_int;
        auto b = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999_int;
        std::cout << a+b << ' ' << b+b << '\n';
    

    zugrundelege, erhalte ich mit clang (-O3):

    TMP         constexpr
    1.30s       0.88s          (Minimum von 10x Compilieren)
    415 MiB     332 MiB        (maximaler Speicherbedarf des Compiler)
    6360 B      8084 B         (Objektdatei)
    10552 B     10560 B        (executable - stripped)
    

    nicht wie erwartet. Und der Asm-Code, den clang für deine Variante erzeugt, sieht auch sehr seltsam aus.

    gcc 7.1.0:

    TMP         constexpr
    0.99s       0.46s          (Minimum von 10x Compilieren)
    467 MiB     259 MiB        (maximaler Speicherbedarf des Compiler)
    5280 B      4964 B         (Objektdatei)
    6016 B      10112 B        (executable - stripped)
    

    Das passt schon eher.

    Hm...

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


  • Mod

    constexpr warum nicht schrieb:

    Nur schlichte Addition implementiert:

    ...
    

    Einschränkung: SIZE muss vorher als Maximale Stellenzahl festgelegt werden.

    Danke für die Inspiration, mit

    // addition
    template <u32 Radix, u32... I, u32... J, std::size_t... K>
    constexpr auto add_helper(integer<Radix, false, digit_sequence<I...>> lhs,
                              integer<Radix, false, digit_sequence<J...>> rhs) noexcept {
        std::array<u32, std::max(sizeof...(I), sizeof...(J)) + 1> sum = {};
        u32 carry = 0;
        for (std::size_t i = 0; i <= std::max(sizeof...(I), sizeof...(J)); ++i) {
            if ( Radix - lhs[i] - carry <= rhs[i] ) {
                sum[i] = rhs[i] + lhs[i] + carry - Radix;
                carry = 1;
            } else {
                sum[i] = rhs[i] + lhs[i] + carry;
                carry = 0;
            }
        }
        return sum;
    }
    template <u32 Radix, bool is_negative, u32... I, u32... J, std::size_t... K>
    constexpr auto add(integer<Radix, is_negative, digit_sequence<I...>> lhs,
                       integer<Radix, is_negative, digit_sequence<J...>> rhs,
                       std::integer_sequence<std::size_t, K...> indexes) noexcept {
        constexpr auto sum_data = add_helper(lhs, rhs);
        return integer<Radix, is_negative, trim_t<digit_sequence<sum_data[K]...>>>{};
    }
    template <u32 Radix, bool lhs_is_negative, u32... I, bool rhs_is_negative, u32... J>
    constexpr auto operator+(integer<Radix, lhs_is_negative, digit_sequence<I...>> lhs,
                             integer<Radix, rhs_is_negative, digit_sequence<J...>> rhs) noexcept
    {
        if constexpr (lhs_is_negative == rhs_is_negative) {
            return add(lhs, rhs, std::make_index_sequence<std::max(sizeof...(I), sizeof...(J))+1>{});
        } else if constexpr (lhs_is_negative) {
            return rhs - -lhs;
        } else {
            return lhs - -rhs;
        }
    }
    

    Bin ich praktisch genauso schnell, ohne die künstliche Einschränkung, einer vorgegebenen Maximalgrösse.
    Der komplizierte Templatecode war dort vorher, weil mir keine Methode eingefallen war, wie ich constexpr-berechnete Daten wieder als Temlateparameter einsetzen kann. Schliesslich ist ja z.B. hier sum_data innerhalb von add_helper kein konstanter Ausdruck. Wie so oft löst Indirektion das Problem 🙂



  • 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