Changeset 33148 in project


Ignore:
Timestamp:
01/28/16 22:29:26 (3 years ago)
Author:
sjamaan
Message:

numbers: Remove yet another pathological case in Burnikel/Ziegler?. We can now revert to the original implementation; reason behind the original slowness was that you shouldn't divide recursively if Y is too small

Location:
release/4/numbers/trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • release/4/numbers/trunk/benchmarks/big-prime.scm

    r33143 r33148  
    66(define big-prime (time (- (expt 2 74207281) 1)))
    77
     8;; This caused pathological behaviour in Burnikel/Ziegler division,
     9;; while being lightning fast with "traditional" division.
     10(display "Perf sanity check...")
     11(time (begin (quotient (- (expt 2 74207281) 1) (expt 10 100)) #f))
     12
    813(display "Converting to hex...")
    914(time (begin (number->string big-prime 16) #f))
  • release/4/numbers/trunk/numbers-c.c

    r33133 r33148  
    32823282  default:
    32833283    size = C_bignum_size(x) - C_bignum_size(y);
    3284     if (size > C_BURNIKEL_ZIEGLER_DIFF_THRESHOLD) {
     3284    if (C_bignum_size(y) > C_BURNIKEL_ZIEGLER_THRESHOLD &&
     3285        size > C_BURNIKEL_ZIEGLER_THRESHOLD) {
    32853286      try_extended_number("numbers#@bignum-2-divrem-burnikel-ziegler", 5,
    32863287                          k, x, y, return_q, return_r);
  • release/4/numbers/trunk/numbers-c.h

    r32729 r33148  
    103103 * division.  It creates even more garbage than Karatsuba :(
    104104 */
    105 #define C_BURNIKEL_ZIEGLER_DIFF_THRESHOLD 300
     105#define C_BURNIKEL_ZIEGLER_THRESHOLD 300
    106106/* This threshold is in terms of the expected string length.  It
    107107 * depends on division speed: if you change the above, change this too.
  • release/4/numbers/trunk/numbers.scm

    r33133 r33148  
    538538  (define-inline (digit-bits n)
    539539    (fx* (foreign-value "C_BIGNUM_DIGIT_LENGTH" int) n))
    540   (define DIV-LIMIT (foreign-value "C_BURNIKEL_ZIEGLER_DIFF_THRESHOLD" int))
     540  (define DIV-LIMIT (foreign-value "C_BURNIKEL_ZIEGLER_THRESHOLD" int))
    541541
    542542  ;; Here and in 2n/1n we pass both b and [b1, b2] to avoid splitting
     
    560560
    561561  (define (burnikel-ziegler-2n/1n a b b1 b2 n)
    562     (if (or (fxodd? n) (fixnum? a) (fixnum? b)
    563             ;; Paper says we should check for N being less than
    564             ;; DIV-LIMIT, but in practice that causes performance
    565             ;; stability issues.  Instead, we look at the actual
    566             ;; difference between the numbers (idea taken from MCA,
    567             ;; Algorithm 1.9).
    568             (fx< (fx- (bignum-digit-count a) (bignum-digit-count b))
    569                  DIV-LIMIT))
     562    (if (or (fxodd? n) (fx< n DIV-LIMIT))
    570563        ((##core#primitive "C_u_integer_divrem") a b)
    571564        (let* ((n/2 (fxshr n 1))
Note: See TracChangeset for help on using the changeset viewer.