[Libre-soc-isa] [Bug 817] Big Integer Math (sv.adde, sv.subfe, sv.madded, 128 by 64-bit -> 64-bit div/rem, maybe more...)

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=817

--- Comment #13 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #11)
> oink moment, why are we not doing Big-Integer Goldschmidt? :)
> 
> https://lists.libre-soc.org/pipermail/libre-soc-dev/2022-April/004772.html

because goldschmidt's algorithm is much slower at small bigint sizes (small
enough that the fastest multiplication algorithm is O(N^2)):
for a 2*N x N -> N word division, Algorithm D does approximately 2*N*N word
operations -- Goldschmidt Division does around log2(N)*8*N*N word operations.

When bigints are bigger, then there are faster software algorithms than either
Algorithm D or Goldschmidt Division, such as divide and conquer algorithms
(good for medium-length bigints) and Block-Wise Barrett Division (good for
large bigints).

There's also the important case of a bigint divided by a single word, where the
algorithm is basically:
uint64_t n[n_size], d; // n has most-significant word in n[n_size - 1]
uint64_t carry = 0;
for(i = n_size; i > 0; i--)
{
    uint128_t v = ((uint128_t)carry << 64) | n[i - 1];
    carry = v % d;
    n[i - 1] = v / d;
}
// n is the quotient, carry is the remainder

see https://gmplib.org/manual/Division-Algorithms

-- 
You are receiving this mail because:
You are on the CC list for the bug.