Find the Cross Product

20

3

The cross product of two three-dimensional vectors \$\vec a\$ and \$\vec b\$ is the unique vector \$\vec c\$ such that:

  • \$\vec c\$ is orthogonal to both \$\vec a\$ and \$\vec b\$

  • The magnitude of \$\vec c\$ is equal to the area of the parallelogram formed by \$\vec a\$ and \$\vec b\$

  • The directions of \$\vec a\$, \$\vec b\$, and \$\vec c\$, in that order, follow the right-hand rule.

There are a few equivalent formulas for cross product, but one is as follows:

$$\vec a\times\vec b=\det\begin{bmatrix}\vec i&\vec j&\vec k\\a_1&a_2&a_3\\b_1&b_2&b_3\end{bmatrix}$$

where \$\vec i\$, \$\vec j\$, and \$\vec k\$ are the unit vectors in the first, second, and third dimensions.

Challenge

Given two 3D vectors, write a full program or function to find their cross product. Builtins that specifically calculate the cross product are disallowed.

Input

Two arrays of three real numbers each. If your language doesn't have arrays, the numbers still must be grouped into threes. Both vectors will have magnitude \$<2^{16}\$. Note that the cross product is noncommutative (\$\vec a\times\vec b=-\bigl(\vec b\times\vec a\bigr)\$), so you should have a way to specify order.

Output

Their cross product, in a reasonable format, with each component accurate to four significant figures or \$10^{-4}\$, whichever is looser. Scientific notation is optional.

Test cases

[3, 1, 4], [1, 5, 9]
[-11, -23, 14]

[5, 0, -3], [-3, -2, -8]
[-6, 49, -10]

[0.95972, 0.25833, 0.22140],[0.93507, -0.80917, -0.99177]
[-0.077054, 1.158846, -1.018133]

[1024.28, -2316.39, 2567.14], [-2290.77, 1941.87, 712.09]
[-6.6345e+06, -6.6101e+06, -3.3173e+06]

This is , so the shortest solution in bytes wins.

Maltysen posted a similar challenge, but the response was poor and the question wasn't edited.

lirtosiast

Posted 2016-01-30T02:42:34.237

Reputation: 20 331

Can the input be taken as a 2D array? – Dennis – 2016-01-30T03:03:45.287

Yes, as long as 2 is the outer dimension. – lirtosiast – 2016-01-30T03:04:57.563

Answers

14

Jelly, 14 13 12 bytes

;"s€2U×¥/ḅ-U

Try it online!

How it works

;"s€2U×¥/ḅ-U Main link. Input: [a1, a2, a3], [b1, b2, b3]

;"           Concatenate each [x1, x2, x3] with itself.
             Yields [a1, a2, a3, a1, a2, a3], [b1, b2, b3, b1, b2, b3].
  s€2        Split each array into pairs.
             Yields [[a1, a2], [a3, a1], [a2, a3]], [[b1, b2], [b3, b1], [b2, b3]].
       ¥     Define a dyadic chain:
     U         Reverse the order of all arrays in the left argument.
      ×        Multiply both arguments, element by element.
        /    Reduce the 2D array of pairs by this chain.
             Reversing yields [a2, a1], [a1, a3], [a3, a2].
             Reducing yields [a2b1, a1b2], [a1b3, a3b1], [a3b2, a2b3].
         ḅ-  Convert each pair from base -1 to integer.
             This yields [a1b2 - a2b1, a3b1 - a1b3, a2b3 - a3b2]
           U Reverse the array.
             This yields [a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1] (cross product).

Non-competing version (10 bytes)

OK, this is embarrassing, but the array manipulation language Jelly did not have a built-in for array rotation until just now. With this new built-in, we can save two additional bytes.

ṙ-×
ç_ç@ṙ-

This uses the approach from @AlexA.'s J answer. Try it online!

How it works

ṙ-×     Helper link. Left input: x = [x1, x2, x3]. Right input: y = [y1, y2, y3].

