The Euclidean Algorithm recursively calculates the greatest common divisor (GCD) of two integers. It works because GCD(a,b) = GCD(a mod b, b) = GCD(b, a mod b). Each step of the algorithm reduces the size of the numbers by about a factor of 2. The total number of steps required is roughly log(a*b). It is …

# Monthly Archive: July 2016

Jul 20

## Calculating Fibonacci Numbers

The following C++ code calculates the Nth number in the Fibonacci sequence. The first routine recursively calculates F_n, however it is very inefficient and takes an unrealistic amount of time to calculate even moderately high values for F_n (say 100). The second routine generates the sequence sequentially on the fly up to F_n, and is …

Jul 11

## References and Pointers (C++)

Inspired by C++ Primer, Fifth Edition A reference refers to (is another name for) another object. Any operation on the reference actually operates on the object to which the reference is bounded. A pointer is an object itself (unlike a reference) and “points to” another object. Pointers can have four states: 1) It can point …

## Recent Comments