5 ms·

Walking Paths with Complex Numbers

86 points by dannybirch 10y ago

deckar01 10y ago
Here is the pseudo-code for matrix rotation for comparison: def rotate(vector, angle): rotation_matrix = [ [cos(angle), -sin(angle)], [sin(angle), cos(angle)] ] return rotation_matrix * vector position = (0, 0) velocity = (0, 1) for instruction in [x.strip() for x in input.split(",")]: direction = instruction[0] distance = int(instruction[1:]) angle = 90 if direction == 'L' else -90 velocity = rotate(velocity, angle) position += velocity * distance print position
- andars 10y ago
  Since you only work with 90 degrees, you don't even need the full machinery. In my solution I used (a,b) -> (-b,a) and its dual.
ajkjk 10y ago
Erg. It's true that complex numbers model a rotation operator in 2d geometry. But I think it's harmful to say that it's better to think about 2d geometry in terms of complex numbers rather than, well, 2d geometry (vectors and rotation operators/matrices/geometric algebras). This kind of thinking doesn't extend to higher dimensions, obfuscates the actual discovery under the 'magic' of complex numbers, and requires knowing 'one weird trick' to figure out yourself. (edit: added reference to geometric algebras, which are cleaner than rotation matrices for intuitively modeling this.)
- ThrustVectoring 10y ago
  i is a rotation operator in R3 as well - it's just a 3-vector instead of a 1-vector, and textbooks usually call these "quaternions". If you do want to think of geometry in terms of linear algebra structures, you probably want to be studying Geometric Algebra.
  - ajkjk 10y ago
    ah, I'm aware of those things and have studied them extensively -- My point is, I think it's harmful to say "hey, you - you're trying to solve a problem in 2d space? Have you considered using complex numbers?" When the correct thing to do is "have you considered using the algebra of N-d spaces?" (that is, Clifford/geometric algebra), and leave all the magical complex numbers out of it.
    - arh68 10y ago
      What would that look like, code-wise? Is there a good library for this stuff? It's easy to reach for complex numbers when they're built-in. Do you have to use Maple/Mathematica for this stuff, or can you do it easily in Python/JS/&c ?
      - andars 10y ago
        If you are interested in this stuff, I have heard that the book Geometric Algebra for Computer Science is good. You can find the first chapter as a pdf download here: http://geometricalgebra.org/downloads/ga4cs_chapter1.pdf http://geometricalgebra.org/downloads/ga4cs_chapter1.pdf. It contains some code examples, and the complete source code is here: http://geometricalgebra.org/sandbox.html http://geometricalgebra.org/sandbox.html
        jacobolus 10y ago
        I made a list recently: https://news.ycombinator.com/item?id=12941658 https://news.ycombinator.com/item?id=12941658 The GACS book is indeed great. The “conformal model” defined there is very pleasant to work with. If you want to learn about it without buying a textbook, there’s also this PhD thesis: http://www2.eng.cam.ac.uk/~rjw57/pdf/r_wareham_pdh_thesis.pdf http://www2.eng.cam.ac.uk/~rjw57/pdf/r_wareham_pdh_thesis.pd...
      - ajkjk 10y ago
        Well, implementing rotation matrices in code isn't hard, and they should be supported in every mathematical library already. Even more lightweight than matrices is just implementing the transformation on vector objects yourself: a 90-degree rotation left is R(x,y) = (-y, x), and (-R)(x,y) = -(R(x,y)). In higher dimensions this remains true for any 2-dimension subplane, so R_zx(x,y,z) = (z,y,-x). Rotation matrices / other formulations become necessary when you're dealing with being able to rotate through any angle. Though, doing rotations of the matrix 'y = Rx' form suffers mathematical problems like numerical instability and bad behavior. Quaternion rotations or Geometric Algebra's rotors (which are equivalent for N=3, and both take the form y = RxR^-1) work a lot better, and also eliminate a lot of the redundancy in the (skew-symmetric) rotation matrices formulation (4 variables instead of 9, for 3d).
- posterboy 10y ago
  I think it does extend to higher dimension. I have to read up on hypercomplex numbers, Clifford algebra and geometric algebra. Quaternions are known to facilitate arbitrary rotations in 3D. I suppose, complex numbers are more powerful in analysis rather than discrete mathematics, if there is a difference at all.
  - ajkjk 10y ago
    Quaternions model 3d rotations, and Clifford algebras in general model rotations in arbitrary higher dimensions, but it's definitely non-trivial to go from "complex numbers model 2d" to all of that machinery. What I mean is that the intuition around complex numbers doesn't extend. Certainly not the "i is the square root of -1"-level understanding of complex numbers. Clifford algebras are better thought of as structures built over the higher-dimension vectors spaces, with little relationship to algebras/fields. They have much more in common with the matrix representation than the algebraic one. The algebraic perspective only supports complex, quaternion, and octonion numbers before breaking down.
