Automatic Algorithms Optimization via Fast Matrix Exponentiation

[peheje]

I recently stumpled upon this thread on HN: 
[https://kukuruku.co/post/automatic-algorithms-optimization-via-fast-matrix-exponentiation](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](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.