Re: Anomaly in mpn_sqrtrem and mpn_rottrem

2015-06-12 Thread Torbjörn Granlund 
ni...@lysator.liu.se (Niels Möller) writes:

  Hmm. Or maybe this is stupid. I could stop insisting on using a full
  size inverse (so that A / x or E / x can be computed as a *single*
  mulhi), and instead work with a half-size inverse, so that the quotient
  is computed in two steps. Then inverse computation using a plain
  Newton-step per iteration should work fine.
  
We indeed do that already when performing division for its own sake;
compute an inverse which is not longer than half the quotient size.

We might want to look into the plain division-free sqrt(A) = A*sqrt(1/A)
approach before implementing a tricky division sqrt(A).


-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Anomaly in mpn_sqrtrem and mpn_rottrem

2015-06-12 Thread bodrato 
Ciao,

Il Ven, 12 Giugno 2015 9:04 am, Torbjörn Granlund ha scritto:
 We might want to look into the plain division-free sqrt(A) = A*sqrt(1/A)
 approach before implementing a tricky division sqrt(A).

We can try improving the current implementation, before implementing any
other algorithm :-)

I wrote a simple patch (it touches very few lines) that allows skipping
the final squaring when mpn_sqrtrem is called with a NULL argument and the
approximation computed so far can not change.
It exploits the spurious half-a-limb that current code adds to the result
when the size is odd, i.e. it changes the timings only for odd sizes.

Before the patch:

$ tune/speed -rp1 -s21-110 -f15 mpn_sqrt mpn_root.2
mpn_rootrem.2 mpn_sqrtrem
overhead 0.2 secs, precision 1 units of 2.86e-10 secs, CPU
freq 3500.08 MHz
 mpn_sqrtmpn_root.2 mpn_rootrem.2   mpn_sqrtrem
210.013801.61551.5569   #0.9996
315  #0.153741.12221.54261.1521
4725  0.000918521   #0.90001.24581.0004
70875 0.029574741   #0.96121.21921.0007
10631250.741147157   #0.97181.21470.

Sometimes mpn_root.2 is faster than the other functios in a wide range

With the patch applied:
$ tune/speed.nsqrt -rp1 -s21-110 -f15 mpn_sqrt mpn_root.2
mpn_rootrem.2 mpn_sqrtrem
overhead 0.2 secs, precision 1 units of 2.86e-10 secs, CPU
freq 3500.08 MHz
 mpn_sqrtmpn_root.2 mpn_rootrem.2   mpn_sqrtrem
21   #0.013391.64961.60891.0244
315  #0.129241.33181.84321.3701
4725 #0.0007996071.03491.43121.1495
70875#0.0263216531.08041.36981.1253
1063125  #0.6563897051.09821.37361.1296

mpn_rot.2 is the faster

-- 
http://bodrato.it/

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: Anomaly in mpn_sqrtrem and mpn_rottrem

2015-06-12 Thread bodrato 
Il Sab, 13 Giugno 2015 12:27 am, bodr...@mail.dm.unipi.it ha scritto:

 I wrote a simple patch (it touches very few lines) that allows
skippingthe final
I forgot the attachment...

-- 
http://bodrato.it/

gmp.diff
Description: plain/text
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel