Mirror of forum.nim-lang.org

4072 :: Automatic Algorithms Optimization via Fast Matrix Exponentiation

• peheje (orginal) [2018-07-23T20:14:25+02:00] view original

  I recently stumpled upon this thread on HN: https://kukuruku.co/post/automatic-algorithms-optimization-via-fast-matrix-exponentiation/

  Impressive. Can the same thing be achieved in Nim? I tried to use the library bignum: https://github.com/FedeOmoto/bignum

  To do:

  
  import bignum
  proc fib(n: Rat): Rat =
      var
          i = newRat(0)
          t = newRat(0)
          a = newRat(0)
          b = newRat(1)
      while i < n:
          t = a + b
          a = b
          b = t
          i += 1
      return a
  
  proc main() =
      let limit = newRat(10 ^ 7)
      # let limit = newRat(10) # 55
      echo fib(limit)
  
  main()
  Run

  Built with

  -d:release c

  also tried

  --cc:clang -d:release --clang.options.speed=-Ofast -flto -fno-strict-aliasing -ffast-math c

  Seems to spin for long time.

---

• mratsim (orginal) [2018-07-24T15:42:37+02:00] view original

  Cpmoptimize works at the bytecode level, it takes Python bytecode and then dynamically recompile it in an optimized version. This is basically a JIT.

  • There is no Nim bytecode, everything is statically compiled, so you can't do the same
  • However you can create a macro / term-rewriting template that would catch certain slow expressions and change them to an optimized version.
  • Or if you're feeling adventurous, you can implement a x86_64 JIT to rewrite at the CPU opcode level.

  My advice is to use libraries with efficient implementations from the start.

  Efficient implementations for numerical algorithms usually comes from linear algebra or number theory and you can't automate that, so either the library implements it efficiently, or there is something like cpmoptimize that detects the pattern and rewrite it for efficiency.

  Side-note, in the past I was having fun trying to compute Fibonacci with signal processing techniques ("Direct Form II transpose filter"). It's super fast.

  
  % Matlab code
  
  % Project Euler 2
  % sum of even fibonacci number <4 000 000
  % transform parenthesis and curly brace into functions (matlab use
  % parenthesis for both input and indexing :/
  paren = @(x, varargin) x(varargin{:});
  curly = @(x, varargin) x{varargin{:}};
  
  iseven = @(x) ~logical(bitget(x,1)); %returns TRUE if number is even
  % keep only even number in matrix A: A(iseven(A))
  
  %Y = FILTER(B,A,X) filters the data in vector X with the
  %    filter described by vectors A and B to create the filtered
  %    data Y.  The filter is a "Direct Form II Transposed"
  %    implementation of the standard difference equation:
  %
  %    a(1)*y(n) = b(1)*x(n) + b(2)*x(n-1) + ... + b(nb+1)*x(n-nb)
  %                          - a(2)*y(n-1) - ... - a(na+1)*y(n-na)
  fib = @(n)filter(1,[1,-1,-1],[1,zeros(1,n-1)]);
  n=1;
  while paren(fib(n),n)<4e6
      n=n+1;
  end;
  A=fib(n-1); sum(A(iseven(A)))
  Run

---

• peheje (orginal) [2018-07-24T20:06:32+02:00] view original

  Thanks for your answer. I'm not smart enough to begin implementing stuff like that.

  The guy DannyBee on the hackernews forum claims that GCC easily could do this.

  https://news.ycombinator.com/item?id=17592359

  Just thought it was interesting.

  Are you referring to some c/c++ lib that does this in an optimized way? And then calling it from nim?

---

• mratsim (orginal) [2018-07-26T15:59:07+02:00] view original

  There is no need to do this if the library use efficient routines from the start.

  In Nim the easiest and most portable would be to use term-rewriting macros you wouldn't need to rely on a compiler or JIT it would also work for the JS backend.

---