Every non-negative binary number (base 2) has a corresponding decimal (base 10) expansion form. Consider a binary number with \( n \) bits, \( b_{n-1} \cdots b_1 b_0 \). This can be written in decimal as a sum of products:

$$ (b_{n-1} \cdot 2^{n-1}) + \cdots + (b_1 \cdot 2^1) + (b_0 \cdot 2^0) $$

As you can see, for every binary digit that is 1 we will add a power of 2 to the decimal representation. The power of 2 to be added corresponds to the placement of the binary digit (indexed from 0, starting on the right). If a binary digit is 0, then it will zero out its corresponding power of two, contributing nothing to the decimal expansion.

If you consider each product in the sum to be a component corresponding to a bit, then:

- The the left hand side of the product represents the value of the bit (0 or 1).
- The right hand side of the product (the power of 2) represents the digit placement of the bit.

Consider the binary number \( 110 \). This expands to:

$$ (1 \cdot 2^2) + (1 \cdot 2^1) + (0 \cdot 2^0) = 4 + 2 + 0 = 6 $$

Check out the following site if you're unfamiliar with how to convert decimal numbers to their binary representation: http://www.wikihow.com/Convert-from-Decimal-to-Binary

The link above shows two different methods for performing the conversion. The first method is analogous to the standard algorithm. The second method is one that may be quicker if performing the conversion by hand (e.g., on an exam) because it doesn't involve division.

Let's assume you have an int called, "result," and you have a way of determining what a bit in its binary representation looks like. Now, suppose you want to toggle the bit at index \( i \) in order to change the value of result.

- If \( b_i = 0 \), then to make it \( 1 \), you should add \( 2^i \) to result.
- If \( b_i = 1 \), then to make it \( 0 \), you should subtract \( 2^i \) from result.

Hopefully this is obvious based on how the decimal expansion, explained earlier, works.

In order to toggle a binary bit, you need to first know if the bit is 0 or 1. To figure this out, we can utilize shifting (which will covered in more detail below). Let's assume you have an int called, "result," and you have access to its binary digits. Now, suppose you want to determine if the bit at index \( i \) is equal to 1 (sometimes we say that the bit is set if it's equal to 1).

The basic idea is that you shift the binary representation of the number to the right by \( i \) places, then check to see if the shifted number is odd. This works because the bit we want to check will end up being the first bit on the right after the shift. If the bit is 1, then the shifted number will be odd. If the bit is 0, then the shifted number will be even. This should make sense of you examine the decimal expansion of the shifted number.

Here is an example implementation:

boolean isSet(int number, int i) { return (number >> i) % 2 == 1; } // isSet

The left shift (<<) and right shift (>>) operators take an integer in its decimal representation, shift the bits in the integer's binary representation, then return the shifted integer in its decimal form. If a bit in the binary representation gets shifted off the edge in either direction, it's lost. Consider the integer \( 6 \) which has a binary representation of \( 110 \).

Shifting to the left shifts the bits to the left:

6 << 1 // 1100 equals 12 6 << 2 // 11000 equals 24 6 << 3 // 110000 equals 48

Shifting to the right shifts the bits to the right:

6 >> 1 // 11 equals 3 6 >> 2 // 1 equals 1 6 >> 3 // 0 equals 0

t should be noted that performing a left shift (<<) by \( i \) places is equivalent to multiplying the original number by \( 2^i \). Also, performing a right shift (>>) by \( i \) places is equivalent to dividing the original number by \( 2^i \) (integer division). This can be seen in the examples above, but can also be proved by examining the decimal expansion.

Consider a number result with a binary representation containing \( n \) bits, \( b_{n-1} \cdots b_1 b_0 \). This can be written as:

result = \( (b_{n-1} \cdot 2^{n-1}) + \cdots + (b_1 \cdot 2^1) + (b_0 \cdot 2^0) \)

Now suppose we shift result to the left by \( i \) places. The binary expansion of this shifted number can be written as:

result << i = \( (b_{n-1} \cdot 2^{n-1+i}) + \cdots + (b_1 \cdot 2^{1+i}) + (b_0 \cdot 2^{0+i}) \)