- andars 10y ago
  I'd say if it depends on how you think about complex numbers. If your understanding of the imaginary unit is limited to "that thing that when you square it you get -1", I agree with you. But if you think of the imaginary unit as the 2-blade in the geometric algebra of R^2, I would argue it is one of the best ways to think about 2D geometry.
  - ajkjk 10y ago
    My point is that almost no one thinks about it that way, and that's the problem. People are content using complex numbers and saying 'it magically' works instead of dealing with the actual structure they want to be using.
    - andars 10y ago
      In that case, I agree with you wholeheartedly.
posterboy 10y ago
I still don't get the significance of complex numbers, to me they seem like vectors with certain operations and I still suppose there is no deeper revelation, that sqrt(-1) represents, and every example could have a geometric interpretation, even if this isn't motivated by the example. Likewise, the only explanation for e^(pi*i)-1=0 I know is the conversion to polar coordinates. >Since you need to keep track of your current orientation this slightly complicates things a bit >If at each step we keep the imaginary multiplication term from the previous step we can effectively encode the rotation in our expression Why, you could just keep track of the rotation as an angle, which would likewise be a result of the previous step. In binary there wouldn't even be much of a difference: Look at a 2-bit value either as a modulo 4 ring of type pi/2, or as a modulo 2 vector of the two complex components. That's my first thought, at least. Although, the real and imaginary parts would always have opposite values, so only one bit is needed. I wonder if complexity analysis would show a difference.
- deleted 10y ago
  [deleted]
- ThrustVectoring 10y ago
  The best non-geometric interpretation of complex numbers is algebraic closure, IMO. Basically, mathematicians invent new kinds of numbers when they want to do things and have the result of the operation always be a number. Adding and multiplying natural numbers gets you a natural number. Subtraction on integers yields integers. Division for rational numbers. Infinite series for real numbers. And factoring all polynomials is the raison d'etre for complex numbers.
- posterboy 10y ago
  >e^(pi*i)+1=0 fixed, otherwise e^pi would be trivially wrong
- pdkl95 10y ago
  (first, I second ThrustVectoring's comment about algebraic closure. That's a key part of understanding complex numbers) I recommend reading this[1] article. I found it very enlightening about why complex numbers are useful. [1] https://acko.net/blog/how-to-fold-a-julia-fractal/ https://acko.net/blog/how-to-fold-a-julia-fractal/ edit: Warning - [1] requires WebGL.
jstewartmobile 10y ago
Good stuff! Even though this may not be the best application for complex numbers, it is a very simple example for a practical use. For some person out there, this may even serve as a "gateway drug" to complex analysis.
rosstex 10y ago
https://acko.net/blog/how-to-fold-a-julia-fractal/ https://acko.net/blog/how-to-fold-a-julia-fractal/

86 points by dannybirch 10y ago

Here is the pseudo-code for matrix rotation for comparison: def rotate(vector, angle): rotation_matrix = [ [cos(angle), -sin(angle)], [sin(angle), cos(angle)] ] return rotation_matrix * vector position = (0, 0) velocity = (0, 1) for instruction in [x.strip() for x in input.split(",")]: direction = instruction[0] distance = int(instruction[1:]) angle = 90 if direction == 'L' else -90 velocity = rotate(velocity, angle) position += velocity * distance print position

andars 10y ago
Since you only work with 90 degrees, you don't even need the full machinery. In my solution I used (a,b) -> (-b,a) and its dual.

ajkjk 10y ago

Erg. It's true that complex numbers model a rotation operator in 2d geometry. But I think it's harmful to say that it's better to think about 2d geometry in terms of complex numbers rather than, well, 2d geometry (vectors and rotation operators/matrices/geometric algebras). This kind of thinking doesn't extend to higher dimensions, obfuscates the actual discovery under the 'magic' of complex numbers, and requires knowing 'one weird trick' to figure out yourself. (edit: added reference to geometric algebras, which are cleaner than rotation matrices for intuitively modeling this.)

