# Blog Archives

## Project Euler Problem#12 solution in C++

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^{th} triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1

3: 1,3

6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

**Solution:**

#include <cstdio> #include <cmath> int numDivisors(int num) { int divisors = 1, exp; //handle 2 and 3 as special case exp = 0; while (num % 2 == 0) { num /= 2; exp++; } divisors *= (exp+1); exp = 0; while (num % 3 == 0) { num /= 3; exp++; } divisors *= (exp+1); //the other primes are 6k +/- 1 int i = 5; int root = floor(sqrt(num)); while (i <= root) { exp = 0; while (num % i == 0) { num /= i; exp++; } divisors *= (exp+1); if (i % 6 == 1) i += 4; else i += 2; root = floor(sqrt(num)); } //a single largest prime factor if (num != 1) divisors *= 2; return divisors; } int main(void) { int n = 0; int divisors = 0; while (divisors <= 500) { //while (n <= 10) { n++; //since t = n*(n+1)/2 and gcd(n,n+1)=1 if (n % 2 == 0) divisors = numDivisors(n/2) * numDivisors(n+1); else divisors = numDivisors(n) * numDivisors((n+1)/2); } printf("%d - %ld: %d\n", n, (long)n*(n+1)/2, divisors); }

###### Related articles

- Project Euler Problem#10 solution in C++ (alikhuram.wordpress.com)
- Project Euler problem#9 solution in C++ (alikhuram.wordpress.com)
- What is Pascal’s Triangle?, Part 2 (scientificamerican.com)

## Computing the Fast Fourier Transform Algorithm in C++

The Fourier transform is an important equation for spectral analysis, and is required frequently in engineering and scientific applications. The FFT is an algorithm for computing a DFT that operates in N log2(N) complexity versus the expected N2 complexity of a naive implementation of a DFT. The FFT achieves such an impressive speed-up by removing redundant computations.

Finding a good FFT implementation written in idiomatic C++ (i.e., C++ that isn’t mechanically ported from old Fortran or C algorithms) and that isn’t severely restricted by a license is very hard. The code in Example below is based on public domain code that can be found on the digital signal processing newswgoup on usenet (comp.dsp). A big advantage of an idiomatic C++ solution over the more common C-style FFT implementations is that the standard library provides the complex template that significantly reduces the amount of code needed. The fft( ) function in below, was written to be as simple as possible rather than focusing on efficiency.

Solution:

The code below provides a basic implementation of the FFT.

#include <iostream> #include <complex> #include <cmath> #include <iterator> using namespace std; unsigned int bitReverse(unsigned int x, int log2n) { int n = 0; int mask = 0x1; for (int i=0; i < log2n; i++) { n <<= 1; n |= (x & 1); x >>= 1; } return n; } const double PI = 3.1415926536; template<class Iter_T> void fft(Iter_T a, Iter_T b, int log2n) { typedef typename iterator_traits<iter_t>::value_type complex; const complex J(0, 1); int n = 1 << log2n; for (unsigned int i=0; i < n; ++i) { b[bitReverse(i, log2n)] = a[i]; } for (int s = 1; s <= log2n; ++s) { int m = 1 << s; int m2 = m >> 1; complex w(1, 0); complex wm = exp(-J * (PI / m2)); for (int j=0; j < m2; ++j) { for (int k=j; k < n; k += m) { complex t = w * b[k + m2]; complex u = b[k]; b[k] = u + t; b[k + m2] = u - t; } w *= wm; } } } int main( ) { typedef complex cx; cx a[] = { cx(0,0), cx(1,1), cx(3,3), cx(4,4), cx(4, 4), cx(3, 3), cx(1,1), cx(0,0) }; cx b[8]; fft(a, b, 3); for (int i=0; i<8; ++i) cout << b[i] << "\n"; }

The program produces the following output:

(16,16)

(-4.82843,-11.6569)

(0,0)

(-0.343146,0.828427)

(0,0)

(0.828427,-0.343146)

(0,0)