To see how this works, consider the bit bj in the original number. Its contribution to the original decimal expansion is \( (b_j \cdot 2^j) \). If we were to shift it to the left by \( i \) places then we need to add \( i \) to its digit placement (its power of 2). This gives us \( (b_j \cdot 2^{j+i}) \) which can also be written as \( (b_j \cdot 2^j \cdot 2^i) \). It therefore follows that:

result << i = \( (b_{n-1} \cdot 2^{n-1+i}) + \cdots + (b_1 \cdot 2^{1+i}) + (b_0 \cdot 2^{0+i}) \)

result << i = \( (b_{n-1} \cdot 2^{n-1} \cdot 2^i) + \cdots + (b_1 \cdot 2^{1} \cdot 2^i) + (b_0 \cdot 2^{0} \cdot 2^i) \)

result << i = \( 2^i \cdot [ (b_{n-1} \cdot 2^{n-1}) + \cdots + (b_1 \cdot 2^{1}) + (b_0 \cdot 2^{0}) ] \)

result << i = \( 2^i \cdot \) result

Therefore:

result << i = \( 2^i \cdot \) result

A similar result can be shown for proving right shift is equivalent to dividing by a power of 2 by considering anything smaller than \( 2^0 \) to be 0.

*The cover image for this post is used under a CC BY-SA 2.0 license as described by its copyright holder @mcclanahoochie.*

