# Algorithm that generates orthogonal vectors: C++ implementation

Recently I asked the similar question, but the algorithm was implemented in Python. Now I've tried to implement the same algorithm, but in C++ (I'm very new to it):

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include <tgmath.h>
using namespace std;

const int MAXRANGE = 1000;

int randint(int low, int high){
return rand() % (high - low) + low;

}

void generate_vector(float vec[],int dimension){
for (int i = 0; i < dimension; i++){
vec[i] = randint(-MAXRANGE,MAXRANGE);
}

// We need to ensure that the last entry doesn't equal to zero

if (vec[dimension-1] == 0){
while (vec[dimension-1] == 0){
vec[dimension-1] = randint(-MAXRANGE,MAXRANGE);

}
}

}

void generate_orthogonal (float *vector, float orthogonal_vector[], int dimension){
float last_entry;
float dot_product = 0;
for (int i = 0; i < dimension -1; i++){
orthogonal_vector[i] = randint(-MAXRANGE,MAXRANGE);
}
for (int i = 0; i < dimension -1; i++){
dot_product = dot_product + (vector[i] * orthogonal_vector[i]);
}
last_entry = -(dot_product/vector[dimension-1]);
orthogonal_vector[dimension-1] = last_entry;
}

float dot_product(float *vector1, float vector2[],int dimension){
float sum = 0;
for (int i = 0; i < dimension; i++){
sum += (vector1[i])*(vector2[i]);
}
return sum;
}

void print_vector(float *A,int dim){
cout << "(";
for (int i = 0; i < dim; i++){
if (i == dim -1){
cout << A[i];
}
else{
cout << A[i] << ",";}
}
cout << ")^T" << endl;
}
int main(){
srand(time(0));
int dimension;
cout << "Choose dimension for the vector: ";
cin >> dimension;
float arbitrary_vector[dimension], orthogonal[dimension];
generate_vector(arbitrary_vector,dimension);
generate_orthogonal(arbitrary_vector,orthogonal,dimension);
cout << "First vector: ";
print_vector(arbitrary_vector,dimension);
cout << "Orthogonal vector: ";
print_vector(orthogonal,dimension);
cout << "Dot product of the vectors: ";
cout << dot_product(arbitrary_vector,orthogonal,dimension) << endl;

}


What can be improved?

As some people previously pointed out, the algorithm would throw exception if the last entry of the first vector was $$\0\$$. I made an a slight change to ensure that generate_vector function won't generate vector where the last element is zero.

Welcome to C++! This code review focuses on writing idiomatic C++ code.

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include <tgmath.h>


Don't #include <tgmath.h> because it is deprecated. It just includes #include <complex> and #include <cmath>. In this case, you do not use complex numbers, and you have #include <cmath>.

It is common practice to place a space after #include to improve readability. Also, sorting the #include directives makes them easier to navigate:

#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;


Well, no. using namespace std; is considered bad practice in C++ because it potentially introduces name clashes. See Why is using namespace std; considered bad practice?.

Instead, explicitly qualify the names with std::. This won't be a lot of effort once you get used to it, but it really helps to avoid subtle problems.

const int MAXRANGE = 1000;


Constants are indicated with constexpr in C++. In general, constexpr allows the constant to be used in more loci than const does.

ALL CAPS names are usually reserved for macros. They are not commonly used for constants.

int randint(int low, int high){
return rand() % (high - low) + low;

}


