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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham 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!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!news-in.ntli.net!newsrout1-win.ntli.net!ntli.net!news.highwinds-media.com!newspeer1-win.ntli.net!newsfe4-win.ntli.net.POSTED!53ab2750!not-for-mail From: "Dr. Adrian Wrigley" Subject: Re: GNAT compiler switches and optimization User-Agent: Pan/0.14.2 (This is not a psychotic episode. It's a cleansing moment of clarity.) Message-ID: 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> <453A532F.2070709@obry.net> <9kfq04-sgm.ln1@newserver.thecreems.com> <5vgs04-64f.ln1@newserver.thecreems.com> <453bc74e$0$19614$426a74cc@news.free.fr> <4jit04-0gq.ln1@newserver.thecreems.com> <453d1d36$0$25551$bf4948fe@news.tele2.nl> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Date: Tue, 24 Oct 2006 09:52:51 GMT NNTP-Posting-Host: 82.10.238.153 X-Trace: newsfe4-win.ntli.net 1161683571 82.10.238.153 (Tue, 24 Oct 2006 10:52:51 BST) NNTP-Posting-Date: Tue, 24 Oct 2006 10:52:51 BST Organization: NTL Xref: g2news2.google.com comp.lang.ada:7179 Date: 2006-10-24T09:52:51+00:00 List-Id: On Mon, 23 Oct 2006 21:52:59 +0200, Wiljan Derks wrote: >> Jeffrey R. Carter wrote: >> I looked at the gcc FORTRAN matmul. Unless there some additional trickery >> going on behind the scenes, it is not anything magical. It looks like a >> matmul implemented in C with manual array subscripting logic (i.e. uses a >> single dimensional array overlay).. > When going for a faster algorithm this might be usefull information. > Notice that this matmul uses an O(n^3) algorithm and it is possible to do > this faster. > I am not sure, but maybe O(n^2 log(n)) is reachable, which is much faster. > It is easy to see that from the loops that the basic multiplications are > done n times for the same pairs of numbers. 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? > In a similar way, the same additions are done multiple times. > That means that there is real potential to improve things. Aren't they only the same additions if the same products are summed? I may be being particularly stupid today, but if the redundancy is obvious from the loops, can you help me see where! Thanks. -- Adrian