Re: Unsigned Integer Restraint Errors

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On 13 Mar 2007 09:04:14 -0700, Adam Beneschan wrote:

> on the theory that using Sqrt is just a waste of cycles when you can
> just use integer arithmetic.  But I've been programming for way too
> long---long enough that I remember what a Hollerith card is

... and what was the Hollerith format of strings? (:-))

>---and I'm
> sure that doing a square-root doesn't take nearly as long as it used
> to, so there are probably some reasonable values of N for which
> computing the square-root first makes things more efficient than the
> repeated integer multiplications.  I don't know.  Use Sqrt if you want
> to.

(for very large number like in infinite arithmetic it could become an
issue)

BTW, the arithmetic complexity can be further "reduced" by removing
multiplication and computing k**2 using binomial decomposition
(k+1)*(k+1)=k*k+2*k+1. So it could be:

quadratic := 1; -- k*k, k=1
linear := 2; -- 2*k+1, k=1

loop
   linear := linear + 2; -- 2*k+1
   quadratic := quadratic + linear; -- k*k
   exit when k>=n;
   ...
end loop;

Whether this really would be any faster than multiplication or square root
computed once, God knows...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de