The indentation is a bit irregular. There is usually a line break or space before the {.

rand is infamous for being a low-quality random number generator. Use <random> instead. See Why is the new random library better than std::rand()?. Time is also not always considered a good seed. std::random_device is better. The function can be rewritten like this:

int randint(int low, int high)
{
static std::mt19937 engine{std::random_device{}()};

assert(low <= high);
std::uniform_int_distribution<int> dist{low, high};
return dist(engine);
}


Note that I used assert (defined in header <cassert>) to express the pre-condition.

void generate_vector(float vec[],int dimension){
for (int i = 0; i < dimension; i++){
vec[i] = randint(-MAXRANGE,MAXRANGE);
}

// We need to ensure that the last entry doesn't equal to zero

if (vec[dimension-1] == 0){
while (vec[dimension-1] == 0){
vec[dimension-1] = randint(-MAXRANGE,MAXRANGE);

}
}

}


Several problems:

• Containers from the standard library are generally preferred over raw C arrays. Use std::vector instead.

• You should really be generating float values instead of int values.

• Using out-parameters is less idiomatic than using the return value.

• Retrying is not a good strategy to ensure that the last entry is non-zero. Generating a number in [-maxrange, 0) and then having a 50% chance of negating the sign is probably better.

• You can use standard algorithms (available in header <algorithm>) to simplify the code.

Here's how I would fix these problems (without using randint). I have added some comments to help you understand.

constexpr float maxrange = 1000.0f;

std::mt19937 engine{std::random_device{}()};

std::vector<float> generate_vector(int dimension)
{
assert(dimension > 0);

// generate the first (n - 1) elements
std::vector<float> result(dimension);
std::uniform_real_distribution<float> dist{-maxrange, maxrange};
std::generate(result.begin(), result.end() - 1, []{ return dist(engine); });

// generate the last element
dist.param({-maxrange, 0});
result.back() = dist(engine);
// negate the sign with a 50% possibility
if (std::bernoulli_distribution bdist{0.5}; bdist(engine))
result.back() = -result.back();

// NRVO, no copying, no performance degradation
return result;
}


Also, double is generally used instead of float in C++ unless you have a good reason.

void generate_orthogonal (float *vector, float orthogonal_vector[], int dimension){
float last_entry;
float dot_product = 0;
for (int i = 0; i < dimension -1; i++){
orthogonal_vector[i] = randint(-MAXRANGE,MAXRANGE);
}
for (int i = 0; i < dimension -1; i++){
dot_product = dot_product + (vector[i] * orthogonal_vector[i]);
}
last_entry = -(dot_product/vector[dimension-1]);
orthogonal_vector[dimension-1] = last_entry;
}


Some problems, in addition to the aforementioned ones:

• Use ++i, not i++, in the for statement. See Difference between pre-increment and post-increment in a loop?.

• You have the dot product function later, you can use it.

• The elements of vector should be const.

• The last_entry variable is not necessary; just assign the result of the calculation directly to orthogonal_vector[dimension - 1]. It should be obvious that we are referring to the last entry if .back() is used.

Note that dot product is available in the standard library as std::inner_product (available in header <numeric>), so no need to roll out your own.

std::vector<float> generate_orthogonal(const std::vector<float>& vector)
{
// at least one dimension
assert(!vector.empty());

// same
std::vector<float> result(dimension);
std::uniform_real_distribution<float> dist{-maxrange, maxrange};
std::generate(result.begin(), result.end() - 1, []{ return dist(engine); });

// generate the last element
auto dot_product = std::inner_product(vector.begin(), vector.end() - 1, result.begin());
result.back() = -dot_product / vector.back();

// same
return result;
}

float dot_product(float *vector1, float vector2[],int dimension){
float sum = 0;
for (int i = 0; i < dimension; i++){
sum += (vector1[i])*(vector2[i]);
}
return sum;
}


As I said before, this function is available in the standard library as std::inner_product.

void print_vector(float *A,int dim){
cout << "(";
for (int i = 0; i < dim; i++){
if (i == dim -1){
cout << A[i];
}
else{
cout << A[i] << ",";}
}
cout << ")^T" << endl;
}


Don't use std::endl without a reason. Use \n instead.

You can simplify the code by printing the first element first:

void print_vector(const std::vector<float>& vector)
{
assert(!vector.empty());

std::cout << '(' << vector[0];
for (auto it = vector.begin() + 1; it != vector.end(); ++it) {
std::cout << ", " << *it;
}
std::cout << ")^T\n";
}


You may noticed that assert(!vector.empty()) appeared several times in the code. Maybe write a class for that.

• Nice review, there is always benefit in a second set of eyes. Especially if it is a throrough as yours – miscco Sep 22 '19 at 12:24
• Thanks a lot for mentioning std::random_device for seeding. I have some old code to update. – miscco Sep 23 '19 at 7:17
• The prefix/postfix page you link says specifically it does not matter which is used in the kinds of for loops in the OP. – Almo Sep 23 '19 at 15:08

Welcome to C++.

It seems that you are more or less trying to write C code rather than C++ though. Lets have a look at what you can improve:

1. Never do using namespace std; It is a terrible practise that gets you into trouble really fast. std:: is not that hard to type so get in the habit early.

2. If you have compile time constants use them via constexpr

3. Your dot_product function is already implemented in the standard library. It is called inner_product. So the following code can be replaced

float dot_product(float *vector1, float vector2[],int dimension){
float sum = 0;
for (int i = 0; i < dimension; i++){
sum += (vector1[i])*(vector2[i]);
}
return sum;
}


by the following code

std::inner_product(a.cbegin(), a.cend(), b.cbegin(), float(0.0));

4. Similarly there is a generate function that fills a vector with a generator. Note that C++ has a variety of good random number generators (rand() is not one of them) in the <random> header. I don't know why you use integers for the float vectors but you can adapt that easily.

EDIT: Incorporated problems found by @L.F.

#include <algorithm>
#include <random>

class randomStreamUniformInt {
public:
explicit randomStreamUniformInt(int lower_bound, int upper_bound)
: mt(std::random_device{}()), uniform_dist(lower_bound, upper_bound) {}
explicit randomStreamUniformInt(int lower_bound, int upper_bound, double seed)
: mt(seed), uniform_dist(lower_bound, upper_bound) {}

int operator() () { return uniform_dist(mt); }
private:
std::mt19937_64                     mt;
std::uniform_int_distribution<>     uniform_dist;
};

static randomStreamUniformInt rng(-MAXRANGE, MAXRANGE);

std::vector<float> generate random(const std::size_t numElements) {
std::vector<float> res(numElements);
std::generate(res.begin(), res.end(), rng);
return res;
}


It would be even better to pass the random number generator as an argument rather than a global variable. I leave that as an exercise.

5. You should use standard facilities for arrays such as std::vector or std::array depending on whether you know the size at compile time. So the following code:

float arbitrary_vector[dimension], orthogonal[dimension]


Should be better written as

std::vector<float> arbitrary_vector = generate_random(dimension);


Note that it is always better to put each declaration into a single line.

6. Your method generate_orthogonal can be improved accordingly.

std::vector<float> generate_orthogonal(const std::vector<float>& a) {
// get some random data
std::vector<float> b = generate_random(a.size());

// find the last non zero entry in a
// We have to turn the reverse iterator into an iterator via std::prev(rit.base())
auto IsZero = [] (const float f) -> bool { return f == float(0.0);};
auto end = std::prev(std::find_if_not(a.crbegin(), a.crend(), IsZero).base());

// determine the dot product up to end
float dot_product = std::inner_product(a.cbegin(), end, b.cbegin(), float(0.0));

// set the value of b so that the inner product is zero
b[std::distance(a.cbegin(), end)] = - dot_product / (*end);

return b;
}


So put together it would look something like this:

#include <algorithm>
#include <random>
#include <vector>

constexpr int MAXRANGE = 1000;

class randomStreamUniformInt {
public:
explicit randomStreamUniformInt(int lower_bound, int upper_bound)
: mt(std::random_device{}()), uniform_dist(lower_bound, upper_bound) {}
explicit randomStreamUniformInt(int lower_bound, int upper_bound, double seed)
: mt(seed), uniform_dist(lower_bound, upper_bound) {}

int operator() () { return uniform_dist(mt); }
private:
std::mt19937_64                     mt;
std::uniform_int_distribution<>     uniform_dist;
};

static randomStreamUniformInt rng(-MAXRANGE, MAXRANGE);

std::vector<float> generate random(const std::size_t numElements) {
std::vector<float> res(numElements);
std::generate(res.begin(), res.end(), rng);
return res;
}

std::vector<float> generate_orthogonal(const std::vector<float>& a) {
// get some random data
std::vector<float> b = generate_random(a.size());

// find the last non zero entry in a
// We have to turn the reverse iterator into an iterator via std::prev(rit.base())
auto IsZero = [] (const float f) -> bool { return f == float(0.0);};
auto end = std::prev(std::find_if_not(a.crbegin(), a.crend(), IsZero).base());

// determine the dot product up to end
float dot_product = std::inner_product(a.cbegin(), end, b.cbegin(), float(0.0));

// set the value of b so that the inner product is zero
b[std::distance(a.cbegin(), end)] = - dot_product / (*end);

return b;
}

int main() {
std::size_t dimension = 20;

std::vector<float> a = generate_random(dimension);
std::vector<float> b = generate_orthogonal(a);
}

• Oops, didn't notice you already posted an answer because my Internet connection sucks. Sorry for the duplicate information! – L. F. Sep 22 '19 at 12:12
• BTW, it appears that your generate_random function will generate the same numbers every time. Should rng be static? – L. F. Sep 22 '19 at 12:18
• Argh yes, Normally it would be passed around sorry – miscco Sep 22 '19 at 12:23
• maybe mention that builtins like "inner_product" are likely to use SSE2/optimized code, so one more reason not to roll your own. – Jean-François Fabre Sep 22 '19 at 19:50
• Also, float(0.0) is just 0.0f. – L. F. Sep 23 '19 at 11:21