[prev in list] [next in list] [prev in thread] [next in thread]
List: gmp-devel
Subject: Faster sqrt/root
From: tg () gmplib ! org (Torbjorn Granlund)
Date: 2011-08-03 19:48:12
Message-ID: 86y5zaqnsz.fsf () shell ! gmplib ! org
[Download RAW message or body]
In a typical sqrt(A) Newton iteration, ere is a division A/x_k where x_k
is the kth approximation. If A is 2n bits, x_k is about n bits.
Division of a 2n-bit number by an n-bit number is typically about 2x
slower than a n-bit by n-bit multiplication.
Perhaps one could save the quotient from A/x_{k-1}, call it q_{k-1}, and
compute A/x_k by first computing A-(x_k * q_{k-1}), then develop further
quotient bits starting with this partial remainder?
If I am not mistaken, this will save about half the division time,
resulting in perhaps a 25% speedup.
--
Torbj?rn
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic