Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: "Nuno Lopes" Newsgroups: comp.compilers Subject: Re: Automatic algorithm optimisation via fast matrix exponentiation Date: Sun, 11 Jan 2015 19:22:03 -0000 Organization: Compilers Central Lines: 20 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-01-011@comp.compilers> References: <15-01-010@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 8bit X-Trace: miucha.iecc.com 1421030134 36760 2001:470:1f07:1126:0:676f:7373:6970 (12 Jan 2015 02:35:34 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Mon, 12 Jan 2015 02:35:34 +0000 (UTC) Keywords: optimize Posted-Date: 11 Jan 2015 21:35:34 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1468 > Lovely article: > > http://kukuruku.co/hub/algorithms/automatic-algorithms-optimization-via-fast-matrix-exponentiation > > Do any compilers do this kind of thing? Partially, yes. For example, LLVM has a quadratic recurrence solver (named SCEV -- scalar evolution). For this purpose, matrix exponentiation is pretty much equivalent to recurrence solving. So, if LLVM manages to rewrite an induction variable as a recurrence, and if it manages to compute its closed-form, then LLVM may replace a loop with straight-line code. I believe GCC and MSVC can do similar things, since it's a somehow required piece of technology for automatic vectorization, which all compilers can do to some extent these days.. Nuno