ṙ-      Rotate x 1 unit to the right (actually, -1 units to the left).
        This yields [x3, x1, x2].
  ×     Multiply the result with y.
        This yields [x3y1, x1y2, x2y3].


ç_ç@ṙ-  Main link. Left input: a = [a1, a2, a3]. Right input: b = [b1, b2, b3].

ç       Call the helper link with arguments a and b.
        This yields [a3b1, a1b2, a2b3].
  ç@    Call the helper link with arguments b and a.
        This yields [b3a1, b1a2, b2a3].
_       Subtract the result to the right from the result to the left.
        This yields [a3b1 - a1b3, a1b2 - a2b1, a2b3 - a3b2].
    ṙ-  Rotate the result 1 unit to the right.
        This yields [a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1] (cross product).

Dennis

Posted 2016-01-30T02:42:34.237

Reputation: 196 637

Convert each pair from base -1? That's just evil. +1 – ETHproductions – 2016-01-31T03:43:18.390

10

LISP, 128 122 bytes

Hi! This is my code:

(defmacro D(x y)`(list(*(cadr,x)(caddr,y))(*(caddr,x)(car,y))(*(car,x)(cadr,y))))(defun c(a b)(mapcar #'- (D a b)(D b a)))

I know that it isn't the shortest solution, but nobody has provided one in Lisp, until now :)

Copy and paste the following code here to try it!

(defmacro D(x y)`(list(*(cadr,x)(caddr,y))(*(caddr,x)(car,y))(*(car,x)(cadr,y))))(defun c(a b)(mapcar #'- (D a b)(D b a)))

(format T "Inputs: (3 1 4), (1 5 9)~%")
(format T "Result ~S~%~%" (c '(3 1 4) '(1 5 9)))

(format T "Inputs: (5 0 -3), (-3 -2 -8)~%")
(format T "Result ~S~%~%" (c '(5 0 -3) '(-3 -2 -8)))

(format T "Inputs: (0.95972 0.25833 0.22140), (0.93507 -0.80917 -0.99177)~%")
(format T "Result ~S~%" (c '(0.95972 0.25833 0.22140) '(0.93507 -0.80917 -0.99177)))

(format T "Inputs: (1024.28 -2316.39 2567.14), (-2290.77 1941.87 712.09)~%")
(format T "Result ~S~%" (c '(1024.28 -2316.39 2567.14) '(-2290.77 1941.87 712.09)))

PieCot

Posted 2016-01-30T02:42:34.237

Reputation: 1 039

Welcome to Programming Puzzles and Code Golf Stack Exchange. This is a great answer, +1. Well done for answering in a language that isn't going to win, but still golfing it down loads. Often [tag:code-golf] challenges are more about within languages than between them! – wizzwizz4 – 2016-01-30T13:29:45.270

9

J, 27 14 bytes

2|.v~-v=.*2&|.

This is a dyadic verb that accepts arrays on the left and right and returns their cross product.

Explanation:

         *2&|.     NB. Dyadic verb: Left input * twice-rotated right input
      v=.          NB. Locally assign to v
   v~-             NB. Commute arguments, negate left
2|.                NB. Left rotate twice

Example:

    f =: 2|.v~-v=.*2&|.
    3 1 4 f 1 5 9
_11 _23 14

Try it here

Saved 13 bytes thanks to randomra!

Alex A.

Posted 2016-01-30T02:42:34.237

Reputation: 23 761

@randomra That's awesome, thanks! I'm no J expert so I'm still figuring out how exactly it works but I have a general idea. – Alex A. – 2016-01-30T19:03:33.450

Some clarifications: *2&|. is a fork of two verbs: * and 2&|.. It multiplies the left input by a rotated by 2 right input. This fork is stored in v so when we write v~, it is equivalent to (*2&|.)~, where the ~ swaps the left and right input parameters for the parenthesized part. – randomra – 2016-01-30T19:53:19.133

@randomra Okay, that makes sense. Thanks again! – Alex A. – 2016-01-31T03:38:49.197

9

Dyalog APL, 12 bytes

2⌽p⍨-p←⊣×2⌽⊢

Based on @AlexA.'s J answer and (coincidentally) equivalent to @randomra's improvement in that answer's comment section.

Try it online on TryAPL.

How it works

2⌽p⍨-p←⊣×2⌽⊢  Dyadic function.
              Left argument: a = [a1, a2, a3]. Right argument: b = [b1, b2, b3].

         2⌽⊢  Rotate b 2 units to the left. Yields [b3, b1, b2].
       ⊣×     Multiply the result by a. Yields [a1b3, a2b1, a3b2].
     p←       Save the tacit function to the right (NOT the result) in p.
  p⍨          Apply p to b and a (reversed). Yields [b1a3, b2a1, b3a2].
    -         Subtract the right result (p) from the left one (p⍨).
              This yields [a3b1 - a1b3, a1b2 - a2b1, a2b3 - a3b2].
2⌽            Rotate the result 2 units to the left.
              This yields [a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1].

Dennis

Posted 2016-01-30T02:42:34.237

Reputation: 196 637

6

C, 156 154 150 148 144 bytes

#include <stdio.h>
main(){float v[6];int i=7,j,k;for(;--i;)scanf("%f",v+6-i);for(i=1;i<4;)j=i%3,k=++i%3,printf("%f ",v[j]*v[k+3]-v[k]*v[j+3]);}

Not going to be winning any prizes for length, but thought I'd have a go anyway.

  • Input is a newline- or space-delimited list of components (i.e. a1 a2 a3 b1 b2 b3), output is space-delimited (i.e. c1 c2 c3).
  • Cyclically permutes the indices of the two input vectors to calculate the product - takes fewer characters than writing out the determinants!

Demo

Ungolfed:

#include <cstdio>
int main()
{
    float v[6];
    int i = 7, j, k;
    for (; --i; ) scanf("%f", v + 6 - 1);
    for (i = 1; i < 4; )
        j = i % 3,
        k = ++i % 3,
        printf("%f ", v[j] * v[k + 3] - v[k] * v[j + 3]);
}

calvinsykes

Posted 2016-01-30T02:42:34.237

Reputation: 61

1Welcome to Programming Puzzles and Code Golf Stack Exchange. This is a great answer; well done for answering in a language that won't beat the golfing languages. +1. – wizzwizz4 – 2016-01-30T10:39:35.323

2Your first for doesn't need {} – removed – 2016-01-30T11:58:04.187

cheers, updated. – calvinsykes – 2016-01-30T15:50:15.147

1You can replace &v[6-i] with v+6-i. Also, you can replace semicolon after j=i%3 and k=(i+1)%3 with commas, which makes everything after the for a single statement so you can omit the {}. Finally, if you initialise i to 1 for the second for loop, you can move the increment into k=++i%3 saving a couple of brackets. If you're not worried about warnings and use the right version of C, you can skip the include as well. – Alchymist – 2016-02-01T16:07:14.917

awesome, cheers! My compiler won't accept the omission of the header, so I've stuck with a version I'm able to build. – calvinsykes – 2016-02-01T21:20:53.983

115 bytes – ceilingcat – 2018-10-04T05:57:08.323

4

Haskell, 41 bytes

x(a,b,c)(d,e,f)=(b*f-c*e,c*d-a*f,a*e-b*d)

A straightforward solution.

xnor

Posted 2016-01-30T02:42:34.237

Reputation: 115 687

4

Bash + coreutils, 51

eval set {$1}*{$2}
bc<<<"scale=4;$6-$8;$7-$3;$2-$4"
  • Line 1 constructs a brace expansion that gives the cartesian product of the two vectors and sets them into the positional parameters.
  • Line 2 subtracts the appropriate terms; bc does the arithmetic evaluation to the required precision.

Input is as two comma-separated lists on the command-line. Output as newline-separated lines:

$ ./crossprod.sh 0.95972,0.25833,0.22140 0.93507,-0.80917,-0.99177
-.07705
1.15884
-1.01812
$

Digital Trauma

Posted 2016-01-30T02:42:34.237

Reputation: 64 644

4

MATL, 17 bytes

!*[6,7,2;8,3,4])d

First input is a, second is b.

Try it online!

Explanation

!              % input b as a row array and transpose into a column array
*              % input a as a row array. Compute 3x3 matrix of pairwise products
[6,7,2;8,3,4]  % 2x3 matrix that picks elements from the former in column-major order
)              % apply index
d              % difference within each column

