core-matrix 2023-08-17 | Slack Archive

pez10:08:00

Hi! Math and matrix noob here. I’m trying out core.matrix for the first time using day 6 of adventofcode 2021, for which I was pointed to a solution in Matlab. My non-matrix solution was O(n), and the Matlab implementation was O(log(n)). With ChatGPT’s help, I’ve managed to implement it and reached O(log(n)) too. Loving the learnings. However, the problem as such involves counting large numbers of fish, so the core.matrix solution quickly just results in nonsense, because of doubles. I take this as being what it is, but wanted to check if I am missing something. I also looked for a way to raise a matrix to an power (exponentiation) but didn’t find it, so rolled my own. Did I not look closely enough? Will post some code in a reply to this thread, to not spoil the problem for anyone who hasn’t done this fun exercise yet.

pez10:08:18

Here’s my solution. It is insanely much faster than my O(n) one. For the 256 generation case (the actual AOC problem) it is 10 µs, compared to 100 µs, and naturally it gets to be much bigger wins as I try with more generations. This is all ignoring that I get correct answers with my O(n) solutions, and incorrect results with this one. 😄

Ben Sless10:08:33

Your implementation is correct

🙏 2

pez10:08:01

Thanks! Do you know of any other matrix library, using integers? For the 256 case it almost works. But only if I squint. 😃

(int (apply + (nth-school input 256)))
; Execution error (IllegalArgumentException) at pez.aoc-2021.day-6-matrix/eval24843 (REPL:3126).
; Value out of range for int: 1592778185024

(That’s the correct answer for my input.)

pez10:08:51

Or maybe it is big decimals that are needed? I really am a noob with matrix math.

Ben Sless10:08:10

Full stack trace?

Ben Sless10:08:47

Ah, nvm, its not a matrix math problem, just a very big number, out of range for int

Ben Sless10:08:04

Why call int on the result and not long?

pez10:08:31

Just pure stupidness. With long I don’t get the error.

❤️ 2

Ben Sless10:08:03

Probably useless but you can type hint n as long and remove the int cast

pez10:08:52

The main issue remains, though:

(bigint (apply + (nth-school [3,4,3,1,2] 1000))) => 379589061144698200000000000000000000000N

pez11:08:18

I don’t know where to type hint n, actually. core.matrix will coerce to doubles anyway, right?

Ben Sless11:08:28

What's the issue?

pez11:08:16

The precision of doubles isn’t enough => I get the wrong answer.

Ben Sless11:08:39

Ahhh I understand

pez11:08:20

I obfuscated the question, obviously. 😃

Ben Sless11:08:21

Why are you calling the array function?

Ben Sless11:08:33

Which implementation is chosen by core matrix?

Ben Sless11:08:17

https://github.com/mikera/core.matrix/wiki/The-Array-Abstraction

pez11:08:30

I’m calling the array function because I wanted to use the :vectorsz implementation and not the regular persistent vectors. I’m not sure it matters all that much now, but I created a much stupid exponentiation function at first and then it mattered tons.

mars0i04:09:39

:vectorz only uses doubles, as I recall. Maybe you already know this, but if you use core.matrix with (mx/set-current-implementation :persistent-vector) or`(mx/set-current-implementation :ndarray)` or then you can use Longs, BigInt s, clojure.lang.Ratios, or whatever you want for the precision you need. These are native clojure matrix implementations, so you can choose whatever clojure datatype you want, and as long as your operations preserve the types. (I think you know that :persistent-vector matrices are just clojure vectors of vectors, so :ndarray should be more efficient.) (At one point I wrote something where I needed precise ratios with no rounding or float slop, and using :ndarray and :persistent-vector is what made it possible. A lot of people like Neanderthal--with good reason--but it won't do this.)

🙏 1

pez07:09:27

Thanks! I think “as long as your operations preserve the types” is key for me. I’m using mmul on two matrices in my matrix-power function. Trying with both :ndarray and :persistent-vector I get:

(m/mmul 1N 1N)         => 1N
  (m/mmul [[1N]] 1N)     => [[1N]]
  (m/mmul [[1N]] [[1N]]) => [[1.0]]
  (-> (m/mmul [[1N]] [[1N]]) ffirst type) => java.lang.Double
  
  (m/mmul 1/2 1/1)         => 1/2
  (m/mmul [[1/2]] 1/1)     => [[1/2]]
  (m/mmul [[1/2]] [[1/1]]) => [[0.5]]

  (m/mmul [[1N]] 1M)       => [[1M]]
  (m/mmul [[1N]] [[1M]])   => [[1.0]]

pez09:09:15

Now reread the article that @UK0810AQ2 provided above. 😃

(m/mmul (object-array [[1/2]]) (object-array [[1/1]])) => [[1/2]]

And using a java array for my school of lantern fish I now get:

(do
    (m/set-current-implementation :ndarray)
    (time
     (println (bigint (apply + (nth-school [3,4,3,1,2] 1000)))))
    (criterium/quick-bench
     (apply + (nth-school [3,4,3,1,2] 1000))))
  =>
379589061144698259131825683795505058481N
"Elapsed time: 1.855416 msecs"
Evaluation count : 486 in 6 samples of 81 calls.
             Execution time mean : 1.231394 ms
    Execution time std-deviation : 11.752512 µs
   Execution time lower quantile : 1.217677 ms ( 2.5%)
   Execution time upper quantile : 1.244845 ms (97.5%)
                   Overhead used : 1.907725 ns
nil
clj꞉pez.aoc-2021.day-6-matrix꞉>

Which is 3X slower than my non-matrix wielding implementation. But starts to get much faster with more generations. So at 1,000,000 generations the matrix implementation is 4-5X faster.

2023-08-17

Channels