Function extendedMultNaive

tests/SelfTest/IntrospectiveTests/Integer.tests.cpp:26–73

Simple (and slow) implementation of extended multiplication for tests

    // Simple (and slow) implementation of extended multiplication for tests
    constexpr Catch::Detail::ExtendedMultResult<std::uint64_t>
    extendedMultNaive( std::uint64_t lhs, std::uint64_t rhs ) {
        // This is a simple long multiplication, where we split lhs and rhs
        // into two 32-bit "digits", so that we can do ops with carry in 64-bits.
        //
        //            32b    32b    32b    32b
        //     lhs                  L1     L2
        //   * rhs                  R1     R2
        //            ------------------------
        //                       |  R2 * L2  |
        //                 |  R2 * L1  |
        //                 |  R1 * L2  |
        //           |  R1 * L1  |
        //           -------------------------
        //           |  a  |  b  |  c  |  d  |

#define CarryBits( x ) ( (x) >> 32 )
#define Digits( x ) ( (x) & 0xFF'FF'FF'FF )

        auto r2l2 = Digits( rhs ) * Digits( lhs );
        auto r2l1 = Digits( rhs ) * CarryBits( lhs );
        auto r1l2 = CarryBits( rhs ) * Digits( lhs );
        auto r1l1 = CarryBits( rhs ) * CarryBits( lhs );

        // Sum to columns first
        auto d = Digits( r2l2 );
        auto c = CarryBits( r2l2 ) + Digits( r2l1 ) + Digits( r1l2 );
        auto b = CarryBits( r2l1 ) + CarryBits( r1l2 ) + Digits( r1l1 );
        auto a = CarryBits( r1l1 );

        // Propagate carries between columns
        c += CarryBits( d );
        b += CarryBits( c );
        a += CarryBits( b );

        // Remove the used carries
        c = Digits( c );
        b = Digits( b );
        a = Digits( a );

#undef CarryBits
#undef Digits

        return {
            a << 32 | b, // upper 64 bits
            c << 32 | d  // lower 64 bits
        };
    }


} // namespace