Class: Bignum

Inherits:
Object show all
Defined in:
(unknown)

Instance Method Summary collapse

Instance Method Details

#factorize ⇒ Object

timer(100000) Bignum.10737418231073741823.factorize

> “res: [3, 3, 7, 11, 31, 151, 331], one: 0.0053ms, total: 530.0ms”

ruby count Bignums starting from 2**30 < 2**30: x1-x30 speed, >= 2**30: x1 - x3 speed ~_~ Caution! It can just hung up on numbers over 2**64 and you’ll have to kill it -9 And this shit doesn’t think if you have 64-bit system, so it could be faster a bit



467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
 
# File 'ext/rmtools.cpp', line 467

static VALUE rb_math_big_factorization(VALUE y) {
  VALUE factors = rb_ary_new2(127);
  int len = 0;
  long n = 2;
  int cont = 0;
  VALUE big_n, divmod, mod;
  while (unsigned_big_lte(rb_int2big(n*n), y)) {
      divmod = rb_big_divmod(y, rb_int2big(n));
      mod = RARRAY_PTR(divmod)[1];
  
      if (FIXNUM_P(mod) && !FIX2LONG(mod)) {
          y = RARRAY_PTR(divmod)[0];
          if (FIXNUM_P(y)) y = rb_int2big(FIX2LONG(y));
          rb_ary_store(factors, len++, LONG2FIX(n));
      } else {
          n++;
          if (n == 46341) {
            big_n = rb_int2big(n);
            cont = 1;
            break;
          }
      }
  }
  if (cont)
    while (unsigned_big_lte(rb_big_mul(big_n, big_n), y)) {
      divmod = rb_big_divmod(y, big_n);
      mod = RARRAY_PTR(divmod)[1];
    
      if (FIXNUM_P(mod) && !FIX2LONG(mod)) {
          y = RARRAY_PTR(divmod)[0];
          if (FIXNUM_P(y)) y = rb_int2big(FIX2LONG(y));
          rb_ary_store(factors, len++, big_n);
      } else {
        big_n = (n < LONG_MAX) ? rb_int2big(++n) : rb_big_plus(big_n, rb_int2big(1));
      }
    }
  rb_ary_store(factors, len++, y);
  ARY_SET_LEN(factors, len);
  return factors;
}