var forEach = new TransformManyBlock<IEnumerable<int>, int>(x => x);
Saturday, October 03, 2015
Saturday, May 17, 2014
Geostationary
Earth's standard gravitational parameter is its mass M x G (the gravitational constant), which is roughly μ = 398,600.4418. The standard gravitational parameters for planets are better known than either M or G individually (the best way we have at our disposal to weigh extremely massive objects is by observing their gravitational effect on other bodies like orbiting satellites). Acceleration due to gravity is \(\mu \over r^2\). The equatorial radius of Earth is
6,378.14 km. If we plug in that figure, we'd see acceleration on the surface is the familiar 0.009798285 km/s. 422 km above the surface (in the orbital sphere of the ISS), it's just 0.008619904 km/s (87.97%). The further out we go, the lower the acceleration and the longer the orbital period.
To find out how far away we have to place a geostationary satellite, consider that it will need to be in a circular orbit with an orbital period of one sidereal day. In one second, it will move \(7.29212 \times 10^{-5} radians\); therefore \(r \times (1 - cos(7.29212 \times 10^{-5}))\) will be the distance that it falls towards the Earth in that time. We know from the SUVAT equation \(s = ut + {1 \over 2}at^2\) that in a second, with no initial velocity, that the distance travelled is half the acceleration. We now have an identity \(r (1 - \cos(7.29212 \times 10^{-5})) = {\mu \over r^2}\). Rearrange it and solve: \[r = \sqrt[3]{\mu \over {2 - 2 cos(7.29212 \times 10^{-5})}}\] It turns out that the altitude of 42164.15974 km above the center of the Earth (35786.02274 km above the equatorial surface) is where you'll find geostationary satellites - and they can only exist in that one orbital plane.
Saturday, May 10, 2014
Gravity / ISS
On Earth's surface the acceleration due to gravity is \(9.8 m \cdot s^{-2}\). The further you go away, the lower the force of gravity. 422km above the surface we're told that the acceleration is 89% of surface gravity - it's \(8.722 m \cdot s^{-2}\).
Using the SUVAT equation \(s = ut + {1 \over 2}at^2\) we can see that an object dropped from 422km (i.e. \(g = 8.772 m \cdot s^{-2}\)) would fall 4.361m in the first second.
In the same second, we know that the ISS traces out the circular orbit (i.e. it doesn't crash into the Earth). The angular distance it travels (we could use the unit circle for visual confirmation) is \(\arccos({{r - s} \over r})\) or \(\arccos({{6806000 - 4.361} \over 6806000})\) or \(\arccos({6805995.639 \over 6806000})\) or simply 0.001132041 radians.
If it travels 0.001132041 radians in a second, it will take 5550.316851 seconds to perform a complete revolution of 2π. 5550 seconds is 92½ minutes, a figure that's very close to the published figure (on Wikipedia) and that's quite amazing given the rough estimates we've made to get this far. A circle of radius 6806km has a circumference of 13612km. Divide that circumference by the orbital period in seconds and you get \(7704 m \cdot s^{-1}\). You could also try \(r \sin(\theta)\) or \(6806000 \sin(0.001132041)\) which gives the same result. It's moving pretty quickly, but would have to be even quicker if the orbit was any closer to the surface!
Wednesday, April 16, 2014
Newtonian Reflector
Newtonian reflector telescopes use two mirrors – a figured primary mirror (the objective) which focuses incoming light, and a flat secondary mirror which redirects that light at an angle so that it can be viewed without getting your head stuck in the tube. The secondary mirror is only practically important – a CCD sensor could be placed directly into the path of the light focused by the objective mirror and it would capture the light without requiring an additional reflection. However, the subject of this post is the primary mirror, particularly: it’s shape.
A 2D parabola is defined by the quadratic equation \(y = ax^2 + bx + c\). If we make some simplifying assumptions (such as: its open side faces up; it “rests” on the x-axis; the focus is on the y-axis at height p) then our equation reduces to \(y = 4px^2\). The first order derivative (e.g. slope) of this equation is \({dy \over dx} = 2px\). That means, for a given focal length (and radius from the centre of the mirror), we can estimate the height of the reflective surface from the x-axis, as well as the slope at that point. These two computed values show where light is reflected when it encounters the surface of the objective mirror. Remember that incident light is reflected about the normal vector to the surface:
\(R = D – (2D \cdot N)N\)
To enable a 3D version (a paraboloid) we can take advantage of the knowledge that we only need rotate the parabola (i.e. the shape is rotationally symmetric about the vertical axis). In 3D, I chose to rotate around the z-axis.
It then becomes rather straight forward to take a solid angle of light, to compute the angles at which each incident ray encounters the parabolic reflector surface (parallax will affect closer light sources more than further away sources) and then note the points at which two or more rays converge to a single point. It turns out that the parabolic shape is ONLY able to focus light that is travelling parallel to the reflector’s primary axis. Closer sources converge further back than the stated focal length; sources at infinity converge exactly at the parabola’s focal point. Off-axis sources result in a complex out-of-focus shape when we attempt to capture them on a flat focal plane like a CCD. Looking at the distribution of focal points for a given field of view it was difficult to imagine a single transformation that might enable coma to be completely (and correctly) removed, though clearly a retail market for coma-correcting lenses abounds.
Thursday, January 24, 2013
Day-glo
Wednesday, October 17, 2012
Scalar
Matrices can be "multiplied" in two ways:
- two matrices are multiplied and the result is an arrangement of dot products;
- one matrix and one scalar are multiplied and every value in the matrix is scaled by the scalar.
Now, every time an algorithm requires to scale a collection of values by some number, will I name that variable "factor" or "scalar"?
Which would you choose?
Tuesday, October 09, 2012
Rectilinear
Now, imagine you're standing in the middle of a massive sphere, pointing the camera outwards. If you took a photograph, each line of pixels (up/down and left/right) would represent a curved line segment of a great circle on that sphere. And if a pixel is defined by a row and column (or X and Y value) then the position of the light source of that pixel will be the intersection of those two great circles.
Mathematically it's relatively simple to calculate the intersection point of two great circles (we only consider two points and then throw one of those away - an optimisation) and thus the position in space of the pixel's light source. We could map two or more photographs of the same scene (taken from the same place, but at different angles) onto our sphere (from the inside) and with the right manipulations, we'd be able to build a 360 degree * 180 degree panoramic view (i.e. the full sphere).
And what are the right manipulations? They involve matrices, or more specifically, singular value decompositions. If every photograph shares two overlapping points with another photograph (or photographs) then we can test our inner-sphere projection by comparing the angle between the point-pairs in one photograph with the same point-pair in another. They need to be equal angles or else something's likely wrong with our assumption of the lens projection. Given two point-pairs, it's simply a case of using Procrustes analysis (or actually, just a sub-solution of it) to determine a rotation that can be applied to all pixels of one image to align it perfectly with the other image. Once the aligned images wrap around the entire sphere, you might find that the computed scale factor obtained when calibrating the lens was slightly out. So... why bother calibrating in the first place if you already know the lens is rectilinear! Readjust the scale factor and realign the images as necessary. Then fill the remainder of the sphere with your photographs. Simples!
Saturday, March 24, 2012
West-East
Thursday, October 27, 2011
Anaglyph
When we mix 100% green with 100% blue we get cyan. A transparent sheet of cyan film therefore allows green and blue light, yet absorbs red light. If we take a digital photograph (composed of red, green and blue light) and view it through a transparent cyan film, the film absorbs the red light allowing only green and blue to pass. In theory, if I have two photographs and I remove all the red from one, then I view both through transparent cyan film, I won't be able to tell the images apart. One's image emits no red light; the other's red light is blocked by the "filter" - in neither case does any red light reach the viewer.
What if we view an image with only red through our cyan filter? There is no green and no blue light in the image, and all red light gets absorbed by the filter. The image will appear black.
LEFT RIGHT
IMAGE (red only) (green/blue only)
FILTER (red) (cyan)
EYE (left only) (right only)
Now, put on an imaginary pair of red/cyan glasses and look at two digital photographs side by side. Close your left eye (red filter) and look with your right eye (cyan filter). Remember, an image with no green or blue appears black through cyan, so we remove these colors from the left image. An image with only green and blue appears in green and blue (there's no point in having red in the image as it would be absorbed by the filter anyway - plus it would destroy what comes next). With only your right eye, the left image is black and right image is visible. Now, close your right eye (cyan filter) and look with your left eye. The right image has gone black because it doesn't have any red - the green and blue have been absorbed by the red filter. The left image springs to life now, because it has red in it. We have found a way to show each eye a different image - and our brains do the rest.
Sunday, September 18, 2011
Diskette
On my Diskette class, I would expose the following methods to modify/access state:
- bool ToggleDiskAccessSlot()
- bool ToggleWriteProtect()
- void RotateDisk(int numSectors)
- int Read(int cylinder, int side)
- void Write(int cylinder, int side, int value)
Using Roy Osherove's naming strategy (a la accepted answer to this question), I'd add a unit test class named DisketteTests. Unit tests - IMHO - are intended to ensure that public methods modify the internal state of an object as expected. A test first sets up the object under test to a known state, then invokes a method, and finally makes an assertion about the state.
I might want to test the ability to read or write while the disk access slot is closed (I'd expect some exception to be thrown, so there's no explicit calls to Assert in the method body, the assertion is made by the test framework based on the test's custom attributes):
[ExpectedException(typeof(InvalidOperationException))]
[TestMethod]
public void Read_DiskAccessSlotIsClosed_ThrowsException()
{
Diskette d = new Diskette();
// intentionally missing the step to ToggleDiskAccessSlot();
Ignore(d.Read(1, 1));
}A more standard test might look like this:
[TestMethod]
public void Read_DiskAccessSlotIsOpen_GetsCurrentValue()
{
Diskette d = new Diskette();
if (!d.ToggleDiskAccessSlot())
{
Assert.Fail("Unable to open disk access slot");
}
int value = d.Read(1, 1);
Assert.AreEqual(value, 0);
}
Saturday, September 10, 2011
Memoize
Consider this problem outlined on ROT13(Cebwrpg Rhyre). Every node in the triangle has an associated maximum cost. For the elements at the base level of the triangle, that value is the value of the element. For the element at the next highest level, the maximum cost is the value of the element itself, plus the greater value of the two elements below it. This property holds recursively throughout the entire graph, and we can use the memoize pattern to our advantage: instead of working out the cost of each element every time our algorithm requires it, we simply fetch it from the cache (if it doesn't exist, we add it to the cache, and use it on all subsequent calls.)
The original brute force C# code looked like this:
static int MaxCost(Triangle triangle, int x, int y)
{
if (y == triangle.Depth)
{
return 0;
}
else
{
int left = MaxCost(triangle, x, y + 1);
int right = MaxCost(triangle, x + 1, y + 1);
return Math.Max(left, right) + triangle[x, y];
}
}We need to rewrite the method body slightly because it's self-recursive, and we can't take advantage of the memoize cache if our function just calls back into itself directly.
If we're pressed for time, we might simply code the cache into the method body:
static int MaxCost(Triangle triangle, int x, int y)
{
var key = new Tuple<Triangle,int,int>(triangle, x, y);
if (cache.ContainsKey(key))
{
return cache[key];
}
if (y == triangle.Depth)
{
return 0;
}
else
{
int left = MaxCost(triangle, x, y + 1);
int right = MaxCost(triangle, x + 1, y + 1);
int result = Math.Max(left, right) + triangle[x, y];
cache.Add(key, result);
return result;
}
}With more time on our hands, we might separate the function into two distinct logic functions, one that deals with memoization, and the other that deals with the problem at hand:
static int MemoizedMaxCost(Triangle triangle, int y, int x)
{
var key = new Tuple<Triangle, int, int>(triangle, x, y);
if (cache.ContainsKey(key))
{
cache[key];
}
int result = InternalMaxCost(triangle, y, x);
cache.Add(key, result);
return result;
}
static int InternalMaxCost(Triangle triangle, int x, int y)
{
if (y == triangle.Depth)
{
return 0;
}
else
{
int left = MemoizedMaxCost(triangle, x, y + 1);
int right = MemoizedMaxCost(triangle, x + 1, y + 1);
return Math.Max(left, right) + triangle[x, y];
}
}Note that we now have a pair of mutually recursive functions: the memoized function calls the internal one to evaluate any uncached values, and the internal one calls the memoized one to gain any of the performance benefits from memoizing. A match made in heaven?
Monday, September 05, 2011
Covariance / Contravariance
#region Covariance
interface IFunction<out TResult>
{
TResult Invoke();
}
class Function<TResult> : IFunction<TResult>
{
public TResult Invoke()
{
throw new NotImplementedException();
}
}
#endregion
#region Contravariance
interface IAction<in T>
{
void Invoke(T arg);
}
class Action<T> : IAction<T>
{
public void Invoke(T arg)
{
throw new NotImplementedException();
}
}
#endregion
#region Both
interface IFunction<in T, out TResult>
{
TResult Invoke(T arg);
}
class Function<T, TResult> : IFunction<T, TResult>
{
public TResult Invoke(T arg)
{
throw new NotImplementedException();
}
}
#endregionNone of the methods are implemented, because a) I'm lazy and b) you don't need to see an implementation to witness the co- or contravariance first hand. The next code block shows the phenomena at work:
IFunction<object> f1 = new Function<string>();
IAction<string> a1 = new Action<object>();
IFunction<string, object> f2 = new Function<object, string>();Notes:
- In the case of covariance, the generic argument type of the class is more specific than the interface (covariance: we can always implicitly cast from string to object when reading from the container).
- In the case of contravariance, the generic argument type of the interface is more specific than the class (contravariance: we can always implicitly cast from string to object when writing to the container).
- In the mixed case, we can see covariance for the output and contravariance for the input.
Monday, August 15, 2011
Real World Scalability
If the tests don't already exist, it will be much more difficult to determine that a scalability fix hasn't negatively altered the required behaviour of a process. But in a time when the bottom line is the final word and employers are encouraged to differentiate developers by price (for example: choosing a large off shore team) it's less common to see the tests written up front.
Friday, July 29, 2011
Map Reduce Example in F#
/// maps an input into a tuple of input and count
let mapper x =
(x, 1)
/// reduces a list of input and count tuples, summing the counts
let reducer (a:(string * int) list) (x:string * int) =
if List.length a > 0 && fst (List.head a) = fst x then
(fst (List.head a), snd (List.head a) + snd x)::List.tail a
else
x::a
/// maps the mapper function over a list of input
let map xs =
List.map (mapper) xs
/// maps the reducer function over a list of input and count tuples
let reduce (xs:(string * int) list) =
List.fold (reducer) [] xs
/// maps the input, sorts the intermediate data, and reduces the results
let mapReduce xs =
map xs
|> List.sort
|> reduceIt turns out the functional programming appears to be made for this pattern!
Monday, July 25, 2011
FaultException<T>
FaultException<T> where T is a custom System.Exception-derived type, you may be interested to know that the exception needs to have this protected constructor in order to work as expected:[Serializable]
public class NotFoundException : ApplicationException {
public NotFoundException() {
}
protected NotFoundException(SerializationInfo info, StreamingContext context)
:base(info, context) {
}
}Without it, WCF will not deserialize your custom exception properly, and you'll (at best) be able to catch a non-generic FaultException (with the rather unhelpful reason of "The creator of this fault did not specify a Reason."
Sunday, July 24, 2011
Monad
Basically, it's a bit of glue that joins two functions together. I decided to write one for myself in C# to see what it would look like without any syntactic sugar that other languages might provide:
public static class Binding {
public static Func<TInput, TOutput> Bind<TInput, TIntermediate, TOutput>(Func<TInput, TIntermediate> left, Func<TIntermediate, TOutput> right) {
return arg => right(left(arg));
}
}It's designed so that the output of
left "flows" into the input of right. The output of the rightmost function is returned to the caller as the result of the expression. Here are two functionally equivalent examples (one written normally, and the other with monads):Func<string, IEnumerable<char>> js = s => s.Select(c => c - '0').Where(i => i % 2 == 0).Select(i => (char)(i + 'a')).Select(c => Char.ToUpper(c));Func<string, IEnumerable<char>> ks = Binding.Bind<IEnumerable<char>, IEnumerable<int>, IEnumerable<char>>(
k1 => k1.Select(c => c - '0'),
Binding.Bind, IEnumerable<int>, IEnumerable<char>>(
k2 => k2.Where(i => i % 2 == 0),
Binding.Bind<IEnumerable<int>, IEnumerable<char>, IEnumerable<char>>(
k3 => k3.Select(i => (char)(i + 'a')),
k4 => k4.Select(c => Char.ToUpper(c))))); Check that they work as expected:
Debug.Assert(ks("0123456789").SequenceEqual(new char[] {'A','C','E','G','I'}));
Wednesday, June 29, 2011
Version Tolerant Serialization
In the object-oriented .NET Framework, memory to represent the state of an object instance is only ever allocated for fields*. Not properties. Properties are syntactic sugar applied to methods invoked to access the state of the object, which is always stored in fields. If you want to serialize an instance's state - it's the fields that must be written to the wire. To deserialize something off the wire - you guessed it - the fields are the destinations of the wire values.
Consider: an assembly A that exposes one type T. Initially (going against my natural desire to start counting at 0) we label them A1 and T1. And T1 looks like this:
namespace A {
[Serializable]
public class T {
private int f;
public int F {
get { return f; }
set { f = value; }
}
}
}
Another developer, D1, takes a copy of the A1 assembly and writes a fantastic application with it, connecting via (*cough*) .NET Remoting to a server that also has a copy of A1. The developer's job is done, and he retires comfortably in the Bahamas, but not before losing all the source code (and forgetting where it was even deployed).
Meanwhile, somebody working on the server team realizes that two ints are better than one, and that he can make the server even better if only he could add another int field G to type T.
Here's where the fun starts.
Prior to .NET 2.0, changing the fields of T would introduce a breaking change. Clients who only had access to A1's T1 would be unable to deserialize an instance of A2's T2, nor would they be able to serialize A1's T1 into the format required by the server (A2's T2). What they wished for (and Microsoft gave them) was:
namespace A {
[Serializable]
public class T {
private int f;
[OptionalField(VersionAdded = 2)]
private int g;
public int F {
get { return f; }
set { f = value; }
}
public int G {
get { return g; }
set { g = value; }
}
}
}
This allows the server to load A2 and serialize T2 down to the wire (and deserialize T1 off the wire).
It also allows the client to load A1 and serialize T1 down to the wire (and deserialize T2 off the wire).
Unfortunately for the fictional company stuck using .NET 1.1 with no source code, they'd have to get someone to bring them up to version 2.0 of .NET before they could appreciate the benefit.
Tuesday, June 21, 2011
Ambient Transactions
First, consider this sample block of code:
using (SqlConnection connection = new SqlConnection(connectionString))
using (SqlCommand command = new SqlCommand(commandText, connection))
{
// do something
}
There is no mention of any transactions; if you're like me you'd think that two things happen by the end of the block:
- SQL Server doesn't still hold any locks for the data accessed in the block, and
- The connection was returned to the pool for somebody else to use.
Wrong on both counts.
See what happens if the block was wrapped in another block (even a couple of frames higher on the stack):
using (TransactionScope transactionScope = new TransactionScope())
{
// substitute original block here
}
Although nothing in our inner block explicitly references any transactions, an ambient transaction (i.e. one on the current thread) has been setup by our outer block and SQL Server enlists in this transaction. At the point the inner block completes, the transaction is incomplete; although the connection is returned to the connection pool, it's in a cordoned off section of the pool where it cannot be used by any other thread that's not sharing the same transaction.
Let's imagine we set
Max Pool Size=1 in our connection string. This means we have 1 connection in the pool, but it's only available to the ambient transaction. If we try to obtain another connection from the pool from a different thread with no transaction or a different transaction (even a different ambient transaction) we would timeout waiting. If, instead, we repeated the inner block twice within the outer block, it would be fine: the second acquisition of a connection from the connection pool would grab the one with the (still open) ambient transaction. If we shared our transaction with another thread, we'd be able to aquire that same connection from the connection pool too. Here's a fun exercise for the imagination: Set
Max Pool Size=2; then open two connections concurrently within the same TransactionScope. You'll automatically have enlisted in a distributed transaction (not just the lightweight transaction outlined in the first part of the post). Hey presto, you're sharing a transaction across more than one SQL connection into the same server!There are several points to take away from this post:
You can force connections not to enlist in ambient transactions by using the
Enlist=false connection string property.You can implicitly participate in transactions (whether lightweight or distributed) even when you're not expecting to.
The connection pool is slightly more complex than at first it seemed - even returning a connection to the pool doesn't guarantee its availability for other operations.
Locks can remain held long after the connection has been disposed (returned to the pool)
For more information
Sunday, June 12, 2011
External Sort
First of all, divide the data into blocks that are small enough to be sorted in memory, then sort them and write the results to disk (or network, or anywhere external to your process). If memory size is M, and total data to be sorted is MxN then you should now have N blocks of locally sorted data.
Next, do an N-way merge. I did it by getting N buffered readers over the N blocks. By continually getting the next lowest value from the pool of N readers (it's easy if you continually sort the readers by last obtained value in ascending order) and writing the obtained values into an output file, you will end up with N globally sorted blocks of data.
For most people attempting a very large sort, this is usually the end result (I am assuming not a lot of people have this requirement very often, and even less frequently is it their first time at seeing it.) If you're left wanting, however, you must continue...
For large values of N it first becomes prohibitive to buffer the input, then to even access one value for every N at the same time. In this case, you will need to perform a second (or higher) pass, working on less than N blocks at a time. A 32-bit Windows machine should only begin to approach this next hurdle somewhere after the 10's of terabytes mark (depending of course, in the size of the objects being sorted)...
Asynchronous ASP.NET MVC
AsyncController class into the framework, enabling asynchronous ASP.NET MVC applications without forcing developers to hand-craft their own weird and wonderful solutions. The AsyncController exposes an AsyncManager property, which allows you to increment/decrement the number of outstanding operations, and collect arguments to pass through to the XxxCompleted method when all operations are complete. To use the said controller, do this:Derive your controller from
System.Web.Mvc.AsyncController, which is treated differently by ASP.NET, and allows you access to the AsyncManager.For each logical asynchronous method you need, provide a pair of methods that follow a set naming convention, where the method name prefix matches the action name:
1) Begin method name suffix is
Async and return type is void2) End method name suffix is
Completed, parameters match those set up in the AsyncManager, and return type is an ActionResult.For example:
public void IndexAsync()
{
ViewData["Message"] = "Welcome to Asynchronous ASP.NET MVC!";
AsyncManager.OutstandingOperations.Increment();
WebService.WebService webService = new MvcApplication1.WebService.WebService();
webService.HelloWorldCompleted += (sender, e) =>
{
AsyncManager.Parameters["greeting"] = e.Result;
AsyncManager.OutstandingOperations.Decrement();
};
webService.HelloWorldAsync();
}
public ActionResult IndexCompleted(string greeting)
{
ViewData["AsyncMessage"] = greeting;
return View();
}
In case the execution flow doesn't appear obvious: on receipt of a request for the Index action, ASP.NET uses reflection to find the method pair with the prefix Index and invokes the first half of the method pair (IndexAsync) on its thread pool. The method implementation declares one asynchronous operation to the AsyncManager. We use the Event-based Asynchronous Pattern to call a demo ASMX web service asynchronously from this client - the Completed event handler sets a parameter value and decrements the number of outstanding operations. ASP.NET waits for the number of outstanding operations to reach zero, then looks for an IndexCompleted method with a string parameter named "greeting" (because this is what we called the parameter when we assigned the result on the AsyncManager, during the web service completed event handler). It invokes it (the second half of the method pair) and the rest - they say - is history.