(-11.6569,-4.82843)

###### Related articles

- FFT-less $O(n\log n)$ algorithm for pairwise sums (cs.stackexchange.com)
- Image interpolation with the fast Fourier transform (eliteraspberries.com)
- Retrotechtacular: The Fourier Series (hackaday.com)
- Speeding up MR Image Reconstruction with GeneRalized Autocalibrating Partially Acquisitions (GRAPPA) (elekslabs.com)

## Single-Source Shortest Path (Dijkstra’s Algorithm Implementation in C++)

Suppose you want to fly a private plane on the shortest path from Saint Johns bury, VT to Waco, TX. Assume you know the distances between the airports for all pairs of cities and towns that are reachable from each other in one nonstop flight of your plane. The best-known algorithm to solve this problem, Dijkstra’s Algorithm, finds the shortest path from Saint Johns bury to all other airports, although the search may be halted once the shortest path to Waco is known.

Dijkstra’s Algorithm conceptually operates in greedy fashion by expanding a set of vertices, *S, *for which the shortest path from *s *to every vertex *VE **S *is known, *but only using paths that include vertices **in S. *Initially, *S *equals the set {s}. To expand *S*, Dijkstra’s Algorithm finds the vertex *VE **V-S* whose distance to *s *is smallest, and follows *v’s *edges to see whether a shorter path exists to another vertex. After processing *v**2** **, *for example, the algorithm determines that the distance from *s *to *v**3 *is really 17 through the path *<s,v**2** **,v** **3**>.** *Once *S *expands to equal *V, *the algorithm completes.

**Input/Output**

**Input**

A directed, weighted graph *G=(V,E) *and a source vertex sE *V. *Each edge *e=**(**u,v**) *has an associated positive weight in the graph. The quantity *n *represents the number of vertices in G.

**Output**

Dijkstra’s Algorithm produces two computed arrays. The primary result is the array dist[] of values representing the distance from source vertex *s *to each vertex in the graph. Note that d ist[ s] is zero. The secondary result is the array p red [), which can be used to rediscover the actual shortest paths from vertex *s *to each vertex in the graph.

**Assumptions**

The edge weights are positive (i.e., greater than zero); if this assumption is not true, then dist[u] may contain invalid results. Even worse, Dijkstra’s Algorithm will loop forever if a cycle exists whose sum of all weights is less than zero.

**Solution**

As Dijkstra’s Algorithm executes, dis t[v] represents the maximum length of the shortest path found from the source *s *to *v *using only vertices visited within the setS. Also, for each vES, dist[v] is correct. Fortunately, Dijkstra’s Algorithm does not actually compute and store the setS. It initially constructs a set containing the vertices in *V, *and then it removes vertices one at a time from the set to compute proper dis t[v] values; for convenience, we continue to refer to this ever-shrinking set as *V-S. *Dijkstra’s Algorithm terminates when all vertices are either visited or are shown to not be reachable from the source vertex *s.*

In the C++ solution shown below, a binary heap stores the vertices in the set *V-S *as a priority queue because, in constant time, one can locate the vertex with smallest priority (where the priority is determined by the vertex’s distance from s). Additionally, when a shorter path from *s *to *v *is found, dist [ v ] is decreased, requiring the heap to be modified. Fortunately, the decrease Key operation on priority queues represented using binary heaps can be performed on average in O(log *q) *time, where *q *is the number of verticesin the binary heap, which will always be less than or equal to the number of vertices, *n.*

