Table of Contents

• Number Systems and Representations
• Continued Fraction Representations
• Convergents of Continued Fractions
• Example: Continued Fraction Coefficients of \(\sqrt{14}\)
• Example: Convergents of \(\sqrt{14}\)
• Approximating Square Roots

Continued Fractions

Let's start part 2 of our discussion of computing square roots by talking about continued fractions. When we first learn mathematics, we learn to count in the base 10 system: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. We can construct representations of all of the integers using these 10 digits, by arranging them in a different order. So, for example, saying 125 is equivalent to saying …

Table of Contents

• Newton's Method for Finding Roots of Equations

• Newton's Method for Finding Square Roots

• Newton's Method for Finding Square Roots: Program

• Accuracy

• Speed

• Next Steps

• References

Newton's Method for Finding Roots of Equations

Suppose we have a function \(f(x)\) and we want to compute values of \(x\) for which \(f(x)=0\). These values of \(x\) are called the roots of \(f(x)\).

We can compute the roots using Newton's Method, which utilizes the derivative of the function to iteratively compute the roots of the function.

Newton's method begins with an initial guess. It evaluates the derivative …

Table of Contents

This is the third in a series of three posts detailing the Hilbert Sort problem, its solution, and its implementation. This post deals with the code to solve the Hilbert Sort problem.

• Pseudocode

• Code

  • Utility Classes
  • Recursive Sort Function
  • Main Method

• References

Hilbert Sort: Pseudocode

From our prior post, here is the psudocode for our Hilbert Sort function:

define hilbert_sort( unsorted queue, square dimension ):
    create southwest queue
    create northwest queue
    create northeast queue
    create southeast queue
    for each point:
        if in southwest:
            create new point using X -> Y, Y -> X
            add to southwest queue
        if in …

Table of Contents:

• A Gentle Introduction to Recursion

• Recursive Backtracking

• Paring Down the Decision Tree

• The Pseudocode

• Accounting for Diagonal Attacks

• Why the N Queens Problem?

A Gentle Introduction to Recursion

Recursion, particularly recursive backtracking, is far and away the most challenging topic I cover when I teach the CSE 143 (Java Programming II) course at South Seattle College. Teaching the concept of recursion, on its own, is challenging: the concept is a hard one to encounter in everyday life, making it unfamiliar, and that creates a lot of friction when students try to understand how to apply recursion.

The …

Table of Contents

• Background
• N Queens Revisited
• Perl Solution
• Python Solution
• Python vs. Perl: Walltime vs. Number of Queens
• Perl Profiling and Results
• Python Profiling
• Python Profiling Results
• Comparing Python to Perl
• Python vs. Perl: Walltime vs. Number of Solutions Tested
• The Winner: Perl for Small Problems, Python for Big Ones
• Sources

Background

Revisiting the N queens problem, this time implementing the solution in Python.

Verb-oriented solution, functional, and based on Perl solution

More fair comparison - both are interpreted languages, not compiled languages

Compare Python and Perl, ease of implementation, speed, flexibility

N Queens Problem

As a recap from the …

Table of Contents

• Background: Huh?
• N Queens Problem
• N Queens Solution
  • Perl Solution
  • Java Solution
• Head to Head: Walltime vs. Number of Queens
• Perl Profiling
• Perl Profiling Results
• Java Profiling
• Java Profiling Results
• Head to Head: Walltime vs. Number of Solutions Tested
• Apples and Oranges
• Sources

Summary

In this post, we describe an implementation of the N Queens Problem, which is a puzzle related to optimization, combinatorics, and recursive backtracking. The puzzle asks: how many configurations are there for placing 8 queens on a chessboard such that no queen can attack any othr queen?

This problem was implemented in Perl …

In this, the fourth article in a series on implementing the Enigma cipher in Java, we use some big number libraries to explore the combinatorics of the Enigma encryption scheme and better understand the Enigma's strengths and weaknesses.

Table of Contents

• The Key Space
• The Switchboard
  • One Cable
  • More Cables
  • Many Cables
  • Accounting for Duplicates
  • Final Combination Count for Switchboard
• The Rotors
  • Final Combination Count for Rotors
• The Reflector
  • Final Combination Count for Reflector
• Final Enigma Combination Count
  • Java BigInteger Combinations Program
• Sources

The Key Space

Basically, what the Enigma did was to encrypt each character of a message one …

As the title suggests, we're continuing with the third in a series of posts exploring a verb-oriented approach to programming - in an attempt to free ourselves from the fetishization of objects, we are attempting to learn how to use languages against their will.

This is all inspired by Steve Yegge's 2006 blog post, "Execution in the Kingdom of Nouns," an excellent read that inspired me to explore the subject more deeply.

Java Pseudocode

In the last post, we ran through the pseudocode for an Enigma machine based entirely upon Strings, iterators, and integer indexes, leading to a vastly simpler abstraction …