UP | HOME

A Zillion Ways to Compute the Inner Product of two Vectors in COMMON LISP

The most common way to compute the inner product s of two vectors a and b of size n is this:

s := 0
for i := 1 to n do
     s := s + a[i] * b[i]

1 Recursive

trivial, eats your stack

(defun IP (a b) 
    (if (null a) 
        0 
        (+ (* (car a) (car b)) 
              (IP (cdr a) (cdr b)))))

This is the genuine lisp way of of computation. But it is not properly tail-recursive. Though it generates a stackoverflow on large vectors.

2 Tail Recursive

less trivial, fast, does not eat your stack

(defun IP (a b &optional (acc 0)) 
    (if (or a b)
        (IP (cdr a) (cdr b) (+ acc (* (car a) (car b)))) 
        acc))

3 Applicative

less trivial, concise, quite fast

(defun IP(a b) (reduce #'+ (mapcar #'* a b)))

Most lispers would do it this way. It is concise and clean. mapcar generates a list of products with the operator * and reduce folds this list with the operator +.

4 Iterative

trivial Although not considered to be koscher Lisp by everyone, this one is most simple to grasp for people coming from imperative Languages.

(defun IP (a b) 
    (loop for p in a as q in b 
          sum (* p q)))

5 Fortranesk

trivial, ugly, lightning fast

(defun IP (a b) 
   (prog ((c 0))

    sum-up 
       (setq  c (+ c (* (car a) (car b))) )
       (setq a (cdr a)) 
       (setq b (cdr b)) 
       (when (and a b) 
             (go sum-up))
       (return c)))

Long and verbose with a spoiled "GOTO".

6 Metalinguistic

not trivial

Here we generate an expression like (+ (* 1 4) (* 2 5) (* 3 6)) and pass it to the EVAL-Function.

(defun IP (a b)
  (eval (cons '+ (mapcar (lambda (p q) (list '* p q)) 
                         a b))))

7 Probably Wrong :-P

89

8 Function-Level

very sophisticated, extravagant, not too fast

This is derived from the Paper "Can Programming be Liberated from the von Neumann Style?" of John Backus 1978. Please refer to this document to fully understand this piece of Code. In essence, the function IP is constructed by function composition of some 1-parameter-functions, that are generated by function calls.

insert and alpha2 are taken from backus' papers. The first one is a function that generates closures, that act like reduce and the second generates closures that act like mapcar-.

transpose simply computes the transposed matrix of a matrix, given in list representation, e.g. ((1 2) (a b)) --> ((1 a) (2 b))

(use-package :alexandria) ;  We need CURRY and COMPOSE

(defun transpose (x) (apply #'mapcar (cons 'list x)))
(defun insert (op) (curry #'apply op))
(defun alpha2 (op) (lambda (l) (mapcar (insert op) l)))
(defparameter IP (compose (insert #'+) 
                          (alpha2 #'*) 
                          #'transpose))

(print (funcall IP '((1 2 3) (4 5 6))))

9 Via Composed Closures

sophisticated and complete bullshit

(defun IP (a b) 
  (funcall 
   (apply #'compose 
          (mapcar (lambda (a b) 
                    (lambda (s) 
                      (+ s (* a b)))) 
                  a b )) 
   0))

This generates a list of closures, each computing one product and adding some parameter eaten by them. After that the 1-parameter closures, that take the sum s computed so far are "composed" together into a single function that is finally called with the value 0 for s. This function finally performs the hole computation.

10 What Else?

This is my collection so far. Are there more ways to implement the inner product? Sure, there are. I'd be glad to hear from you of other possibilies. Pass me a mail or use the comment facility.

I would like to grow this collection. Even bizarre solutions are welcome. Thanks in advance!

Author: Patrick Krusenotto (patrick.krusenotto@googlemail.com)

Date: 2014-10-08 22:57:27 CEST

Generated by Org version 7.8.11 with Emacs version 24

comments powered by Disqus