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.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM,
	FROM_WORDY autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,7767a311e01e1cd
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news2.google.com!news3.google.com!news.glorb.com!news2.euro.net!newsfeed.freenet.de!border2.nntp.ams.giganews.com!nntp.giganews.com!feeder2.cambrium.nl!feeder3.cambrium.nl!feed.tweaknews.nl!not-for-mail
From: "Wiljan Derks" <Wiljan.Derks@zonnet.nl>
Newsgroups: comp.lang.ada
References: <1161341264.471057.252750@h48g2000cwc.googlegroups.com>
 <9Qb_g.111857$aJ.65708@attbi_s21> <434o04-7g7.ln1@newserver.thecreems.com>
 <4539ce34$1_2@news.bluewin.ch> <nrup04-5hj.ln1@newserver.thecreems.com>
 <453A532F.2070709@obry.net> <9kfq04-sgm.ln1@newserver.thecreems.com>
 <sj3r04-rlv.ln1@newserver.thecreems.com>
 <5vgs04-64f.ln1@newserver.thecreems.com>
 <453bc74e$0$19614$426a74cc@news.free.fr>
 <4jit04-0gq.ln1@newserver.thecreems.com>
 <jcot04-l2u.ln1@newserver.thecreems.com> <Ld__g.206207$FQ1.45478@attbi_s71>
 <c6nu04-m31.ln1@newserver.thecreems.com>
 <453d1d36$0$25551$bf4948fe@news.tele2.nl>
 <pan.2006.10.24.09.54.07.340442@linuxchip.demon.co.uk.uk.uk>
Subject: Re: GNAT compiler switches and optimization
Date: Tue, 24 Oct 2006 21:21:13 +0200
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2900.2869
X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2900.2869
X-RFC2646: Format=Flowed; Original
Message-ID: <453e675e$0$30736$bf4948fe@news.tele2.nl>
Organization: Tele2
X-Trace: 
 DXC=`kg1_HQ_^V_G>D9`j;4j^X6`Y6aWje^YZZP\hYYmiCN]BbQ>\>HV]ZZG6KFLW8egdZ
Xref: g2news2.google.com comp.lang.ada:7187
Date: 2006-10-24T21:21:13+02:00
List-Id: <comp.lang.ada>


"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message 
news:pan.2006.10.24.09.54.07.340442@linuxchip.demon.co.uk.uk.uk...
> I know you're quite correct that there is a faster algorithm for
> large n.  But looking at the loops, I don't see where the same
> number pairs are multiplied at different points in the calculation.
> Doesn't A(1,1)*B(1,1) only appear in C(1,1)?  Where else?
>
> Aren't they only the same additions if the same products are summed?
>
Sorry, I was to fast writing this remark.
Since I was wrong, I checked my old school papers and found how to perfrom a 
faster matrix multiplication.
It is called the Strassen algorithm.
For more details see: http://en.wikipedia.org/wiki/Strassen_algorithm
It still looks to me, there may be considerable savings since this algortihm 
is O(n^2.8) instead of O(n^3).
Wikipedia also mention the drawback: numeric instability!
So the subtraction and addition tricks probably lead to less accurate 
results in certain cases.