Repository: gonum/gonum
Pull request #2004 (2024-11-28 12:58:27)

graph/path: Improve performance of `YenKShortestPaths`
`YenKShortestPaths`'s running time is dominated by calls to Dijkstra's shortest path algorithm, so it makes sense to focus on improvements there.
For Yen's algorithm, we are not interested in shortest path trees, but only _a_ shortest path between some source and target node. We can exploit this in Dijkstra's algorithm by terminating when the target is discovered.
Of course this does not improve the worst-case complexity, but it should be a worthwhile optimization for many practical uses.

BarrensZeppelin: Done. See #2005
BarrensZeppelin: It does not have the same effect.
Consider the following graph, where we're looking for a path from node 1 to node 2.

![gonum](https://github.com/user-attachments/assets/64477f15-0865-4f13-b753-bbffd53f758b)

With the implementation in the PR, only nodes 1, 2 and 4 are pushed to the priority queue, and only nodes 1 and 2 are popped.
With you suggestion (as I understand it), we would remove the edge from 2 to 3, but we would still compute the shortest path to nodes 4 and 5, which is wasted work.

I guess it's possible to achieve the same effect with composition by making the `From` function stateful: once the target is reached, remove _all_ edges from the graph, but then correctness will depend on the order that Dijkstra's algorithm calls `From`, which seems brittle.

kortschak: Yes, making it stateful would be required. In that construction is has exactly the same behaviour as the code here.

The required code is straightforward.
```
type stopGraph struct {
	g      traverse.Graph
	target int64
}

func (g *stopGraph) From(uid int64) graph.Nodes {
	if uid == g.target {
		g.g = empty{}
	}
	return g.g.From(uid)
}

func (g *stopGraph) Edge(uid, vid int64) graph.Edge {
	if uid == g.target {
		g.g = empty{}
	}
	return g.g.Edge(uid, vid)
}

type empty struct{}

func (empty) From(uid int64) graph.Nodes     { return graph.Empty }
func (empty) Edge(uid, vid int64) graph.Edge { return nil }
```
kortschak: No, you're right.

Patch:
diff --git a/AUTHORS b/AUTHORS
index d17db07f..dc7e93d0 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -103,6 +103,7 @@ Patrick DeVivo <patrick@tickgit.com>
 Pontus Melke <pontusmelke@gmail.com>
 Renee French
 Rishi Desai <desai.rishi1@gmail.com>
+Robert Kleffner <rob.kleffner@gmail.com>
 Robin Eklind <r.eklind.87@gmail.com>
 Roger Welin <roger.welin@icloud.com>
 Rondall Jones <rejones7@gmail.com>
diff --git a/CONTRIBUTORS b/CONTRIBUTORS
index 51acb5a7..bf429a49 100644
--- a/CONTRIBUTORS
+++ b/CONTRIBUTORS
@@ -110,6 +110,7 @@ Patrick DeVivo <patrick@tickgit.com>
 Pontus Melke <pontusmelke@gmail.com>
 Renee French
 Rishi Desai <desai.rishi1@gmail.com>
+Robert Kleffner <rob.kleffner@gmail.com>
 Robin Eklind <r.eklind.87@gmail.com>
 Roger Welin <roger.welin@icloud.com>
 Roman Werpachowski <roman.werpachowski@gmail.com>
diff --git a/README.md b/README.md
index b01b9e1e..9c90a76f 100644
--- a/README.md
+++ b/README.md
@@ -43,7 +43,7 @@ The current list of non-internal tags is as follows:
 - safe — do not use assembly or unsafe
 - bounds — use bounds checks even in internal calls
 - noasm — do not use assembly implementations
-- tomita — use [Tomita, Tanaka, Takahashi pivot choice](https://doi.org/10.1016%2Fj.tcs.2006.06.015) for maximimal clique calculation, otherwise use random pivot (only in [topo package](https://pkg.go.dev/gonum.org/v1/gonum/graph/topo))
+- tomita — use [Tomita, Tanaka, Takahashi pivot choice](https://doi.org/10.1016%2Fj.tcs.2006.06.015) for maximal clique calculation, otherwise use random pivot (only in [topo package](https://pkg.go.dev/gonum.org/v1/gonum/graph/topo))
 
 
 ## Issues [![TODOs](https://badgen.net/https/api.tickgit.com/badgen/github.com/gonum/gonum)](https://www.tickgit.com/browse?repo=github.com/gonum/gonum)
diff --git a/dsp/transform/doc.go b/dsp/transform/doc.go
new file mode 100644
index 00000000..bb4f0b02
--- /dev/null
+++ b/dsp/transform/doc.go
@@ -0,0 +1,6 @@
+// Copyright ©2024 The Gonum Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package transform provides important transforms on signals used in digital signal processing.
+package transform // import "gonum.org/v1/gonum/dsp/transform"
diff --git a/dsp/transform/hilbert.go b/dsp/transform/hilbert.go
new file mode 100644
index 00000000..bf444ee1
--- /dev/null
+++ b/dsp/transform/hilbert.go
@@ -0,0 +1,76 @@
+// Copyright ©2024 The Gonum Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package transform
+
+import (
+	"gonum.org/v1/gonum/dsp/fourier"
+)
+
+// Hilbert implements an approximate Hilbert transform that allows calculation
+// of an approximate analytical signal of a real signal, and determine the
+// real envelope of a signal.
+type Hilbert struct {
+	fft  *fourier.CmplxFFT
+	work []complex128
+}
+
+// NewHilbert returns a new Hilbert transformer for signals of size n.
+// The transform is most efficient when n is a product of small primes.
+// n must not be less than one.
+func NewHilbert(n int) *Hilbert {
+	return &Hilbert{
+		fft:  fourier.NewCmplxFFT(n),
+		work: make([]complex128, n),
+	}
+}
+
+// Len returns the length of signals that are valid input for this Hilbert transform.
+func (h *Hilbert) Len() int {
+	return len(h.work)
+}
+
+// AnalyticSignal computes the analytical signal of a real signal, and stores
+// the result in the dst slice, returning it.
+//
+// If the dst slice is nil, a new slice will be created and returned. The dst slice
+// must be the same length as the input signal, otherwise the method will panic.
+func (h *Hilbert) AnalyticSignal(dst []complex128, signal []float64) []complex128 {
+	if len(signal) != h.Len() {
+		panic("transform: input signal length mismatch")
+	}
+
+	if dst == nil {
+		dst = make([]complex128, len(signal))
+	} else if len(dst) != h.Len() {
+		panic("transform: destination length mismatch")
+	}
+
+	for i, v := range signal {
+		h.work[i] = complex(v, 0)
+	}
+
+	// Forward FFT of the signal.
+	coeff := h.fft.Coefficients(dst, h.work)
+	for i := range h.work {
+		h.work[i] = 0
+	}
+
+	// Multiply positive frequencies by 2, zero out negative frequencies.
+	// However, leave dc unchanged (and nyquist when n%2 == 0).
+	h.work[0] = coeff[0]
+	for i, d := range coeff[1 : len(coeff)/2+1] {
+		h.work[i+1] = d * 2
+	}
+	if len(coeff)%2 == 0 {
+		h.work[len(coeff)/2] = coeff[len(coeff)/2]
+	}
+
+	// Normalize the results so they have a similar amplitude to the input
+	unnorm := h.fft.Sequence(dst, h.work)
+	for i, u := range unnorm {
+		unnorm[i] = u / complex(float64(len(unnorm)), 0)
+	}
+	return unnorm
+}
diff --git a/graph/path/dijkstra.go b/graph/path/dijkstra.go
index 96faa816..7ba8395d 100644
--- a/graph/path/dijkstra.go
+++ b/graph/path/dijkstra.go
@@ -20,8 +20,30 @@ import (
 //
 // The time complexity of DijkstraFrom is O(|E|.log|V|).
 func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
+	return dijkstraFrom(u, nil, g)
+}
+
+// DijkstraFromTo returns a shortest path from u to t in the graph g. The
+// result is equivalent to DijkstraFrom(u, g).To(t.ID()), but DijkstraFromTo
+// can be more efficient, as it can terminate early if t is reached. If the
+// graph does not implement Weighted, UniformCost is used. DijkstraFromTo will
+// panic if g has a u-reachable negative edge weight that is discovered before
+// reaching t.
+//
+// The time complexity of DijkstraFromTo is O(|E|.log|V|).
+func DijkstraFromTo(u, t graph.Node, g traverse.Graph) (path []graph.Node, weight float64) {
+	// An implementation of Bidirectional Dijkstra's algorithm could be even
+	// more efficient, but it requires a transposed (or undirected) graph.
+	if t == nil {
+		panic("dijkstra: nil target node")
+	}
+	return dijkstraFrom(u, t, g).To(t.ID())
+}
+
+func dijkstraFrom(u, t graph.Node, g traverse.Graph) Shortest {
 	var path Shortest
-	if h, ok := g.(graph.Graph); ok {
+	// Use the incremental version when a target is provided.
+	if h, ok := g.(graph.Graph); t == nil && ok {
 		if h.Node(u.ID()) == nil {
 			return Shortest{from: u}
 		}
@@ -58,6 +80,9 @@ func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
 			continue
 		}
 		mnid := mid.node.ID()
+		if t != nil && mnid == t.ID() {
+			break
+		}
 		to := g.From(mnid)
 		for to.Next() {
 			v := to.Node()
diff --git a/graph/path/yen_ksp.go b/graph/path/yen_ksp.go
index b6cb660f..7bc38752 100644
--- a/graph/path/yen_ksp.go
+++ b/graph/path/yen_ksp.go
@@ -33,7 +33,7 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
 		yk.weight = UniformCost(g)
 	}
 
-	shortest, weight := DijkstraFrom(s, yk).To(t.ID())
+	shortest, weight := DijkstraFromTo(s, t, yk)
 	cost += weight // Set cost to absolute cost limit.
 	switch len(shortest) {
 	case 0:
@@ -73,7 +73,7 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][]
 				yk.removeNode(u.ID())
 			}
 
-			spath, weight := DijkstraFrom(spur, yk).To(t.ID())
+			spath, weight := DijkstraFromTo(spur, t, yk)
 			if weight > cost || math.IsInf(weight, 1) {
 				continue
 			}
diff --git a/mathext/beta.go b/mathext/beta.go
index 203ec577..2df51f3d 100644
--- a/mathext/beta.go
+++ b/mathext/beta.go
@@ -18,7 +18,7 @@ import "gonum.org/v1/gonum/mathext/internal/gonum"
 //	B(a,b) returns NaN if a or b is < 0
 //	B(a,b) returns +Inf if a xor b is 0.
 //
-// See http://mathworld.wolfram.com/BetaFunction.html for more detailed informations.
+// See http://mathworld.wolfram.com/BetaFunction.html for more detailed information.
 func Beta(a, b float64) float64 {
 	return gonum.Beta(a, b)
 }
diff --git a/optimize/functions/functions.go b/optimize/functions/functions.go
index 233d71dc..d3ae55a0 100644
--- a/optimize/functions/functions.go
+++ b/optimize/functions/functions.go
@@ -710,7 +710,7 @@ func (BrownAndDennis) Minima() []Minimum {
 //
 // References:
 //   - Spedicato E.: Computational experience with quasi-Newton algorithms for
-//     minimization problems of moderatly large size. Towards Global
+//     minimization problems of moderately large size. Towards Global
 //     Optimization 2 (1978), 209-219
 //   - More, J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained
 //     optimization software. ACM Trans Math Softw 7 (1981), 17-41
@@ -1334,7 +1334,7 @@ func (PowellBadlyScaled) Minima() []Minimum {
 //
 // References:
 //   - Spedicato E.: Computational experience with quasi-Newton algorithms for
-//     minimization problems of moderatly large size. Towards Global
+//     minimization problems of moderately large size. Towards Global
 //     Optimization 2 (1978), 209-219
 //   - More, J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained
 //     optimization software. ACM Trans Math Softw 7 (1981), 17-41
diff --git a/stat/distmv/dirichlet.go b/stat/distmv/dirichlet.go
index 4869f022..fec49ce4 100644
--- a/stat/distmv/dirichlet.go
+++ b/stat/distmv/dirichlet.go
@@ -134,7 +134,7 @@ func (d *Dirichlet) Prob(x []float64) float64 {
 	return math.Exp(d.LogProb(x))
 }
 
-// Rand generates a random number according to the distributon.
+// Rand generates a random number according to the distribution.
 //
 // If dst is not nil, the sample will be stored in-place into dst and returned,
 // otherwise a new slice will be allocated first. If dst is not nil, it must
diff --git a/stat/distmv/interfaces.go b/stat/distmv/interfaces.go
index 35dd2550..04f56aa2 100644
--- a/stat/distmv/interfaces.go
+++ b/stat/distmv/interfaces.go
@@ -18,9 +18,11 @@ type LogProber interface {
 	LogProb(x []float64) float64
 }
 
-// Rander generates a random number according to the distributon.
+// Rander generates a random number according to the distribution.
+//
 // If the input is non-nil, len(x) must equal len(p) and the dimension of the distribution,
 // otherwise Quantile will panic.
+//
 // If the input is nil, a new slice will be allocated and returned.
 type Rander interface {
 	Rand(x []float64) []float64
diff --git a/stat/distmv/normal.go b/stat/distmv/normal.go
index bd609eeb..8d6cc814 100644
--- a/stat/distmv/normal.go
+++ b/stat/distmv/normal.go
@@ -294,7 +294,7 @@ func (n *Normal) Quantile(dst, p []float64) []float64 {
 	return dst
 }
 
-// Rand generates a random sample according to the distributon.
+// Rand generates a random sample according to the distribution.
 //
 // If dst is not nil, the sample will be stored in-place into dst and returned,
 // otherwise a new slice will be allocated first. If dst is not nil, it must
@@ -303,7 +303,7 @@ func (n *Normal) Rand(dst []float64) []float64 {
 	return NormalRand(dst, n.mu, &n.chol, n.src)
 }
 
-// NormalRand generates a random sample from a multivariate normal distributon
+// NormalRand generates a random sample from a multivariate normal distribution
 // given by the mean and the Cholesky factorization of the covariance matrix.
 //
 // If dst is not nil, the sample will be stored in-place into dst and returned,
diff --git a/stat/distmv/studentst.go b/stat/distmv/studentst.go
index e038d506..2ef71bec 100644
--- a/stat/distmv/studentst.go
+++ b/stat/distmv/studentst.go
@@ -331,7 +331,7 @@ func (s *StudentsT) Prob(y []float64) float64 {
 	return math.Exp(s.LogProb(y))
 }
 
-// Rand generates a random sample according to the distributon.
+// Rand generates a random sample according to the distribution.
 //
 // If dst is not nil, the sample will be stored in-place into dst and returned,
 // otherwise a new slice will be allocated first. If dst is not nil, it must
diff --git a/stat/distmv/uniform.go b/stat/distmv/uniform.go
index 74235903..75082f7a 100644
--- a/stat/distmv/uniform.go
+++ b/stat/distmv/uniform.go
@@ -155,7 +155,7 @@ func (u *Uniform) Prob(x []float64) float64 {
 	return math.Exp(u.LogProb(x))
 }
 
-// Rand generates a random sample according to the distributon.
+// Rand generates a random sample according to the distribution.
 //
 // If dst is not nil, the sample will be stored in-place into dst and returned,
 // otherwise a new slice will be allocated first. If dst is not nil, it must


Test patch:
diff --git a/dsp/transform/hilbert_example_test.go b/dsp/transform/hilbert_example_test.go
new file mode 100644
index 00000000..2f571dd4
--- /dev/null
+++ b/dsp/transform/hilbert_example_test.go
@@ -0,0 +1,56 @@
+// Copyright ©2024 The Gonum Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package transform
+
+import (
+	"fmt"
+	"math/cmplx"
+)
+
+func ExampleHilbert_AnalyticSignal() {
+	// Samples is a set of real amplitudes that make up a signal.
+	samples := []float64{1, 0, 2, 0, 4, 0, 2, 0}
+
+	// Initialize a Hilbert transform and 'demodulate' to get the
+	// analytic signal.
+	// The result is the complex I/Q (In-Phase / Quadrature) demodulation
+	// of the input signal.
+	h := NewHilbert(len(samples))
+	iqSamples := h.AnalyticSignal(nil, samples)
+
+	// We can compute the instantaneous amplitude of the signal
+	// (or 'envelope') using absolute value. Analyzing the envelope
+	// is an easy way to measure changes in amplitude over time in a
+	// signal.
+	envelope := make([]float64, len(samples))
+	for ind, iq := range iqSamples {
+		envelope[ind] = cmplx.Abs(iq)
+	}
+
+	// We can also compute the instantaneous phase of each part of the
+	// signal using the 4-quadrant arc-tangent. With multiple samples,
+	// the instantaneous phase can be used to estimate instantaneous
+	// frequency of a signal.
+	phase := make([]float64, len(samples))
+	for ind, iq := range iqSamples {
+		phase[ind] = cmplx.Phase(iq)
+	}
+
+	for i, iq := range iqSamples {
+		fmt.Printf("ind=%d -> I=%.4f, Q=%.4f, envelope=%.4f, phase=%.4f\n",
+			i, real(iq), imag(iq), envelope[i], phase[i])
+	}
+
+	// Output:
+	//
+	// ind=0 -> I=1.0000, Q=0.0000, envelope=1.0000, phase=0.0000
+	// ind=1 -> I=-0.0000, Q=-0.8107, envelope=0.8107, phase=-1.5708
+	// ind=2 -> I=2.0000, Q=0.0000, envelope=2.0000, phase=0.0000
+	// ind=3 -> I=-0.0000, Q=-1.3107, envelope=1.3107, phase=-1.5708
+	// ind=4 -> I=4.0000, Q=0.0000, envelope=4.0000, phase=0.0000
+	// ind=5 -> I=0.0000, Q=1.3107, envelope=1.3107, phase=1.5708
+	// ind=6 -> I=2.0000, Q=0.0000, envelope=2.0000, phase=0.0000
+	// ind=7 -> I=0.0000, Q=0.8107, envelope=0.8107, phase=1.5708
+}
diff --git a/dsp/transform/hilbert_test.go b/dsp/transform/hilbert_test.go
new file mode 100644
index 00000000..3a671cdb
--- /dev/null
+++ b/dsp/transform/hilbert_test.go
@@ -0,0 +1,57 @@
+// Copyright ©2024 The Gonum Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package transform
+
+import (
+	"testing"
+
+	"gonum.org/v1/gonum/cmplxs"
+)
+
+var hilbertAnalyticSignalTests = []struct {
+	name string
+	in   []float64
+	want []complex128
+}{
+	{
+		name: "zeros",
+		in:   []float64{0, 0, 0, 0},
+		want: []complex128{0, 0, 0, 0}},
+	{
+		name: "whole_components",
+		in:   []float64{1, 2, 3, 4},
+		want: []complex128{1 + 1i, 2 - 1i, 3 - 1i, 4 + 1i},
+	},
+	{
+		name: "irrational_imaginary_components",
+		in:   []float64{1, 2, 3, 4, 5},
+		want: []complex128{
+			1 + 1.7013016167i,
+			2 - 1.3763819204i,
+			3 - 0.6498393924i,
+			4 - 1.3763819204i,
+			5 + 1.7013016167i,
+		},
+	},
+}
+
+func TestHilbertAnalytic(t *testing.T) {
+	const tol = 1e-10
+
+	for _, test := range hilbertAnalyticSignalTests {
+		t.Run(test.name, func(t *testing.T) {
+			h := NewHilbert(len(test.in))
+			if h.Len() != len(test.in) {
+				t.Errorf("unexpected Hilbert transform length: got:%d, want:%d", h.Len(), len(test.in))
+			}
+
+			dst := make([]complex128, len(test.in))
+			got := h.AnalyticSignal(dst, test.in)
+			if !cmplxs.EqualApprox(got, test.want, tol) {
+				t.Errorf("unexpected Hilbert transform result:\ngot: %v\nwant:%v", got, test.want)
+			}
+		})
+	}
+}
diff --git a/graph/path/dijkstra_test.go b/graph/path/dijkstra_test.go
index 99762bbf..bab2d2d8 100644
--- a/graph/path/dijkstra_test.go
+++ b/graph/path/dijkstra_test.go
@@ -27,9 +27,11 @@ func TestDijkstraFrom(t *testing.T) {
 		for _, tg := range []struct {
 			typ string
 			g   traverse.Graph
+			t   graph.Node
 		}{
-			{"complete", g.(graph.Graph)},
-			{"incremental", incremental{g.(graph.Weighted)}},
+			{"complete", g.(graph.Graph), nil},
+			{"incremental", incremental{g.(graph.Weighted)}, nil},
+			{"single-destination", g.(graph.Graph), test.Query.To()},
 		} {
 			var (
 				pt Shortest
@@ -40,13 +42,13 @@ func TestDijkstraFrom(t *testing.T) {
 				defer func() {
 					panicked = recover() != nil
 				}()
-				pt = DijkstraFrom(test.Query.From(), tg.g)
+				pt = dijkstraFrom(test.Query.From(), tg.t, tg.g)
 			}()
 			if panicked || test.HasNegativeWeight {
 				if !test.HasNegativeWeight {
 					t.Errorf("%q %s: unexpected panic", test.Name, tg.typ)
 				}
-				if !panicked {
+				if !panicked && tg.t == nil {
 					t.Errorf("%q %s: expected panic for negative edge weight", test.Name, tg.typ)
 				}
 				continue
@@ -62,7 +64,7 @@ func TestDijkstraFrom(t *testing.T) {
 					test.Name, tg.typ, weight, test.Weight)
 			}
 			if weight := pt.WeightTo(test.Query.To().ID()); weight != test.Weight {
-				t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+				t.Errorf("%q %s: unexpected weight from WeightTo: got:%f want:%f",
 					test.Name, tg.typ, weight, test.Weight)
 			}
 
diff --git a/graph/product/product_ext_example_test.go b/graph/product/product_ext_example_test.go
index e868faaf..955e5b5d 100644
--- a/graph/product/product_ext_example_test.go
+++ b/graph/product/product_ext_example_test.go
@@ -54,13 +54,13 @@ func ExampleModularExt_subgraphIsomorphism() {
 
 	// Make a graph for the query pattern: a love triangle.
 	pattern := simple.NewDirectedGraph()
-	for _, relationsip := range []simple.WeightedEdge{
+	for _, relationship := range []simple.WeightedEdge{
 		{F: person{name: "A", id: -1}, T: person{name: "B", id: -2}, W: 1},
 		{F: person{name: "B", id: -2}, T: person{name: "A", id: -1}, W: 1},
 		{F: person{name: "C", id: -3}, T: person{name: "A", id: -1}, W: -1},
 		{F: person{name: "C", id: -3}, T: person{name: "B", id: -2}, W: 1},
 	} {
-		pattern.SetEdge(relationsip)
+		pattern.SetEdge(relationship)
 	}
 
 	// Produce the modular product of the two graphs.
diff --git a/mat/vector_test.go b/mat/vector_test.go
index 89e3fceb..258cab7a 100644
--- a/mat/vector_test.go
+++ b/mat/vector_test.go
@@ -118,7 +118,7 @@ func TestCap(t *testing.T) {
 	} {
 		got := test.vector.Cap()
 		if got != test.want {
-			t.Errorf("unexpected capacty for test %d: got: %d want: %d", i, got, test.want)
+			t.Errorf("unexpected capacity for test %d: got: %d want: %d", i, got, test.want)
 		}
 	}
 }
diff --git a/stat/samplemv/halton_test.go b/stat/samplemv/halton_test.go
index 7a03ca46..b2381950 100644
--- a/stat/samplemv/halton_test.go
+++ b/stat/samplemv/halton_test.go
@@ -28,7 +28,7 @@ func TestHalton(t *testing.T) {
 		batch := mat.NewDense(test.n, test.d, nil)
 		Halton{Kind: Owen, Q: distmv.NewUnitUniform(test.d, nil), Src: src}.Sample(batch)
 
-		// In each dimension, the samples should be stratefied according to the
+		// In each dimension, the samples should be stratified according to the
 		// prime for that dimension. There should be at most 1 sample per
 		// 1/b^k block, where k is log(n)/log(b).
 		for d := 0; d < test.d; d++ {