package com.michaelcotterell.math; import static java.lang.Math.abs; import java.util.function.Function; /** * A function that maps Real values to Real values. Here, the term "Real" is * equivalent to <code>double</code>. This functional interface allows users to * easily take derivatives and find zeros of the function using established * techniques. * * <p> * This interface is intended to be used with lambda expressions in order to * provide easy access to it's default methods. * * @author Michael E. Cotterell <mepcotterell@gmail.com> */ @FunctionalInterface public interface RealFunction extends Function<Double, Double> { /** The value used for determining if two <code>double</code> values are essentially equal. */ public static final double EPSILON = 1E-11; /** The half-width uses for two-sided differentiation. */ public static final double H = EPSILON; /** * Estimate the derivative of the function at <code>x</code> using a * two-sided method (central difference). * * @param x the point at which to estimate the derivative * @return derivative of the function evaluated at <code>x</code> (estimate) */ default double derivative(double x) { return derivative().apply(x); } // derivative /** * Returns the first derivative of the function. * * @return first derivative */ default RealFunction derivative() { return x -> (apply(x + H) - apply(x - H)) / ((x + H) - (x - H)); } // derivative /** * Find the root (zero ) of this {@link com.michaelcotterell.math.RealFunction} * using Newton's method, given a <code>guess</code> of where the root is. * This implementation of Newton's method finds an approximation to the * root of the function using enough consecutive terms of the function's * Taylor series such that the value of the function at the estimated root * is essentially zero using {@link com.michaelcotterell.math.Constants#EPSILON}. * * @param guess a guess of where the root is * @return the root of the function, using Newton's method */ default double zero(double guess) { double x = guess; while (abs(apply(x)) > EPSILON) x = x - apply(x) / derivative(x); return x; } // newtonZero /** * Find the root (zero ) of this {@link com.michaelcotterell.math.RealFunction} * using Newton's method. This implementation of Newton's method finds an * approximation to the root of the function using enough consecutive terms * of the function's Taylor series such that the value of the function at * the estimated root is essentially zero using * {@link com.michaelcotterell.math.Constants#EPSILON}. * * <p> * This particular method sets the initial guess of where the root is to 10. * * @return the root of the function, using Newton's method */ default double zero() { return zero(10); } // newtonZero } // RealFunction

With this functional interface, we can take derivatives of functions expressed as lambda expressions:

RealFunction f = x -> x * x; RealFunction df = f.derivative(); System.out.println(df.apply(4.0)); // ~ 8.0 System.out.println(df.apply(4.5)); // ~ 9.0

Here is a neat implementation of finding the positive square root of a number using Newton's method (as implemented by the default method zero in the interface):

/** * Return the positive square root of <code>n</code> using Newton's method. * * @param n a value * @return the positive square root of <code>n</code> */ public static double sqrt(double n) { RealFunction f = x -> x * x - n; // the square root function double guess = 0.3 * n; // arbitrary starting place; seemed good return f.zero(guess); } // sqrt]]>

Here is a Java 8 stream-based implementation of a pseudo-random number generator using a linear congruential generator (LCG):

package com.michaelcotterell.util; import java.util.stream.DoubleStream; import java.util.stream.IntStream; import java.util.stream.LongStream; public class Random { private final long a; // multiplier private final long c; // increment private final long m; // modulus private final long seed; // start value private final LongStream stream; public Random(long a, long c, long m, long seed) { this.a = a; this.c = c; this.m = m; this.seed = seed % m; this.stream = LongStream.iterate(this.seed, x -> (a * x + c) % m); } // Random public Random(long a, long c, long m) { this(a, c, m, System.currentTimeMillis()); } // Random public LongStream longs() { return stream.map(e -> e); } // longs public IntStream ints() { return stream.mapToInt(e -> (int) (e % (Integer.MAX_VALUE + 1L))); } // ints public DoubleStream doubles() { final double ONE_OVER_M = 1.0 / m; return stream.mapToDouble(e -> e * ONE_OVER_M); } // doubles } // Random

To use this class, you might do something like the following:

Random lcg = new Random(48271, 0, (2L << 31) - 1, System.currentTimeMillis()); Iterator<Double> rand = lcg.doubles().iterator(); for (int i = 0; i < 10; ++i) System.out.println(rand.next());

To test different LCGs, you might do the following:

long iters = 100_000; long seed = System.currentTimeMillis(); Random[] lcgs = new Random[] { new Random(48271, 0, (2L << 31) - 1, seed), // MINSTD (updated) new Random(16807, 0, (2L << 31) - 1, seed), // MINSTD (old) new Random(65539, 0, (2L << 31), seed) // RANDU }; for (Random lcg : lcgs) { System.out.println(lcg.doubles().limit(iters).summaryStatistics()); } // for]]>

A purely tail recursive function or method is one in which there are no deferred operations. A deferred operation in this case, is one that must wait until a recursive call returns before it can complete. This article goes into this a little detail about the differences between "ordinary" and "pure" tail recursive methods.

Given a function that can swap two elements of an array and the partition function, it is possible to find the k-th smallest element of an array of distinct integers using the following purely tail recursive implementation (the accumulator parameters act in a fashion that is similar to a binary search):

private static int kthMin(int[] a,intleft,intright,intk) {intnewPivot =partition(a, left, right, k - 1); if (newPivot == k - 1)returna[k - 1]; if (newPivot < k - 1) left = newPivot + 1; if (newPivot > k - 1) right = newPivot - 1; returnkthMin(a, left, right, k); } // kthMin

If you have any questions, then please post them in the comments.

]]>[In] gaming [,...] a model is constructed that is an abstract and simplified representation of the real environment. This model provides a responsive mechanism to evaluate the effectiveness of proposed alternatives, which the decision-maker must supply in an organized and sequential fashion. The model is simply a device that allows the decision-maker to test the performance of the various alternatives that seem worthwhile to pursue.

v.s.

]]>Simulation models are similar to gaming models except that all human decision-makers are removed from the modeling process. The model provides the means to evaluate the performance of a number of alternatives, supplied externally to the model by the decision-maker, without allowing for human interactions at intermediate stages of the model computation.

$$ \left( n;~ k_1, \dots, k_m \right) ~\mbox{where}~ k_m = n - \sum_{i=1}^{m-1} k_i \equiv {n \choose k_1, \dots, k_{m-1}} $$

For convenience, I'm going to use the first notation.

I'm not sure if this has ever been stated before, but here's an observation that I made a couple months ago:

$$ \left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \frac{1}{k_m !} \prod_{i=1}^{k_m} n-i+1 $$

That is, there exists a linear, tail recursive definition for calculating multinomial coefficients.

Without loss of generality, assume that \( n = \sum_{i=1}^{m} k_i \). According to the equivalence noted above as well as the Multinomial Theorem, we have:

$$ \left( n;~ k_1, \dots, k_m \right) = {n \choose k_1, \dots, k_m} = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_m ! } $$

(1) If we pull out the term \( k_m \), we get:

$$ \left( n;~ k_1, \dots, k_m \right) = \frac{1}{k_m !} \cdot \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } $$

(2) Now, let's find some \( \zeta \) such that:

$$ \frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \zeta = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } $$

(3) If we isolate \( \zeta \) on the left-hand side, we observe the following:

