Changeset 3784


Ignore:
Timestamp:
Jan 14, 2015, 9:23:52 AM (7 years ago)
Author:
sam
Message:

math: bigint multiplication (the naïve O(n²) algorithm for now).

Location:
trunk
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/demos/test/sandbox/sample.cpp

    r3782 r3784  
    2424    bigint<16> x(2), y(12);
    2525    auto z = x + y;
    26     printf("%d\n", (int)z);
     26    printf("0x%x\n", (int)z);
     27    z.print();
    2728
    2829    bigint<0> lol;
    2930    auto w = z + lol;
    30     printf("%d\n", (int)w);
     31    printf("0x%x\n", (int)w);
     32
     33    bigint<2> f(0x10101010), g(0x20202020);
     34    (f * f * f * g - g).print();
    3135}
    3236
  • trunk/src/lol/math/bigint.h

    r3783 r3784  
    208208     * bigint subtraction: a combination of addition and unary minus;
    209209     * we add the result of flipping digits and adding one.
     210     * FIXME: this could be factored with operator+().
    210211     */
    211212    template<unsigned int M>
     
    228229
    229230    /*
     231     * bigint multiplication: the resulting integer has as many digits
     232     * as the sum of the two operands.
     233     */
     234    template<unsigned int M>
     235    bigint<N + M, T> operator *(bigint<M,T> const &x) const
     236    {
     237        /* FIXME: other digit sizes are not supported */
     238        static_assert(sizeof(T) == sizeof(uint32_t), "ensure T is uint32_t");
     239
     240        if (x.is_negative())
     241            return -(*this * -x);
     242        if (is_negative())
     243            return -(-*this * x);
     244
     245        bigint<N + M> ret(0);
     246        for (unsigned int i = 0; i < N; ++i)
     247        {
     248            T carry(0);
     249            for (unsigned int j = 0; j < M; ++j)
     250            {
     251                uint64_t digit = ret.m_digits[i + j]
     252                               + (uint64_t)m_digits[i] * x.m_digits[j]
     253                               + carry;
     254                ret.m_digits[i + j] = (T)digit & digit_mask;
     255                carry = (digit >> bits_per_digit) & digit_mask;
     256            }
     257
     258            for (unsigned int j = M; i + j < M + N && carry != 0; ++i)
     259            {
     260                T digit = ret.m_digits[i + j] + carry;
     261                ret.m_digits[i + j] = (T)digit & digit_mask;
     262                carry = (digit & ~digit_mask) ? T(1) : T(0);
     263            }
     264        }
     265
     266        return ret;
     267    }
     268
     269    /*
    230270     * bigint equality operator: just use memcmp.
    231271     * FIXME: we could easily support operands of different sizes.
     
    275315    }
    276316
     317    void print() const
     318    {
     319        printf("0x");
     320
     321        int n = (bits_per_digit * N + 31) / 32;
     322        while (n > 1 && get_uint32(n) == 0)
     323            --n;
     324
     325        if (n > 0)
     326            printf("%x", get_uint32(--n));
     327        while (n--)
     328            printf("%08x", get_uint32(n));
     329
     330        printf("\n");
     331    }
     332
    277333private:
    278334    /* Allow other types of bigints to access our private members */
     
    283339        if (N < 1)
    284340            return false;
    285         return (m_digits[N - 1] & ((T)1 << (bits_per_digit - 1))) != 0;
     341        return (m_digits[N - 1] >> (bits_per_digit - 1)) != 0;
     342    }
     343
     344    inline uint32_t get_uint32(int offset) const
     345    {
     346        unsigned int bit = offset * 32;
     347        unsigned int digit_index = bit / bits_per_digit;
     348        unsigned int bit_index = bit % bits_per_digit;
     349
     350        if (digit_index >= N)
     351            return 0;
     352
     353        uint32_t ret = m_digits[digit_index] >> bit_index;
     354        if (bits_per_digit - bit_index < 32 && digit_index < N - 1)
     355            ret |= m_digits[digit_index + 1] << (bits_per_digit - bit_index);
     356        return ret;
    286357    }
    287358
Note: See TracChangeset for help on using the changeset viewer.