Programming

Chinese Remainder Theorem Calculator

 Chinese Remainder Theorem example

A system of three congruences is shown on the right, but start with the simpler system:
\[ \begin{align*}
x &\equiv 1 \hspace{-.6em} {\pmod{2}}\\
x &\equiv 2 \hspace{-.6em} {\pmod{3}}.
\end{align*} \]
Values congruent \( \text{mod} \; 6 \) are certainly congruent \( \text{mod} \; 2 \) and \( \text{mod} \; 3, \) so in looking for an \( x \) solving both congruences simultaneously, it suffices to consider congruence classes \( \text{mod} \; 6 \) and in particular their smallest positive residues, namely \( 0, 1, 2, 3, 4, 5. \) We're seeking an odd number among those \( 6 \) since \( x \equiv 1{\pmod{2}}, \) one that is also congruent to \( 2 \; \text{mod} \; 3. \) \( x = 1 \) won't do, since \( 1 \equiv 1{\pmod{3}} \) neither will \( x = 3, \) since \( 3 \equiv 0{\pmod{3}}. \) \( x = 5 \) is the solution, since it satisfies both congruences, and it is the only solution \( \text{mod} \; 6. \)

Fermat Sum of Two Squares Calculator

 Sums of two squares
Integers under \( 40 \) that are the sum of two squares. \( \color{red}{25} \) is the first that is the sum of two squares in two ways.

\( 5 = 1^2 + 2^2 \) is the sum of two squares, \( 3 \) is not. Dealing with whole numbers only, including \( 0, \) it's a bit of a riddle coming up with the criterion distinguishing the two situations. Based on empirical investigations, mathematicians in the \( 17^\text{th} \) century found the key. According to Leonard Dickson[1]:

A. Girard (Dec 9, 1632) had already made a determination of the numbers expressible as a sum of two integral squares: every square, every prime \( 4n + 1, \) a product formed of such numbers, and the double of one of the foregoing.

The part about primes \( p \equiv 1 \; (\text{mod} \; 4) \) is central, because a product of two numbers each of which is the sum of two squares is itself the sum of two squares. Since \( 5 = 1^2 + 2^2 \) and \( 13 = 2^2 + 3^2, \) for example, \( 65 = 5 \cdot 13 \) is also the sum of two squares: \( 65 = 4^2 + 7^2. \) In fact there is a second representation: \( 65 = 1^2 + 8^2, \) and the number of representations is of interest too (this exact example is from Diophantus).

Invariant Factor and Elementary Divisor Calculator

 All Abelian groups of order 72
All Abelian groups of order 72.

The Fundamental Theorem of Finite Abelian Groups decisively characterizes the Abelian finite groups of a given order. Its remote origins go back to Gauss in the Disquisitiones Arithmeticae in 1801 and it was nailed down by Schering (1869) and by Frobenius and Stickelberger (1879)[1]:

Fundamental Theorem of Finite Abelian Groups

Let \( G \) be a finite Abelian Group of order \( n. \) Then: \[ \begin{equation}{G \cong \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \cdots \times \mathbb{Z}_{n_s},} \tag{1} \end{equation} \] where \( s \) and the \( n_i \) are the unique integers satisfying \( s \geq 1, n_i \geq 2 \) for all \( i, \) and \( n_{i+1} \; | \; n_i \) for \( 1 \leq i \leq s - 1. \) And also: \[ \begin{equation}{G \cong \mathbb{Z}_{p^{\beta_1}} \times \cdots \times \mathbb{Z}_{p^{\beta_t}} \times \cdots \times \mathbb{Z}_{q^{\gamma_1}} \times \cdots \times \mathbb{Z}_{q^{\gamma_u}},} \tag{2} \end{equation} \] for \( p \) and \( q \) and all the other primes dividing \( n, \) again in a unique way, where \( \sum \beta_i \) is the exponent of the greatest power of \( p \) dividing \( n, \) \( \sum \gamma_i \) is the exponent of the greatest power of \( q \) dividing \( n, \) and so on for all the other primes dividing \( n. \)

Bernstein Proves the Weierstrass Approximation Theorem

 Sergei Bernstein
Sergei Bernstein.

In 1912 Sergei Bernstein introduced his famous polynomials to prove the Weierstrass Approximation theorem:

If \( F(x) \) is any continuous function in the interval [0,1], it is always possible, regardless how small \( \varepsilon \), to determine a polynomial \( E_n(x) = {a_0 x^n + a_1 x^{n-1} + \cdots + a_n} \) of degree \( n \) high enough such that we have \[ {|F(x) - E_n(x)|} < \varepsilon \] for every point in the interval under consideration.

Weierstrass proved the theorem originally in 1885[1], the very man who had earlier shown how wild a continuous function can be and in particular, how far from being smooth and subject to a Taylor expansion. Bernstein's proof was simple and based on probability theory. Maven Philip J. Davis says that "while [Bernstein's proof] is not the simplest conceptually, it is easily the most elegant".[2]

Rigid Motions of the Dodecahedron

 Escher's Reptiles

