From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD,
	FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,b2923d60cb81694b
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!postnews.google.com!e1g2000hsg.googlegroups.com!not-for-mail
From: "frikk" <frikker@gmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Unsigned Integer Restraint Errors
Date: 16 Mar 2007 06:38:44 -0700
Organization: http://groups.google.com
Message-ID: <1174052324.689881.20710@e1g2000hsg.googlegroups.com>
References: <1173712032.183064.264340@8g2000cwh.googlegroups.com>
   <e9in1ny6b3gb.16e7shcfhyja8$.dlg@40tude.net>
   <1173726806.656979.305660@8g2000cwh.googlegroups.com>
   <et4cma$o0v$1@jacob-sparre.dk>
   <BFoJh.14542$PF.8157@attbi_s21>
   <et57ho$bjm$1@jacob-sparre.dk>
   <1173787790.826099.287610@s48g2000cws.googlegroups.com>
   <1173797935.875023.7590@p10g2000cwp.googlegroups.com>
   <1173801854.505211.245650@64g2000cwx.googlegroups.com>
   <10l92gksnkfjl$.1rhbr6sokrtjy.dlg@40tude.net>
NNTP-Posting-Host: 12.129.98.129
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
X-Trace: posting.google.com 1174052326 7544 127.0.0.1 (16 Mar 2007 13:38:46
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Fri, 16 Mar 2007 13:38:46 +0000 (UTC)
In-Reply-To: <10l92gksnkfjl$.1rhbr6sokrtjy.dlg@40tude.net>
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1;
 InfoPath.1; .NET CLR 1.1.4322; .NET CLR 2.0.50727),gzip(gfe),gzip(gfe)
X-HTTP-Via: 1.1 TRY0PX01
Complaints-To: groups-abuse@google.com
Injection-Info: e1g2000hsg.googlegroups.com; posting-host=12.129.98.129;
   posting-account=192wHg0AAAAzciSzoZsEBI9bw5pVCopO
Xref: g2news1.google.com comp.lang.ada:14534
Date: 2007-03-16T06:38:44-07:00
List-Id: <comp.lang.ada>

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