$$ \zeta = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \frac{ k_1 ! \cdot \cdots \cdot k_{m-1} ! }{ (n-k_m)! } = \frac{ n! }{ (n-k_m)! }$$

(4) We know that certain terms cancel in this fraction. It is easy to see that

$$ \zeta = \frac{ n! }{ (n-k_m)! } = (n - k_m + 1) \cdot (n - k_m + 2) \cdot \cdots \cdot n = \prod_{i=1}^{k_m} n - k_m + i $$

(5) Since the product in \( \zeta \) is from \( 1 \) to \( k_m \), we can be further simplify the expression to

$$ \zeta = \prod_{i=1}^{k_m} n - k_m + i = \prod_{i=1}^{k_m} n-i+1 $$

(6) Replacing \( \zeta \) in (2) gives us the following:

$$ \frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \prod_{i=1}^{k_m} n-i+1 = \frac{ n! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } $$

(7) Now we use the result of (6) with (1) to get:

$$ \left( n;~ k_1, \dots, k_m \right) = \frac{1}{k_m !} \cdot \frac{ (n-k_m)! }{ k_1 ! \cdot \cdots \cdot k_{m-1} ! } \cdot \prod_{i=1}^{k_m} n-i+1 $$

(8) Since the second fraction in (7) can be expressed as a multinomial, we have:

$$ \left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \frac{1}{k_m !} \prod_{i=1}^{k_m} n-i+1 $$

Therefore, the theorem is correct.

This result that we observed in (7) directly relates to the ratios between the coefficients on the face of a multidimensional Pascal triangle.

It is easy to see that the following follows from the theorem:

$$ \left( n;~ k_1, \dots, k_m \right) = \left( n-k_m;~ k_1, \dots, k_{m-1} \right) \cdot \prod_{i=1}^{k_m} \frac{n-i+1}{i} $$

In Scala, the expression in the corollary can be expressed concisely using the foldLeft operator.This operator applies a binary operator to a start value and all elements of a list, going left to right. If we let our list be the numbers \( 1, \dots, k_m \), then we can foldLeft with the following binary operator:

$$ \left(a,b\right) \Rightarrow \frac{a \left(k_m-b+1\right)}{b} $$

For more information on the general fold operator (with which you can pretty much do anything with), see "Introduction to Metamathematics" by Kleene (affiliate link).

Here is my recursive implementation of the recurrence relation mentioned in the corollary above:

I've omitted a an iterative implementation of the corollary that I've written for the sake of brevity. If anyone expresses some interest, I may include here or in a future blog post.

object Combinatorics {]]>

/** Computes the multinomial coefficient (n; k_1, .., k_m)

* where n = the sum of k_1, .., k_m.

*

* This is a variadic convenience function that allows

* someone to invoke <code>multi</code> without using an

* array. Note, however, that the variadic parameter is

* transformed into an array when this version of

* <code>multi</code> is invoked.

*

* @author Michael E. Cotterell <mepcotterell@gmail.com>

* @param k items to choose

*/

def multi (k: Int*): Long = multi(k.toArray)

/** Computes the multinomial coefficient (n; k_1, .., k_m)

* where n = the sum of k_1, .., k_m.

*

* This implementation requires exactly n-many

* multiplications and m-many recursive calls.

*

* @see http://michaelcotterell.com/2013/03/multinomial-coefficients/

* @author Michael E. Cotterell <mepcotterell@gmail.com>

* @param k items to choose

*/

def multi (k: Array[Int]): Long =

{

if (k.length == 1) 1L

else {

(1 to k.last).foldLeft(multi(k.slice(0, k.length - 1))){

(prev, i) => prev * (k.sum - i + 1) / i

}

} // if

} // multi

/** Computes the multinomial coefficient (n; k_1, .., k_m)

* where n = the sum of k_1, .., k_m.

*

* This implementation requires exactly n-many

* multiplications and m-many recursive calls. Also, it is

* experimentally slower than the <code>foldLeft</code>

* implementation provided by the <code>multi</code>

* function.

*

* @see http://michaelcotterell.com/2013/03/multinomial-coefficients/

* @author Michael E. Cotterell <mepcotterell@gmail.com>

* @param k items to choose

*/

def _multi (k: Array[Int]): Long =

