sqrt algorithm

[Torbjörn Granlund]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

  Great code!
  
Thanks.

  May I suggest to save a variable?
  
I know you like 'while', but I like 'for'...  When we move to c99 I'll
stick the variable decl into the 'for' in order to bind the variable
to the loop.

I agree with saving variables which are simultaneously alive.  In this
code, n and i are not simultaneously alive.

The variant below makes an important change: It makes one quantity less
live across calls.  The result is that gcc spills no variable for
x86-64, using 13 instructions for the loop.

void
mpn_mullo_basecase (mp_ptr rp, mp_srcptr up, mp_srcptr vp, mp_size_t n)
{
  mp_limb_t h;

  h = up[0] * vp[n - 1];

  if (n != 1)
    {
      mp_size_t i;
      mp_limb_t v0;

      v0 = *vp++;
      h += up[n - 1] * v0 + mpn_mul_1 (rp, up, n - 1, v0);
      rp++;

      for (i = n - 2; i > 0; i--)
	{
	  v0 = *vp++;
	  h += up[i] * v0 + mpn_addmul_1 (rp, up, i, v0);
	  rp++;
	}
    }

  rp[0] = h;
}

-- 
Torbjörn
Please encrypt, key id 0xC8601622