ThrustVectoring 10y ago
i is a rotation operator in R3 as well - it's just a 3-vector instead of a 1-vector, and textbooks usually call these "quaternions". If you do want to think of geometry in terms of linear algebra structures, you probably want to be studying Geometric Algebra.
- ajkjk 10y ago
  ah, I'm aware of those things and have studied them extensively -- My point is, I think it's harmful to say "hey, you - you're trying to solve a problem in 2d space? Have you considered using complex numbers?" When the correct thing to do is "have you considered using the algebra of N-d spaces?" (that is, Clifford/geometric algebra), and leave all the magical complex numbers out of it.
  - arh68 10y ago
    What would that look like, code-wise? Is there a good library for this stuff? It's easy to reach for complex numbers when they're built-in. Do you have to use Maple/Mathematica for this stuff, or can you do it easily in Python/JS/&c ?
    - andars 10y ago
      If you are interested in this stuff, I have heard that the book Geometric Algebra for Computer Science is good. You can find the first chapter as a pdf download here: http://geometricalgebra.org/downloads/ga4cs_chapter1.pdf http://geometricalgebra.org/downloads/ga4cs_chapter1.pdf. It contains some code examples, and the complete source code is here: http://geometricalgebra.org/sandbox.html http://geometricalgebra.org/sandbox.html
      - jacobolus 10y ago
        I made a list recently: https://news.ycombinator.com/item?id=12941658 https://news.ycombinator.com/item?id=12941658 The GACS book is indeed great. The “conformal model” defined there is very pleasant to work with. If you want to learn about it without buying a textbook, there’s also this PhD thesis: http://www2.eng.cam.ac.uk/~rjw57/pdf/r_wareham_pdh_thesis.pdf http://www2.eng.cam.ac.uk/~rjw57/pdf/r_wareham_pdh_thesis.pd...
    - ajkjk 10y ago
      Well, implementing rotation matrices in code isn't hard, and they should be supported in every mathematical library already. Even more lightweight than matrices is just implementing the transformation on vector objects yourself: a 90-degree rotation left is R(x,y) = (-y, x), and (-R)(x,y) = -(R(x,y)). In higher dimensions this remains true for any 2-dimension subplane, so R_zx(x,y,z) = (z,y,-x). Rotation matrices / other formulations become necessary when you're dealing with being able to rotate through any angle. Though, doing rotations of the matrix 'y = Rx' form suffers mathematical problems like numerical instability and bad behavior. Quaternion rotations or Geometric Algebra's rotors (which are equivalent for N=3, and both take the form y = RxR^-1) work a lot better, and also eliminate a lot of the redundancy in the (skew-symmetric) rotation matrices formulation (4 variables instead of 9, for 3d).
posterboy 10y ago
I think it does extend to higher dimension. I have to read up on hypercomplex numbers, Clifford algebra and geometric algebra. Quaternions are known to facilitate arbitrary rotations in 3D. I suppose, complex numbers are more powerful in analysis rather than discrete mathematics, if there is a difference at all.
- ajkjk 10y ago
  Quaternions model 3d rotations, and Clifford algebras in general model rotations in arbitrary higher dimensions, but it's definitely non-trivial to go from "complex numbers model 2d" to all of that machinery. What I mean is that the intuition around complex numbers doesn't extend. Certainly not the "i is the square root of -1"-level understanding of complex numbers. Clifford algebras are better thought of as structures built over the higher-dimension vectors spaces, with little relationship to algebras/fields. They have much more in common with the matrix representation than the algebraic one. The algebraic perspective only supports complex, quaternion, and octonion numbers before breaking down.
andars 10y ago
I'd say if it depends on how you think about complex numbers. If your understanding of the imaginary unit is limited to "that thing that when you square it you get -1", I agree with you. But if you think of the imaginary unit as the 2-blade in the geometric algebra of R^2, I would argue it is one of the best ways to think about 2D geometry.
- ajkjk 10y ago
  My point is that almost no one thinks about it that way, and that's the problem. People are content using complex numbers and saying 'it magically' works instead of dealing with the actual structure they want to be using.
  - andars 10y ago
    In that case, I agree with you wholeheartedly.

posterboy 10y ago

I still don't get the significance of complex numbers, to me they seem like vectors with certain operations and I still suppose there is no deeper revelation, that sqrt(-1) represents, and every example could have a geometric interpretation, even if this isn't motivated by the example. Likewise, the only explanation for e^(pi*i)-1=0 I know is the conversion to polar coordinates. >Since you need to keep track of your current orientation this slightly complicates things a bit >If at each step we keep the imaginary multiplication term from the previous step we can effectively encode the rotation in our expression Why, you could just keep track of the rotation as an angle, which would likewise be a result of the previous step. In binary there wouldn't even be much of a difference: Look at a 2-bit value either as a modulo 4 ring of type pi/2, or as a modulo 2 vector of the two complex components. That's my first thought, at least. Although, the real and imaginary parts would always have opposite values, so only one bit is needed. I wonder if complexity analysis would show a difference.

deleted 10y ago
[deleted]
ThrustVectoring 10y ago
The best non-geometric interpretation of complex numbers is algebraic closure, IMO. Basically, mathematicians invent new kinds of numbers when they want to do things and have the result of the operation always be a number. Adding and multiplying natural numbers gets you a natural number. Subtraction on integers yields integers. Division for rational numbers. Infinite series for real numbers. And factoring all polynomials is the raison d'etre for complex numbers.
posterboy 10y ago
>e^(pi*i)+1=0 fixed, otherwise e^pi would be trivially wrong
pdkl95 10y ago
(first, I second ThrustVectoring's comment about algebraic closure. That's a key part of understanding complex numbers) I recommend reading this[1] article. I found it very enlightening about why complex numbers are useful. [1] https://acko.net/blog/how-to-fold-a-julia-fractal/ https://acko.net/blog/how-to-fold-a-julia-fractal/ edit: Warning - [1] requires WebGL.

jstewartmobile 10y ago

Good stuff! Even though this may not be the best application for complex numbers, it is a very simple example for a practical use. For some person out there, this may even serve as a "gateway drug" to complex analysis.

rosstex 10y ago

https://acko.net/blog/how-to-fold-a-julia-fractal/ https://acko.net/blog/how-to-fold-a-julia-fractal/