//Dijkstra’s Algorithm with priority queue implementation #include "BinaryHeap.h" #include "Graph.h" /** Given directed, weighted graph, compute shortest distance to vertices * (dist) and record predecessor links (pred) for all vertices. */ void singleSourceShortest(Graph const &g, int s, vector &dist, vector &pred) { // initialize dist[] and pred[] arrays. Start with vertex s by setting // dist[] to 0. Priority Queue PQ contains all v in G. const int n = g.numVertices( ); pred.assign(n, -1); dist.assign(n, numeric_limits<int>::max( )); dist[s] = 0; BinaryHeap pq(n); for (int u = 0; u < n; u++) { pq.insert (u, dist[u]); } // find vertex in ever-shrinking set, V-S, whose dist[] is smallest. // Recompute potential new paths to update all shortest paths while (!pq.isEmpty( )) { int u = pq.smallest( ); // For neighbors of u, see if newLen (best path from s->u + weight // of edge u->v) is better than best path from s->v. If so, update // in dist[v] and re-adjust binary heap accordingly. Compute in // long to avoid overflow error. for (VertexList::const_iterator ci = g.begin(u); ci != g.end(u); ++ci) { int v = ci->first; long newLen = dist[u]; newLen += ci->second; if (newLen < dist[v]) { pq.decreaseKey (v, newLen); dist[v] = newLen; pred[v] = u; } } } }

**Consequences**

Arithmetic error also may occur if the sum of the individual edge weights exceeds numeric_limits<i n t>: :max () (although the individual values do not). To avoid this situation, the computed new len uses a long data type.

**Analysis**

In the implementation of Dijkstra’s Algorithm, the loop that constructs the initial priority queue performs the insert operation *V *times, resulting in performance *O(V *log V). In the remaining while loop, each edge is visited once, and thus decrease Key is called no more than E times, which contributes *O(E *log V) time. Thus, the overall performance is O(( V *+E) *log V).

The C++ implementation below is simpler since it avoids the use of a binary heap. Th e efficiency of this version is determined by considering how fast the smallest dist [] value in *V-S *can be retrieved. The while loop is executed *n *times, since *S *grows on e vertex at a time. Finding the smallest dist [ u] in *V-S *inspects all *n *vertices. Note that each edge is inspected exactly once in the inner loop within the while loop. Thus, the total running time of this version is 0 (V 2+E).

//Implementation of Dijkstra’s Algorithm for dense graphs #include "Graph.h" void singleSourceShortest(Graph const &graph, int s, vector &dist, vector &pred) { // initialize dist[] and pred[] arrays. Start with vertex s by setting // dist[] to 0. const int n = graph.numVertices( ); pred.assign(n, -1); dist.assign(n, numeric_limits<int>::max( )); vector<bool> visited(n); dist[s] = 0; // find vertex in ever-shrinking set, V-S, whose dist value is smallest // Recompute potential new paths to update all shortest paths while (true) { // find shortest distance so far in unvisited vertices int u = -1; int sd = numeric_limits<int>::max( ); // assume not reachable for (int i = 0; i < n; i++) { if (!visited[i] && dist[i] < sd) { sd = dist[i]; u = i; } } if (u == -1) { break; // no more progress to be made } // For neighbors of u, see if length of best path from s->u + weight // of edge u->v is better than best path from s->v. visited[u] = true; for (VertexList::const_iterator ci = graph.begin(u); ci != graph.end(u); ++ci) { int v = ci->first; // the neighbor v long newLen = dist[u]; // compute as long newLen += ci->second; // sum with (u,v) weight if (newLen < dist[v]) { dist[v] = newLen; pred[v] = u; } } } }

We can further optimize to remove all of the C++ standard template library objects, as shown below. By reducing the overhead of the supporting classes, we realize impressive performance benefits, as discussed in the “Comparison” section.

