[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gmp-devel
Subject:    =?iso-8859-1?q?Sch=F6nhage?='s algorithm for fast integer GCD
From:       tege () swox ! com (Torbjorn Granlund)
Date:       2003-07-06 9:50:49
Message-ID: 868yrct24m.fsf () king ! swox ! se
[Download RAW message or body]

nisse@lysator.liu.se (Niels Möller) writes:

  Kevin Ryde <user42@zip.com.au> writes:

  > > Here, hgcd_2 is the work horse for Lehmer steps,
  >
  > Is q=ah/bh the primary quotient step?  Bear in mind that "/" is pretty
  > woeful on a lot of chips.

  The important thing for the lehmer step is to compute the one-limb
  quotient of two two-limb numbers a and b, q = floor(a/b), a >= b.
  What's the fastest way of doing that? I know I could do some special
  casing for small quotients by subtracting a few times before trying a
  proper division, but I don't know of any obvious way to speed up the
  general case.

Perhaps the bitwise div2 function from mpn/generic/gcdext.c could
be used.  That function accepts a two-limb divisor, but
simplifying it to just handle a one-limb divisor should be
straightforward.

  Do you mean

  	if (! (limb & GMP_NUMB_HIGHBIT))
  	  {
  	    count_leading_zeros(shift, limb);
  	    ...

  ?

Please use "!= 0" for numerical data.

--
Torbjörn

[prev in list] [next in list] [prev in thread] [next in thread]