Re: Unsigned Integer Restraint Errors

["frikk" <frikker@gmail.com>]

On Mar 13, 1:23 pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> 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. Kazakovhttp://www.dmitry-kazakov.de

That's very cool. I've had the opportunity to work with algorithms
like that.  You guys have definitely made me think about what it takes
to break down an algorithm into more simple parts.

Thanks!
Blaine