Think of a square in the plane and how it can be rotated around its center to coincide with its original position. There are four rotations altogether — 90°, 180°, 270°, and 360° clockwise, the last bringing the square back to its original configuration. You wouldn't even know the square had been moved unless the corners were somehow distinguished. Starting at the upper left, number the corners 1, 2, 3, 4 in clockwise fashion in order to track the rotations, so that a 90° rotation is identified with the cyclic permutation \( (1 2 3 4) \). In essence, you're rotating around a z axis perpendicular to the plane through the center of the square. You can also rotate around an x, or horizontal, axis through the center of the square. The square comes out of the plane, but is pinned at the middles of the left and right edges as it rotates around that axis through space by 180° — the result is the same whichever way the rotation proceeds, the permutation \( (1 4) (2 3) \). There is a similar vertical rotation, and rotations around each diagonal. These eight rotations form a group, the rigid motions of the square, and the same can be done for any regular polygon. These are the dihedral groups, \( D_4 \) in the case of the square. \( D_n \) has \( 2n \) elements and these groups are nice concrete examples of finite groups.

Starting with three.js

 3D cube

3D graphics is an inherently difficult subject, but less so with the advent of three.js, a lightweight, open source Javascript library for 3D graphics widely supported in modern browsers. It is as easy as possible, while still doing the job. Basic information can be found on the Wikipedia page, including its connection with WebGL, a standard itself based on OpenGL. WebGL goes back to 2011 and is now supported in all modern browsers. My first experiments worked fine in Chrome, but not Firefox v 12 or Internet Explorer v 10 (years out of date, I don't use them much). No problem — update to Firefox v 34 and Internet Explorer v 11 and all works fine. Check here for browser compatibility.

This might be big. Who thought 3D would come to the masses through Javascript and the browser? The beauty of that approach is its universality and device independence. Evidently WebGL taps the GPU directly for help with intensive processing tasks, and 3D graphics can be very demanding, a social as well as technical bottleneck until now, such problems dissolving before our eyes with the ongoing march of desktop and even mobile processing power and libraries like this. It should be mentioned that three.js is a port from the most impressive ActionScript, the Flash technology now on the wane that looked a lot like Javascript.

Tutorial: Assembly District in Google Maps

 University of Wisconsin - Madison

There are two ways to embed a Google map in a web page. One is Google Static Maps, which simply requires building a URL with appropriate settings, like where the map is to be centered and how big you want it to be. Below is an example of such a URL with "get parameters", the part after the question mark (multiple parameters are separated by ampersands). Copy and paste the URL into a separate browser instance or tab to see the map in your browser, much like a specific image on a server somewhere, except that it is actually a program on Google servers that is being called and they build a bitmap for you depending on the parameters.

Keep Away Game in HTML5 Canvas

 Keep Away Game
Expand to entire article to play.

The Keep Away game was the last assignment in my Flash class and this is the port to HTML5 canvas, programmed in Javascript. Flash is declining for a number of reasons, including its proprietary nature and that it's not supported by the iPhone. Too bad, because Flash's ActionScript 3.0 is a thoroughgoing object oriented approach to graphics programming similar to Javascript. For the programmer, a circle or rectangle or any other figure suitable to be part of a display list is just an object with properties and methods. Many artists know Flash through the sophisticated Flash Pro environment, where they can create and store images efficiently with "symbols". Think Adobe Photoshop, apt in a couple ways considering that Adobe acquired Flash and developed ActionScript 3.0. Even animations are possible with "tweens". It's a nice in-between technology, where artists can experience Flash as as they always do, but be gently introduced to programming those objects in the code window. My approach is to forgo the environment entirely, except as a medium to execute ActionScript. The environment can be skipped entirely with Abobe's free compiler which turns ActionScript into .swf, which executes in the (free) Flash Player.

Tutorial: HTML5 Canvas Demo in Drupal

The image of the Old Glory below was created with HTML5 canvas and there are a few tricks involved in getting it to work with Drupal 7. The first step is to get the HTML5 doctype at the top of all your Drupal pages. You can modify html.tpl.php, the template determining this, but careful if you do, and maybe the simplest approach is to install the Elements and HTML5 Tools modules. Before enabling those modules, viewing the page source shows doctype references to xhtml, afterwards it does not. Don't forget to clear the cache after enabling the modules and before viewing the source if you want to check (Configuration > Performance > Clear all caches). Then this HTML/CSS puts the rectangle at the upper right:

 <div id="canvasContainer" style="float:right; border:1px solid black; margin:0 0 15px 15px">
  <canvas id="flag" width="296" height="156"></canvas>
 </div>

Teaching at MATC

 MATC circa 1912

After driving truck for eleven years, it was time for a change. Education was important in my household coming up. I have a Latin book from a great-great-grandfather on Mom's side. Half of Mom's family were teachers, including her parents for brief stints as young people in Iowa - two of my first cousins became Math and Computer Science professors in Canada. Mom did her entire high school through correspondence on the plains of Saskatchewan; she said trig just about sunk her. Dad too, where education was seen as a deliverance from poverty. He was an engineering student at the University of Manitoba and struggled through school for many years, having to support himself from a very young age. Struggled academically too, but was in awe of mathematics. I told him once as a kid I wanted to be an engineer like him; he said, oh no, shoot higher - go for mathematics. I still have his calculus book and gave his rebound copy of Men of Mathematics to my daughter Lydia when she graduated with a major in mathematics. On occasion I'd get some recognition at school, the honor roll or something, and would throw it aside as of little interest. Later it would appear framed and on the wall in Dad's home office. I essentially ended up teaching software engineering, that was typically my job title when working in the field; I think he would've been Ok with that.

Pages

Subscribe to RSS - Programming