Luis Mendo

Posted 2016-01-30T02:42:34.237

Reputation: 87 464

4

Pyth, 16 bytes

-VF*VM.<VLQ_BMS2

Try it online: Demonstration

Explanation:

-VF*VM.<VLQ_BMS2   Q = input, pair of vectors [u, v]
              S2   creates the list [1, 2]
           _BM     transforms it to [[1, -1], [2, -2]]
      .<VLQ        rotate of the input vectors accordingly to the left:
                   [[u by 1, v by -1], [u by 2, v by -2]]
   *VM             vectorized multiplication for each of the vector-pairs
-VF                vectorized subtraction of the resulting two vectors

Jakube

Posted 2016-01-30T02:42:34.237

Reputation: 21 462

3

K5, 44 40 37 32 bytes

Wrote this one quite a while ago and dusted it off again recently.

{{x[y]-x[|y]}[*/x@']'3 3\'5 6 1}

In action:

 cross: {{x[y]-x[|y]}[*/x@']'3 3\'5 6 1};

 cross (3 1 4;1 5 9)
-11 -23 14
 cross (0.95972 0.25833 0.22140;0.93507 -0.80917 -0.99177)
-7.705371e-2 1.158846 -1.018133

Edit 1:

Saved 4 bytes by taking input as a list of lists instead of two separate arguments:

old: {m:{*/x@'y}(x;y);{m[x]-m[|x]}'(1 2;2 0;0 1)}
new: {m:{*/x@'y}x    ;{m[x]-m[|x]}'(1 2;2 0;0 1)}

Edit 2:

Saved 3 bytes by computing a lookup table with base-decode:

old: {m:{*/x@'y}x;{m[x]-m[|x]}'(1 2;2 0;0 1)}
new: {m:{*/x@'y}x;{m[x]-m[|x]}'3 3\'5 6 1}

Edit 3:

Save 5 bytes by rearranging application to permit using a tacit definition instead of a local lambda. Unfortunately, this solution no longer works in oK, and requires the official k5 interpreter. Gonna have to take my word for this one until I fix the bug in oK:

old: {m:{*/x@'y}x;{m[x]-m[|x]}'3 3\'5 6 1}
new: {{x[y]-x[|y]}[*/x@']     '3 3\'5 6 1}

JohnE

Posted 2016-01-30T02:42:34.237

Reputation: 4 632

3

Ruby, 49 bytes

->u,v{(0..2).map{|a|u[a-2]*v[a-1]-u[a-1]*v[a-2]}}

Try it online!

Returning after 2 years, I shaved off 12 bytes by using how Ruby treats negative array indices. -1 is the last element of the array, -2 the second last etc.

Ruby, 57

->u,v{(0..2).map{|a|u[b=(a+1)%3]*v[c=(a+2)%3]-u[c]*v[b]}}

In test program

f=->u,v{(0..2).map{|a|u[b=(a+1)%3]*v[c=(a+2)%3]-u[c]*v[b]}}

p f[[3, 1, 4], [1, 5, 9]]

p f[[5, 0, -3], [-3, -2, -8]]

p f[[0.95972, 0.25833, 0.22140],[0.93507, -0.80917, -0.99177]]

p f[[1024.28, -2316.39, 2567.14], [-2290.77, 1941.87, 712.09]]

Level River St

Posted 2016-01-30T02:42:34.237

Reputation: 22 049

2

Jelly, 5 bytes

Takes input in the form \$[[x_1,x_2],[y_1,y_2],[z_1,z_2]]\$. If you want them to be two lists of x-y-z coordinates, just prepend Z to the beginning of the program.

ṁ4ÆḊƝ

Try it online!

Here is a PDF explanation in case SE markdown can't handle it.


The cross-product in analytic form

Let \$(x_1,y_1,z_1)\$ be the coordinates of \$\vec{v_1}\$ and \$(x_2,y_2,z_2)\$ be the coordinates of \$\vec{v_2}\$. Their analytic expressions are as follows:

$$\boldsymbol{\vec{v_1}}=x_1\cdot \boldsymbol{\vec{i}}+y_1\cdot \boldsymbol{\vec{j}}+z_1\cdot\boldsymbol{\vec{k}}$$ $$\boldsymbol{\vec{v_2}}=x_2\cdot \boldsymbol{\vec{i}}+y_2\cdot \boldsymbol{\vec{j}}+z_2\cdot\boldsymbol{\vec{k}}$$

The only thing left to do now is to also write their cross-product in terms of its coordinates in the \$Oxyz\$ space.

$$\boldsymbol{\vec{v_1}}\times \boldsymbol{\vec{v_2}}=\left(x_1\cdot \boldsymbol{\vec{i}}+y_1\cdot \boldsymbol{\vec{j}}+z_1\cdot\boldsymbol{\vec{k}}\right)\times\left(x_2\cdot \boldsymbol{\vec{i}}+y_2\cdot \boldsymbol{\vec{j}}+z_2\cdot\boldsymbol{\vec{k}}\right)$$

Keeping in mind that: $$\boldsymbol{\vec{i}}\times \boldsymbol{\vec{j}}=\boldsymbol{\vec{k}}, \:\: \boldsymbol{\vec{i}}\times \boldsymbol{\vec{k}}=-\boldsymbol{\vec{j}}, \:\: \boldsymbol{\vec{j}}\times \boldsymbol{\vec{i}}=-\boldsymbol{\vec{k}}, \:\: \boldsymbol{\vec{j}}\times \boldsymbol{\vec{k}}=\boldsymbol{\vec{i}}, \:\: \boldsymbol{\vec{k}}\times \boldsymbol{\vec{i}}=\boldsymbol{\vec{j}}, \:\: \boldsymbol{\vec{k}}\times \boldsymbol{\vec{j}}=-\boldsymbol{\vec{i}}$$

After the necessary rearrangements and calculations:

$$\boldsymbol{\vec{v_1}}\times \boldsymbol{\vec{v_2}}=(y_1z_2-z_1y_2)\cdot \boldsymbol{\vec{i}}+(z_1x_2-x_1z_2)\cdot \boldsymbol{\vec{j}}+(x_1y_2-y_1x_2)\cdot \boldsymbol{\vec{k}}$$

The close relationship with matrix determinants

There's an interesting thing to note here:

$$x_1y_2-y_1x_2=\left|\begin{matrix}x_1 & y_1 \\\ x_2 & y_2\end{matrix}\right|$$ $$z_1x_2-x_1z_2=\left|\begin{matrix}z_1 & x_1 \\\ z_2 & x_2\end{matrix}\right|$$ $$y_1z_2-z_1y_2=\left|\begin{matrix}y_1 & z_1 \\\ y_2 & z_2\end{matrix}\right|$$

Where we use the notation \$\left|\cdot\right|\$ for matrix determinant. Notice the beautiful rotational symmetry?

Jelly code explanation

Well... not much to explain here. It just generates the matrix:

$$\left(\begin{matrix}x_1 & y_1 & z_1 & x_1 \\\ x_2 & y_2 & z_2 & x_2\end{matrix}\right)$$

And for each pair of neighbouring matrices, it computes the determinant of the matrix formed by joining the two.

ṁ4ÆḊƝ – Monadic Link. Takes input as [[x1,x2],[y1,y2],[z1,z2]].
ṁ4    – Mold 4. Cycle the list up to length 4, reusing the elements if necessary.
        Generates [[x1,x2],[y1,y2],[z1,z2],[x1,x2]].
    Ɲ – For each pair of neighbours: [[x1,x2],[y1,y2]], [[y1,y2],[z1,z2]], [[z1,z2],[x1,x2]].
  ÆḊ  – Compute the determinant of those 2 paired together into a single matrix.

Mr. Xcoder

Posted 2016-01-30T02:42:34.237

Reputation: 39 774

neater form in the equations here :P – ASCII-only – 2019-01-20T09:09:40.953

2

Python, 73 48 bytes

Thanks @FryAmTheEggman

lambda (a,b,c),(d,e,f):[b*f-c*e,c*d-a*f,a*e-b*d]

This is based on the component definition of the vector cross product.

Try it here

TanMath

Posted 2016-01-30T02:42:34.237

Reputation: 1 431

lambda (a,b,c),(d,e,f):... should save a lot. – FryAmTheEggman – 2016-01-30T03:09:49.253

@FryAmTheEggman You are right. I forgot that lambda can specify how the argument should be. – TanMath – 2016-01-30T03:12:49.720

2

Wolfram Language (Mathematica), 38 33 bytes

Det@{a={i,j,k},##}~Coefficient~a&

Try it online!

alephalpha

Posted 2016-01-30T02:42:34.237

Reputation: 23 988

1

Julia 0.7, 45 39 bytes

f(a,b)=1:3 .|>i->det([eye(3)[i,:] a b])

Try it online!

Uses the determinant-based formula given in the task description.

Thanks to H.PWiz for -6 bytes.

Kirill L.

Posted 2016-01-30T02:42:34.237

Reputation: 6 693

39 bytes with two tricks: f(a,b)=1:3 .|>i->det([eye(3)[i,:] a b]) – H.PWiz – 2019-04-20T01:45:49.727

1

ES6, 40 bytes

(a,b,c,d,e,f)=>[b*f-c*e,c*d-a*f,a*e-b*d]

44 bytes if the input needs to be two arrays:

([a,b,c],[d,e,f])=>[b*f-c*e,c*d-a*f,a*e-b*d]

52 bytes for a more interesting version:

(a,b)=>a.map((_,i)=>a[x=++i%3]*b[y=++i%3]-a[y]*b[x])

Neil

Posted 2016-01-30T02:42:34.237

Reputation: 95 035

0

APL(NARS), 23 chars, 46 bytes

{((1⌽⍺)×5⌽⍵)-(5⌽⍺)×1⌽⍵}

test:

  f←{((1⌽⍺)×5⌽⍵)-(5⌽⍺)×1⌽⍵}
  (3 1 4) f (1 5 9)
¯11 ¯23 14 
  (5 0 ¯3) f (¯3 ¯2 ¯8)
¯6 49 ¯10 
  (0.95972 0.25833 0.22140) f (0.93507 ¯0.80917 ¯0.99177)
¯0.0770537061 1.158846002 ¯1.018133265 
  (1024.28 ¯2316.39 2567.14) f (¯2290.77 1941.87 712.09)
¯6634530.307 ¯6610106.843 ¯3317298.117 

RosLuP

Posted 2016-01-30T02:42:34.237

Reputation: 3 036

0

Pari/GP, 41 bytes

(a,b)->Vec(matdet(Mat([[x^2,x,1],a,b]~)))

Try it online!

alephalpha

Posted 2016-01-30T02:42:34.237

Reputation: 23 988