Matrix multiplication: Difference between revisions

This short version works on lists of lists length less than 253 rows and less than 253 columns.

<lang scheme>; short version based on 'apply'

This long version works on lists of lists with any matrix dimensions.

<lang scheme>; long version based on recursive cycles

(define (matrix-multiply A B)

(define m (length A))

(define n (length (car A)))

(assert (eq? (length B) n) ===> #true)

(define q (length (car B)))

(define (at m x y)

(lref (lref m x) y))

(let mloop ((i (- m 1)) (rows #null))

(if (< i 0)

rows

(mloop

(- i 1)

(cons

(let rloop ((j (- q 1)) (r #null))

(if (< j 0)

r

(rloop

(- j 1)

(cons

(let loop ((k 0) (c 0))

(if (eq? k n)

c

(loop (+ k 1) (+ c (* (at A i k) (at B k j))))))

r))))

rows)))))

</lang>

Testing large matrices:

<lang scheme>; [372x17] * [17x372]

(define M 372)

(define N 17)

; [0 1 2 ... 371]

; [1 2 3 ... 372]

; [2 3 4 ... 373]

; ...

; [16 17 ... 387]

(define A (map (lambda (i)

(iota M i))

(iota N)))

; [0 1 2 ... 16]

; [1 2 3 ... 17]

; [2 3 4 ... 18]

; ...

; [371 372 ... 387]

(define B (map (lambda (i)

(iota N i))

(iota M)))

(for-each print (matrix-multiply A B))

</lang>

{{Out}}

<pre>

(17090486 17159492 17228498 17297504 17366510 17435516 17504522 17573528 17642534 17711540 17780546 17849552 17918558 17987564 18056570 18125576 18194582)

(17159492 17228870 17298248 17367626 17437004 17506382 17575760 17645138 17714516 17783894 17853272 17922650 17992028 18061406 18130784 18200162 18269540)

(17228498 17298248 17367998 17437748 17507498 17577248 17646998 17716748 17786498 17856248 17925998 17995748 18065498 18135248 18204998 18274748 18344498)

(17297504 17367626 17437748 17507870 17577992 17648114 17718236 17788358 17858480 17928602 17998724 18068846 18138968 18209090 18279212 18349334 18419456)

(17366510 17437004 17507498 17577992 17648486 17718980 17789474 17859968 17930462 18000956 18071450 18141944 18212438 18282932 18353426 18423920 18494414)

(17435516 17506382 17577248 17648114 17718980 17789846 17860712 17931578 18002444 18073310 18144176 18215042 18285908 18356774 18427640 18498506 18569372)

(17504522 17575760 17646998 17718236 17789474 17860712 17931950 18003188 18074426 18145664 18216902 18288140 18359378 18430616 18501854 18573092 18644330)

(17573528 17645138 17716748 17788358 17859968 17931578 18003188 18074798 18146408 18218018 18289628 18361238 18432848 18504458 18576068 18647678 18719288)

(17642534 17714516 17786498 17858480 17930462 18002444 18074426 18146408 18218390 18290372 18362354 18434336 18506318 18578300 18650282 18722264 18794246)

(17711540 17783894 17856248 17928602 18000956 18073310 18145664 18218018 18290372 18362726 18435080 18507434 18579788 18652142 18724496 18796850 18869204)

(17780546 17853272 17925998 17998724 18071450 18144176 18216902 18289628 18362354 18435080 18507806 18580532 18653258 18725984 18798710 18871436 18944162)

(17849552 17922650 17995748 18068846 18141944 18215042 18288140 18361238 18434336 18507434 18580532 18653630 18726728 18799826 18872924 18946022 19019120)

(17918558 17992028 18065498 18138968 18212438 18285908 18359378 18432848 18506318 18579788 18653258 18726728 18800198 18873668 18947138 19020608 19094078)

(17987564 18061406 18135248 18209090 18282932 18356774 18430616 18504458 18578300 18652142 18725984 18799826 18873668 18947510 19021352 19095194 19169036)

(18056570 18130784 18204998 18279212 18353426 18427640 18501854 18576068 18650282 18724496 18798710 18872924 18947138 19021352 19095566 19169780 19243994)

(18125576 18200162 18274748 18349334 18423920 18498506 18573092 18647678 18722264 18796850 18871436 18946022 19020608 19095194 19169780 19244366 19318952)

(18194582 18269540 18344498 18419456 18494414 18569372 18644330 18719288 18794246 18869204 18944162 19019120 19094078 19169036 19243994 19318952 19393910)

</pre>