{

if (k.length == 1) 1L

else {

var product = _multi(k.slice(0, k.length-1))

for(i <- 1 to k.last) product = product * (k.sum-i+1) / i

product

} // if

} // _multi

} // Combinatorics

Since the definition of a 3 digit number seems to depend on who you're talking too, I always make sure to mention that the code can be easily modified to only work with true 3 digit numbers. Also, since Scala is my favorite language, here is the same code converted to Scala.

Another interesting approach is to enumerate all 3 digit numbers and use what I call the modulus technique to get the digits for each (mod 10 to get the last digit, divide by 10 to decrease the number by one digit, repeat). I suspected (correctly) that some of my students would think of this method because it's very similar to a lab in the prerequisite course.

If you know any other method to enumerate Armstrong numbers then please post it in the comments.

]]>Now, I took it a step further and created a small DSL (Domain-Specific Language) that adds shuffling directly to ranges in Scala. This allows me to do the following:

It's pretty straightforward to setup if you're even a little acquainted with implicit conversions. Here are the other two files that make it all work:

A commenter named Martin (Martin Odersky?) commented that since the "foreach" method takes a function of arity 1, we can use `foreach println`

, which is just syntactic sugar for `foreach (x => println(x))`

. Here is the example that he provided:

Referential Transparency:A function in a program is referentially transparent (has no side effects) if it can be replaced with its evaluation without changing the effect of the program.

What if referential transparency can be applied to more than just programming? Specifically, what if it could be applied to research paper writing? I think that there is some practical application to this thought process. Although the idea of research papers is not just to convey results but to also provide enough information to support one's claim. The idea of making papers referentially transparent is a convenient way to make sure that your writing is concise and to the point. In fact, many of the problems that are encountered in both paper writing and dissemination also occur in programming. Mainly, in this case, I consider the following:

- Make it clear and to the point.
- Provide enough context so that the statements make sense.
- Stay in scope.

If we break up the statements that are to be conveyed and express them as functions then all of the supporting statements should be their own atomic functions as well. Referential transparency comes into place when you consider that the information being conveyed by the greater function should be able to stand on its own. That is, if we assume that the persons reading the greater statement already knows the supporting information then effect of ignoring the supporting statements should be the same as if they were read.

**Note:** Now if only I can apply this sort of thinking to my blog posts as well.

Work is cool. Besides that, my friends and I have been able to see some of the sites. Here's me and my buddies near Chautauqua. The view is great!

]]>```
-a -b -c -d
+a -b -c -d
-a +b -c -d
+a +b -c -d
-a -b +c -d
+a -b +c -d
-a +b +c -d
+a +b +c -d
-a -b -c +d
+a -b -c +d
-a +b -c +d
+a +b -c +d
-a -b +c +d
+a -b +c +d
-a +b +c +d
+a +b +c +d
```

Also, please note that this is probably, by no means, the most functional way to do this. It was merely an attempt at hacking together some code that just gets the job done. If I have time, I will write up some posts on functional ways to produce both combinations and permutations in Scala.]]>- Java: 5,625
- Freemarker Templates & HTML: 1,079
- CSS: 665
- XML: 1,892

Here are some screenshots, for the curious: The entire software development process (a modified version of the Waterfall model) was followed in the creation of this software system. The result is a system that I, as the Team Technical Editor, can say with confidence fulfills the functional and non-functional requirements presented to us at the beginning of the semester.

I would like to thank the entire Carrello development team: Mehdi Allahyari (Project Manager & Developer), Usman Nisar (Concept Modeler & Developer), and Haseeb Yousaf (Persistence Engineer & Developer). It has been an amazing semester! The experience we've gained and the teamwork we've demonstrated will definitely serve us well in the future.

]]>In order to fix the problem, I tried changing the context bound to a view bound. Viola, it worked!

In the following code, the commented out line will not compile. MyNumContainerB is able to hold both built-in and user-derived Numeric types.

error: ambiguous implicit values: both method stringCanBuildFrom in object Predef of type => scala.collection.generic.CanBuildFrom[String,Char,String] and method conforms in object Predef of type [A]=> <:<[A,A] match expected type

val d = new MyNumContainerA(c)

I'm still trying to figure out why a context bound doesn't work. Perhaps there is a lack of implicit evidence somewhere? Anyway, some more investigation is needed. If anyone knows why this happening then please let me know!

]]>