From: eric@... (Eric Lee Green)
Date: 2001-08-04T14:08:39+09:00
Subject: [ruby-talk:19106] Re: Endianness and integer indexing

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sat, 04 Aug 2001 03:40:12 GMT, Harry Ohlsen <harryo@zip.com.au> wrote:
>> For those wondering why I did this, here is a mod_exp routine
>> for calculating z**n % q for very large numbers such as are used
>> in public key encryption:
>
>Sorry, I can't answer your question, but thanks for the code.  I was 
>literally just about to write the same thing!

Oh, okay. I've noticed an interesting thing about [] though -- it is
almost as slow as doing a " % 2" on the number! 

This especially shows up in the gcd (greatest common denominator) code:

Here is the classic Euclidean algorithm, which involves a division and
thus should be fairly slow (this is part of the Crypto_math module, and
thus gets included in both Integer and Bignum when I do the 'include
Crypto_math' in both of them). 

  # Find the gcd of two numbers, self and i, using the
  # Euclidean algorithm. Seems to work fairly fast!
  def gcd(i)
    n=self.clone
    if n >= i
      a=n
      b=i.clone
    else
      a=i.clone
      b=n
    end
    
    while b > 0
      r = a % b
      a = b.clone
      b= r.clone
    end
    return a
  end

Here is Stein's binary GCD, which has no multiplication or division
in it and thus supposedly will run much faster than the Euclidean
algorithm:

  # Stein's binary gcd, for test purposes: Algorithm B from
  # Knuth sec. 4.5.2. This is actually slower than the above
  # routine at the moment, apparently bigint [] is very slow :-(.

  def gcdb(i)
    k=0
    n=self.clone

    if n >= i
      u=n
      v=i.clone
    else
      u=i.clone
      v=n
    end

    # Now, test both for even-ness:
    while u[0]==0 && v[0]==0
      k=k+1
      u>>=1
      v>>=1
    end
    
    # okay, they've been divided by 2**k, and at least one
    # of their present values is odd:

    if u[0]==1
      t=-v
    else
      t=u
    end

    while t != 0
      while t[0]==0
	t>>=1  # halve it.
      end
      
      if t > 0
	u = t
      else
	v = -t
      end
      
      t = u - v
    end
    return u * (1 << k)
  end
end

Here is a quicky random number generator:

  # define a random number of size <self>. <self> is a number of bytes, 
  # *NOT* a  # of bits! This will need to be modified to
  # work on anything other than Unix, because it uses /dev/urandom. If you
  # are on a Unix without a dev/urandom, such as Solaris, use
  # Ocotillo (http://ocotillo.sourceforge.net) as your PRNG. 
  def random()
    n=self.clone
    fh=open("/dev/urandom","r")
    if (!fh) 
      fh=open("/dev/orandom","r")  # optional place.
    end
    if (!fh)
      raise "NO RANDOM DEVICE"
    end
    
    i=0
    s=fh.read(n)
    while (n > 0)
      n -= 1
      i = i << 8
      i  = i | s[n]  # yep, a 1 char slice in an integer context is guess what?
    end
    fh.close()
    return i
  end

And finally, to put it all together, here's a couple of tests:

% ruby  -r profile -e 'require "modexp.rb"' -e "10.times do a=128.random ;
a.gcdb(128.random) ; end"
 %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 55.18     8.09      8.09       10   809.00  1271.00  Crypto_math.gcdb
  9.00     9.41      1.32       20    66.00    97.00  Crypto_math.random
  6.62    10.38      0.97    20902     0.05     0.05  Bignum#[]
  6.48    11.33      0.95    21744     0.04     0.04  Fixnum#==
  5.05    12.07      0.74    13853     0.05     0.05  Bignum#>>
  4.50    12.73      0.66     7025     0.09     0.14  Comparable.>
  2.52    13.10      0.37     7035     0.05     0.05  Bignum#-
  2.46    13.46      0.36     7038     0.05     0.05  Bignum#==
  2.18    13.78      0.32     7035     0.05     0.05  Bignum#<=>
  1.23    13.96      0.18     2765     0.07     0.07  Fixnum#-
  1.16    14.13      0.17     2474     0.07     0.07  Bignum#<<
  1.09    14.29      0.16     3512     0.05     0.05  Bignum#-@
  0.68    14.39      0.10     2494     0.04     0.04  Bignum#|
  0.61    14.48      0.09     2791     0.03     0.03  Fixnum#>
  0.41    14.54      0.06      423     0.14     0.14  Fixnum#>>
  0.41    14.60      0.06     2560     0.02     0.02  String#[]
  0.14    14.62      0.02      634     0.03     0.03  Fixnum#[]
  0.07    14.63      0.01       66     0.15     0.15  Fixnum#|
  0.07    14.64      0.01        1    10.00    10.00  Kernel.require
  0.07    14.65      0.01       40     0.25     0.25  Numeric#clone
  0.07    14.66      0.01      118     0.08     0.08  Fixnum#-@
  0.00    14.66      0.00       10     0.00     0.00  Fixnum#*
  0.00    14.66      0.00       20     0.00     0.00  Kernel.open
  0.00    14.66      0.00       10     0.00     0.00  Module#method_added
  0.00    14.66      0.00        2     0.00     0.00  Module#append_features
  0.00    14.66      0.00        1     0.00 14650.00  Fixnum#times
  0.00    14.66      0.00       10     0.00     0.00  Comparable.>=
  0.00    14.66      0.00        4     0.00     0.00  Bignum#coerce
  0.00    14.66      0.00       20     0.00     0.00  IO#close
  0.00    14.66      0.00       96     0.00     0.00  Fixnum#<<
  0.00    14.66      0.00        1     0.00     0.00  Class#inherited
  0.00    14.66      0.00        3     0.00     0.00  Fixnum#+
  0.00    14.66      0.00       20     0.00     0.00  IO#read
  0.00    14.66      0.00        2     0.00     0.00  Module#include
  0.00    14.66      0.00        1     0.00 14660.00  #toplevel

% ruby  -r profile -e 'require "modexp.rb"' -e "10.times do a=128.random ;
a.gcd(128.random) ; end"

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 37.34     2.39      2.39       10   239.00   439.00  Crypto_math.gcd
 21.72     3.78      1.39       20    69.50    99.50  Crypto_math.random
 12.97     4.61      0.83     5875     0.14     0.18  Comparable.>
  9.53     5.22      0.61    12182     0.05     0.05  Numeric#clone
  4.53     5.51      0.29     5885     0.05     0.05  Bignum#%
  4.06     5.77      0.26     5885     0.04     0.04  Bignum#<=>
  2.97     5.96      0.19     2493     0.08     0.08  Bignum#|
  2.50     6.12      0.16     2473     0.06     0.06  Bignum#<<
  1.87     6.24      0.12     2560     0.05     0.05  Fixnum#-
  1.25     6.32      0.08     2560     0.03     0.03  String#[]
  0.47     6.35      0.03     2786     0.01     0.01  Fixnum#>
  0.16     6.36      0.01        1    10.00  6390.00  Fixnum#times
  0.16     6.37      0.01       67     0.15     0.15  Fixnum#|
  0.16     6.38      0.01        1    10.00    10.00  Kernel.require
  0.16     6.39      0.01       87     0.11     0.11  Fixnum#<<
  0.16     6.40      0.01      186     0.05     0.05  Fixnum#%
  0.00     6.40      0.00        2     0.00     0.00  Module#append_features
  0.00     6.40      0.00       10     0.00     0.00  Module#method_added
  0.00     6.40      0.00       20     0.00     0.00  IO#close
  0.00     6.40      0.00       10     0.00     1.00  Comparable.>=
  0.00     6.40      0.00       20     0.00     0.00  Kernel.open
  0.00     6.40      0.00        1     0.00     0.00  Class#inherited
  0.00     6.40      0.00       20     0.00     0.00  IO#read
  0.00     6.40      0.00        2     0.00     0.00  Module#include
  0.00     6.40      0.00        1     0.00  6400.00  #toplevel

As you can see, the gcd routine is very much faster than the gcdb
routine, by a large amount (as in, gcdb is only 2/3rds the speed).  I
did without -r profile and used Unix 'time' command and got same
result, gcdb only 2/3rds the speed of gcd for 128-byte (1024-bit)
Bignums. The problem appears to be the number of a[0]=0 type calls
Stein's algorithm, note the big # of calls to [] and to ==.

Right now, it appears to me that the only way to speed up things is to
write a 'even-ness' test in "C" that looks at the lower-order bit and
goes from there, without doing all the array computations and etc.
Otherwise 'gcd' will always be faster, because it does not have the
20,000 calls to [] and == that are boggind down gcdb with procedure
call overhead. A 'iseven?' call will halve the number of calls
immediately by eliminating the == part (since I can return a boolean
and use the boolean directly in computations). That will not however
make it faster. If you look, next up comes the swap overhead (the test
and swap part of "while t != 0" which Ruby turns into bignum
comparison of t > 0, the negating of bignums, and the right shifting
of bignums. The overhead of doing all these on 1024-bit numbers
appears to be heavier than the overhead of doing a simple % on
1024-bit numbers, and it appears that I will need to go to "C" if I
need to have anything faster than the plain old Euclidean GCD in
Ruby. (BTW, I sped up the Euclidean gcd even more by removing the
..clone calls from the inner loop, they were not needed since nothing
modified the values in place).

Eric Lee Green         Web: http://www.badtux.org 
  GnuPG public key at http://badtux.org/eric/eric.gpg
    Free Dmitry Sklyarov! [ http://www.eff.org ]

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE7a38j3DrrK1kMA04RAisbAJwIYrH/Y+41eY36+CPkYp3mQyhpZACfYNFb
K2/gihnWQPOtO12HrvVsstE=
=1J3h
-----END PGP SIGNATURE-----