Re: Another implementation of Bignum [I'm working with 1.7.2]

-----Original Message-----
From: [e-mail] (Yukihiro Matsumoto)
To: [e-mail]
Date: Sat, 8 Jun 2002 03:32:21 +0900
Subject: Re: Another implementation of Bignum [tarball attached]

> One more note: this kind of enhancement will never be merged to the
> stable version (1.6.x), so the patch is better be prepared against > the
development version (the lastest CVS trunk).

----------------

  I'm finished merging my Bignums with 1.7.2 shapshot dated
2002-06-04. All issues listed in README within my previous tarball are fixed
(except for round-up differences).

  Bignum <-> LONG_LONG interoperability and rb_quad_pack/rb_quad_unpack are
implemented, but not well-tested. It's hard to handle all possible pairs of
Ruby/GMP configuratons
(GMP digit (`mp_limb_t') may be `unsigned int' or
`unsigned long long it' depend on configuration).

  Packing with "q" or "Q" seems works wrong in 1.7.2 2002-06-04. The
following test reports 8 errors:

$packerrors = 0

def testpackunpack(lineno, description, packtype, array)
  packformat = packtype * array.size
  data = array.pack(packformat)
  newarray = data.unpack(packformat)
  if newarray != array
    print "*** Pack test #{lineno}:#{description} FAILED for array [ "
    array.each {|x| print x.to_s + " "}
    puts "] ***"
    $packerrors += 1
  else
    puts lineno.to_s + ":" + description + ": " + newarray.to_s
  end
end

testpackunpack(__LINE__, "pack/unpack [], q", "q", [])
testpackunpack(__LINE__, "pack/unpack [], Q", "Q", [])

testpackunpack(__LINE__, "pack/unpack [Fixnum], q", "q", [345])
testpackunpack(__LINE__, "pack/unpack [Fixnum], q", "q", [-345])
testpackunpack(__LINE__, "pack/unpack [Fixnum], Q", "Q", [345])
testpackunpack(__LINE__, "pack/unpack [Fixnum], Q", "Q", [-345])

testpackunpack(__LINE__, "pack/unpack [Fixnum, Fixnum...], q", "q",
        [74467456, -45646745, 634643164, -54163463])
testpackunpack(__LINE__, "pack/unpack [Fixnum, Fixnum...], Q", "Q",
        [74467456, -45646745, 634643164, -54163463])

testpackunpack(__LINE__, "pack/unpack [Bignum], q", "q",
        [79238423645234234564752345234672345672345723423452345])
testpackunpack(__LINE__, "pack/unpack [Bignum], q", "q",
        [-79238423645234234564752345234672345672345723423452345])
testpackunpack(__LINE__, "pack/unpack [Bignum], Q", "Q",
        [79238423645234234564752345234672345672345723423452345])
testpackunpack(__LINE__, "pack/unpack [Bignum], Q", "Q",
        [-79238423645234234564752345234672345672345723423452345])

testpackunpack(__LINE__, "pack/unpack [Bignum, Bignum...], q", "q",
        [80374658734657834657343465345343465834653434,
   -823456856378456365378456347856347856348,
   928345623895685627834563784563478653478563784563478,
   -378465347896578345634785634785634856347856347856347856])
testpackunpack(__LINE__, "pack/unpack [Bignum, Bignum...], Q", "Q",
        [80374658734657834657343465345343465834653434,
   -823456856378456365378456347856347856348,
   928345623895685627834563784563478653478563784563478,
   -378465347896578345634785634785634856347856347856347856])

puts "#{$packerrors} pack/unpack errors occursed"

----------------

Question: how can I check LONG_LONG <-> Bignum interoperability ?

----------------

I'm thinking about 4 new number theoretic functions
(`Integer' means `Fixnum or Bignum'):

- Integer.gcd(Integer) -> Integer
  Return a greatest common divisor

- Integer.lcm(Integer) -> Integer
  Return a least common multiple

- Integer.prime? -> true or false
  Return true if Integer is prime, false otherwise

- Integer.factorize -> array of factors with exponents
  For example:
  17.factorize -> [17] (17 is prime)
  36.factorize -> [[2, 2], [3, 2]] (36 = 2^2 * 3^2)
  645645654.factorize -> [2, [3, 5], 137, 9697]
                         (645645654 =  2 * 3^5 * 137 * 9697)

These are a common tasks for numerical algorithms and appropriate functions
(IMHO) will be quite useful. The impelementation for Fixnum is not hard, but
it's a serious task to implement fast `prime?' and `factorize' for Bignums.

Any ideas ?

----------------

Dmitry