What kind of speedup are we talking, like approx % on + - % * for bignum integers and bignum rationals, of size ~10^25/~10^25?

For bignum rationals I guess GCD calculation is what really the heaviest work; will this make GCD calculation faster too?


2015-01-18 2:49 GMT+05:30 Bradley Lucier <lucier@math.purdue.edu>:
I just noticed this in

https://gcc.gnu.org/gcc-5/changes.html

  • A new set of built-in functions for arithmetics with overflow checking has been added: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow and for compatibility with clang also other variants. These builtins have two integral arguments (which don't need to have the same type), the arguments are extended to infinite precision signed type, +, - or * is performed on those, and the result is stored in an integer variable pointed to by the last argument. If the stored value is equal to the infinite precision result, the built-in functions return false, otherwise true. The type of the integer variable that will hold the result can be different from the types of the first two arguments. The following snippet demonstrates how this can be used in computing the size for the calloc function:
    void *
    calloc (size_t x, size_t y)
    {
      size_t sz;
      if (__builtin_mul_overflow (x, y, &sz))
        return NULL;
      void *ret = malloc (sz);
      if (ret) memset (res, 0, sz);
      return ret;
    }
    
    On e.g. i?86 or x86-64 the above will result in a mul instruction followed by a jump on overflow.

  • Maybe we can exploit this to improve the speed of bignum arithmetic.

    Brad

    _______________________________________________
    Gambit-list mailing list
    Gambit-list@iro.umontreal.ca
    https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list