/** * Optimized Dijkstra’s Algorithm for dense graphs * * Given int[][] of edge weights in raw form, compute shortest distance to * all vertices in graph (dist) and record predecessor links for all * vertices (pred) to be able to recreate these paths. An edge weight of * INF means no edge. Suitable for Dense Graphs Only. */ void singleSourceShortestDense(int n, int ** const weight, int s,int *dist, int *pred) { // initialize dist[] and pred[] arrays. Start with vertex s by setting // dist[] to 0. All vertices are unvisited. bool *visited = new bool[n]; for (int v = 0; v < n; v++) { dist[v] = numeric_limits<int>::max( ); pred[v] = -1; visited[v] = false; } dist[s] = 0; // find shortest distance from s to all unvisited vertices. Recompute // potential new paths to update all shortest paths. Exit if u remains -1. while (true) { int u = -1; int sd = numeric_limits<int>::max( ); for (int i = 0; i < n; i++) { if (!visited[i] && dist[i] < sd) { sd = dist[i]; u = i; } } if (u == -1) { break; } // For neighbors of u, see if length of best path from s->u + weight // of edge u->v is better than best path from s->v. Compute using longs. visited[u] = true; for (int v = 0; v < n; v++) { int w = weight[u][v]; if (v == u) continue; long newLen = dist[u]; newLen += w; if (newLen < dist[v]) { dist[v] = newLen; pred[v] = u; } } } delete [] visited; }

###### Related articles

- Dijkstra’s Algorithm (woodscompscitutorials.wordpress.com)
- Practice (graph searching) Dijkstra algorithm (codekhal.wordpress.com)
- How to record all the shortest paths from a source vertex to a destination vertex (stackoverflow.com)
- Dijkstra algorithm, application to problem RoboCourier I3 (codekhal.wordpress.com)
- SSSP (Single Source Shortest Path) on weighted graph (mohamed0essam.wordpress.com)
- Graph Theory in Everyday Life (gavinleroux.wordpress.com)

## Project Euler Problem#10 solution in C++

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

**Explanation:**

In mathematics, the **sieve of Eratosthenes** (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.^{[1]}

The multiples of a given prime are generated starting from that prime, as a sequence of numbers with the same difference, equal to that prime, between consecutive numbers.^{[1]} This is the sieve’s key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.^{[2]}

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so).^{[3]} It is named after Eratosthenes of Cyrene, a Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the *Introduction to Arithmetic* by Nicomachus.^{[4]}

(above explanation taken from Wikipedia)

C++ solution:

*//solution is written in a flexible manner that you could compute sum of n prime numbers.*

#include <iostream>

using namespace std;

int find_prime (long *numArray, int maxNum)

{

long factor = 2; // we will make 2 as the starting point.

numArray[1] = 0; // rule out 1 from our logic to avoid incorrect results.

// loop condition will check, if we are in our maximum number limit.

//maxNum is the number till there we can find the prime numbers.

while ((factor * factor) < maxNum)

{

for (int i = 2; i < maxNum; i++) // we start our itration from number 2 not from 0 or 1 to get correct results.

{

if (numArray[i] != 0) //if a number on current array index is not zero, it is a prime or we havne’t yet checked it.

{

// we are putting zeros on all multiples of prime numbers, one by one.

if (numArray[i] != factor && (numArray[i]% factor) == 0)

{

numArray[i] = 0;

}

}

}

++factor;

}// after the loop, array will have zeros on all non prime locations and prime numbers.

}

int main ()

{

int prime_count = 0;

int64_t sum = 0;

int maxNum = 0;

int i = 0;

cout << “enter max number for array: “; // you need to test some upper limit values.

cin >> maxNum;

long *myArray = new long [maxNum];

//we fill up the array till the number we want to find the smallest positive number that is evenly divisible.

for (int i = 0; i < maxNum; i++)

{

myArray[i]= i;

}

// we will get prime numbers till the maxNum by calling below funtions.

find_prime(myArray, maxNum);

for (int j = 0; j< maxNum; j++)

{

sum += myArray[j];

}

cout << “Sum of first ” << maxNum << ” prime numbers : ” << sum << endl;

}

###### Related articles

- Project Euler Problem#7 solution in C++ (Brute Force) (alikhuram.wordpress.com)
- Implementing the Sieve of Eratosthenes with Functional Programming (raganwald.com)
- Simple prime sieve in C (houstin.wordpress.com)
- Prime numbers (haskell.org)
- Quadratic Sieve (programmingpraxis.com)
- Project Euler problem#9 solution in C++ (alikhuram.wordpress.com)
- New prime-generating algorithm (cp4space.wordpress.com)