# Finding vector of same direction with smallest integer coordinates

To determine Miller Indices of crystal lattice planes I would need a stable algorithm which determines the smallest set of integer coordinates of a vector which has same direction as a given vector (e.g. through the unit vector). Let's try out an example: When I have a simple integer vector given as $v=\{1.,2.,3.\}$ and I calculate the unit vector through

v={1.,2.,3.}
e=Normalize[v]


I get

{0.267261, 0.534522, 0.801784}


for e. Using this vector now to reconstruct the original vector by trying to find the smallest integer coordinates e.g. through

Function[x,If[And@@(IntegerQ[#]&)/@x,x,(#/GCD@@#&)@Rationalize[x, 1/10^10]]]]
@Normalize[{1.,2.,3.}]


is just working for vector coordinates which are greater than one (e.g. $\{1.5,2.,3\}$ is yielding the correct result $\{3,4,6\}$) but not for normalized vector coordinates. The above example yields a vector with very high integer coordinates.

I'm sure there is a simple solution to this but it seems that I'm a blockhead on this...

• Is there a reason to use floating point numbers for the initial coordinates? Using exact numbers/integers would eliminate potential errors due to Rationalize. – Yves Klett Dec 8 '15 at 13:00
• @Ives Klett: There is a reason. As mentioned in the question, the issue is related to miller Indices. The input variable is an axis or plane norm vector with float coordinate components. The example with normalized coordinates was just used for illustration. – Rainer Dec 8 '15 at 13:07
• Thanks for the clarification. Hope the suggested solutions are useful. – Yves Klett Dec 8 '15 at 13:09
• @Ives Klett. It is useful, thank you! – Rainer Dec 8 '15 at 17:11

There are probably much better ways, but this seems to work:

v={1.,2.,3.}
e=Normalize[v]

#/GCD @@ # &@Rationalize[e/Max[Abs[e]]]

(*{1, 2, 3}*)


An alternative version (courtesy of J.M.) cleverly uses the second argument of Normalize and reads:

Normalize[Rationalize[Normalize[e, Composition[Max, Abs]]], GCD @@ # &]

• Alternatively: Normalize[Rationalize[Normalize[e, Composition[Max, Abs]]], GCD @@ # &] – J. M. is in limbo Dec 9 '15 at 3:13
• @J.M. much better, and educating as well. Would suggest you add as answer. Reversing the order of Max and Abs gets rid of the whole unpleasant If thing :D – Yves Klett Dec 9 '15 at 7:45
• Hmm, I think I'd prefer that you just edit your answer instead, if it's okay. I merely simplified your procedure, you see. :) – J. M. is in limbo Dec 9 '15 at 8:00
• @J.M. o.k., done :) – Yves Klett Dec 9 '15 at 8:33

As noted by @YvesKlett, this can sometimes be done using Rationalize, with the idea being to get a common denominator.

For hard cases this would be a job for projective simultaneous rationalization. There is a former standard add-on package, available at this library link, for such purpose.

Alternatively one can code a variant from scratch. I'll illustrate with the example from the original post.

v = {1., 2., 3.};
e = Normalize[v]

(* Out[71]= {0.267261241912, 0.534522483825, 0.801783725737} *)


We create a vector that will make its way into a lattice we later reduce.

big = 10^2;
rats = Prepend[Round[big*e/Min[e]], 1]

(* Out[73]= {1, 100, 200, 300} *)


It is fairly clear from the above that our quarry is {1,2,3}. But this is not always so obvious. We proceed as though it were not.

lat = Join[{rats}, Rest[big*IdentityMatrix[Length[rats]]]];
redlat = LatticeReduce[lat];
rows = Select[redlat, #[[1]] =!= 0 &];
rnum = Ordering[Map[N[#].# &, rows], 1][[1]];
xvals = Abs[(rows[[rnum, 1]]*Rest[rats] - Rest[rows[[rnum]]])/big]

(* Out[78]= {1, 2, 3} *)


There is some explanation of how/why this works in these pdf slides

• Can you present some mean cases? It might be interesting to compare the merits of the different approaches. – Yves Klett Dec 9 '15 at 8:36
• @Yves, Am I not a mean enough case? – Daniel Lichtblau Dec 9 '15 at 15:13
• (1) @YvesKlett, Okay, here goes. It requires "large" integers to mess up the Rationalize approach. That happens because Rationalize itself might fail to deliver a sufficiently good rationalization. So something like this gets into trouble: SeedRandom[11122221]; v = RandomInteger[10^7, 3] e = Normalize[N@v]; #/GCD @@ # &@Rationalize[e/Max[Abs[e]]]1 – Daniel Lichtblau Dec 9 '15 at 15:19
• (2) @YvesKlett I should add that my method has its own sensitivity and in particular the multiplier big` needs to be somewhat larger than the integers we hope to recover. For the example I showed in the last comment 10^10 suffices. With smaller multipliers we recover smaller integer sets that give "good" approximations in the sense of having close common ratios. Useful for working with approximations that might have some noise in them. – Daniel Lichtblau Dec 9 '15 at 15:24
• ... almost, but not quite, entirely unlike uninspired... – Yves Klett Dec 9 '15 at 19:55