Multi-service architectures surround us daily. Our computing needs are served from many different independently operated services, and all implemented using different underlying technologies. When these independent units bring only one small service or set of services, it is called a microservice. While there is still some industry discussion about the exact properties of a microservice, one thing can be agreed upon: microservice-based systems enforce modular design by default. This begs the question, if my services are decoupled and modular, how do they communicate effectively to create an entire system that performs something useful?

Enterprise Service Buses and Middleware

The solution to this problem is a connector software which acts as a message routing bus. The Enterprise Service Bus (ESB), often simplified as Middleware (although Middleware is not always an ESB), allows these decoupled services to talk to each other in a language and medium-neutral way. For instance, if you have a Service-Oriented Architecture (SOA) comprised of services written in different languages, with a few plug ‘n play components, but they all need to share data, a language-neutral ESB is in order.

Many of the commercial ESBs are written as a publisher-subscriber (PubSub) system. This allows the individual services to subscribe to the types of messages it is interested in knowing about. The ESB or Middleware is responsible for managing the “channels” and relaying the published messages to the right subscribers. The Middleware or ESB provider will usually provide a connector for many languages making it easy to interface your services to the ESB. If the connector is not provided, the specification will usually be provided so that you can implement your own connector. This allows an SOA system to communicate without worrying about the transport mechanism of its messages.

It’s easy to see that ESBs can be found nearly everywhere in technology. In fact, many of the most common services we use today can be loosely classified as an ESB. Perhaps I’ll start a project soon to build an ESB and see how it goes?

Thanks for reading!

The post Enterprise Service Buses and Middleware appeared first on Jacob N Calvert.

An interesting thing to note about the Fibonacci sequence is that the ratio of one Fib number to its predecessor approaches the Golden Ratio as the Fib numbers get higher and higher. For example:

Golden Ratio =  1.61803398875

2/1 = 2

3/2 = 1.5

5/3 = 1.667

8/5 = 1.6

.
.
.

55/34 = 1.617647059
.
.
.
987/610 = 1.618032787

This is a very interesting point to me. However, I learned a few days ago that there is another sequence like the Fibonacci sequence. If you take any two positive integers as the starting of the sequence, and the apply the Fibonacci method, the same approach to the Golden Ratio occurs, with a twist. Let’s test this:

Take the first number = 1234
Take the second number = 1588


1588/1234 = 1.286871961

1588+1234 = 2822

2822/1588 = 1.777078086

2822+1588 = 4410

4410/2822 = 1.562721474

from here, I will just show the divisions...

7232/4410 = 1.639909297

11642/7232 = 1.60978923

18874/11642 = 1.621199107

30516/18874 = 1.616827382

It seems as though the ratio is “hovered around” as the sequence grows. To cut down on the number of hand calculations, I wrote a python script which I have attached to this post. I took three samples and recorded the output. Sample1 I used A = 1234 and B = 1588, Sample 2 I used A = 10 and B = 20 and Sample 3 I used A = 13 and B = 17. I used L = 10000000000 for all three. They each settled down to approximately the Golden Ratio after about 20 iterations of the algorithm. I do not know the mathematical proof of this sequence however I find it interesting that they each reach the same result in a similar numbers of iterations. I’ve attached the python file and my three sample outputs if you’re interested in playing with the sequence! I’ve also linked some articles about this subject in case you want to read more technical descriptions.

More on this subject

Fibonacci Numbers
Golden Ratio

Downloads

interesting_sequence.py

Sample3 Sample2 Sample1
Thanks for reading!

The post Interesting Numbers appeared first on Jacob N Calvert.

But to multiply really big numbers, we represent the two multiplicands as polynomials where each term is in the form cxⁿ, where x is the base in the number system, c is its coefficent modifier and n is the power to which the base is modified. For example, we can represent 4587 as 4x³ + 5x² + 8x¹ + 7x⁰, where x = 10.
Now, two numbers in this polynomial base representation can be multiplied to give the result. Here’s a small example:

321 = 3*10^2 + 2*10^1 + 1*10^0 ==> 3x^2 + 2x + 1

123 = 1*10^2 + 2*10^1 + 3*10^0 ==> 1x^2 + 2x + 3

321 * 123 = (3x^2 + 2x + 1)*(1x^2 + 2x + 3) = 3x^4 + 6x^3 + 9x^2 + 2x^3 + 4x^2 + 6x + x^2 +2x + 3 
= 3x^4 + 8x^3 + 14x^2 + 8x + 3

Now plugging in x = 10 ==>  3(10)^4 + 8(10)^3 + 14(10)^2 + 8(10) + 3 = 39483

Now verify with a calculator that 123*321 = 39483

Cool, huh?

We can use this knowledge to multiply some really, really big numbers. Since we have a way to calculate them product using polynomials, the question now is this: how do we multiply these polynomials when the order is large (like order-50 or order-n)? This is where the Toom-k algorithm becomes helpful.
First, let’s represent the polynomials as arrays where the position i indicates the power and the value at i represents the coefficient.

3x^2 + 2x + 1

will be represented as

[1, 2, 3]

Toom-k states that we can divide the polynomial array into sub-arrays of length (n/k) and perform (2*k)-1 recursive calls on those sub-arrays, then recombine them in O(n) time, and have a solution. For this article I want to focus on Toom-3, or otherwise called the Toom-Cook algorithm. To simplfiy the algorithm, we’ll require the length of our input arrays to be divisible by 3. Call the two input polynomials P and Q. P and Q get partitioned into n/3 or otherwise stated, they are divided into thirds. Call these sub-arrays A, B, C, D, E, and F where these are each of size n/3. Create 5 more arrays of size n/3 called G, H, J, L, M. Their values are as follows:
G = A+C, H = D+F, J = G-B, K = H-E, L = 2(J+A)-C, M = 2(K+D)-F
Here comes some serious math.
In this method of representing polynomials as arrays, an order-n polynomial takes up an array of length (n+1). Like in our previous example:

3x^2 + 2x + 1 is order-2

so n = 2, but its array representation takes up (n+1) = 3 length

[1, 2, 3]

Since this is known, then we can determine that multiplying two polynomials together of any order-n will generate in our system of representation an array of length (2*n)-1.
Ok, back to the Toom-3. We now create 5 more arrays of length (2*n)-1 named R, S, T, U, V. They are defined as R = AD, S = CF, T = (G+B)(H+E), U = JK, V = LM.
One more set of arrays of length (2*n/3)-1 named W, X, Y, Z and are defined as W = (V-T)/3, X = (T-U)/2, Y = U-S, Z = (Y-W)/2 + 2R.
Now we need to recombine these arrays into the final solution form. The product P*Q is defined as follows:
P*Q = Rx^(4n/3) + Zx^n + (X+Y-R)x^(2n/3) + (X-Z)x^(n/3) + S
This formula can look confusing, but it makes sense with some code to go with it:

BigInt* make_array(BigInt size)
{
	BigInt*res = new BigInt[size];
	for(BigInt i = 0; i < size; i ++)
	{
		res[i] = 0;
	}
	return res;
}
BigInt* Toom3(BigInt* P, BigInt*Q, BigInt n)
{
	BigInt pq_size = (2*n) -1 ;
	BigInt *PQ_Res = make_array(pq_size);
	BigInt sub_eq_size = n/3;
	BigInt *A = new BigInt[sub_eq_size], *B =new BigInt[sub_eq_size], *C=new BigInt[sub_eq_size], *D=new BigInt[sub_eq_size], *E=new BigInt[sub_eq_size], *F=new BigInt[sub_eq_size];
	memcpy(C,&P[0], sizeof(BigInt) * sub_eq_size);
	memcpy(B,&P[sub_eq_size], sizeof(BigInt) * sub_eq_size);
	memcpy(A,&P[sub_eq_size*2], sizeof(BigInt) * sub_eq_size);
	memcpy(F,&Q[0], sizeof(BigInt) * sub_eq_size);
	memcpy(E,&Q[sub_eq_size], sizeof(BigInt) * sub_eq_size);
	memcpy(D,&Q[sub_eq_size*2], sizeof(BigInt) * sub_eq_size);

	BigInt *G = new BigInt[sub_eq_size], *H =new BigInt[sub_eq_size], *J =new BigInt[sub_eq_size], *K =new BigInt[sub_eq_size], *L =new BigInt[sub_eq_size],*M =new BigInt[sub_eq_size];
	BigInt* GpB=new BigInt[sub_eq_size], *HpE=new BigInt[sub_eq_size];
	for(BigInt i = 0; i < sub_eq_size; i++)
	{
		G[i] = A[i] + C[i];
		H[i] = D[i] + F[i];
		J[i] = G[i] - B[i];
		K[i] = H[i] - E[i];
		L[i] = (2* (J[i] + A[i])) - C[i];
		M[i] = (2* (K[i] + D[i])) - F[i];
		GpB[i] = G[i] + B[i];
		HpE[i] = H[i] + E[i];
	}
	BigInt *R, *S, *T, *U, *V; //finally!
	R = mult(A, D, sub_eq_size, sub_eq_size);
	S = mult(C, F, sub_eq_size, sub_eq_size);
	U = mult(J, K, sub_eq_size, sub_eq_size);
	V = mult(L, M, sub_eq_size, sub_eq_size);
	T = mult(GpB, HpE, sub_eq_size, sub_eq_size);
	
	BigInt *W=new BigInt[2*n/3 -1], *X=new BigInt[2*n/3 -1], *Y=new BigInt[2*n/3 -1], *Z=new BigInt[2*n/3 -1]; // i just thought i was done.
	for(BigInt i = 0; i < 2*n/3 -1; i++)
	{
		W[i] = (V[i] - T[i])/3;
		X[i] = (T[i] - U[i])/2;
		Y[i] = U[i] - S[i];
		Z[i] = ((Y[i] - W[i])/2) + (2*R[i]);
	}
	for(BigInt i = 0; i < 2*n/3 -1; i++)
	{
		PQ_Res[i] 		+= S[i];
		PQ_Res[i + (n/3)]	+= (X[i] - Z[i]);
		PQ_Res[i + (2*n/3)] 	+= (X[i] + Y[i] - R[i]);
		PQ_Res[i + (n)] 	+= Z[i];
		PQ_Res[i + (4*n)/ 3] 	+= R[i];
	}
	return PQ_Res;
}

This method can be analyzed in its runtime using the Master Recurrence Theorem. Take Toom-3 for example. Its running time is T(n) = θ(1) + 5T(n/3) + θ(n). Using the Recurrence theorem we can show that the running time of Toom-3 is n^log₃5.For any general Toom-k, it can be shown that since we do (2*k) – 1 recursions and we split the arrays in to sub-arrays of size (n/k), the running time of Toom-k is T(n) = θ(1) + ((2*k)-1)T(n/k) + θ(n) which when used against the Recurrence theorem we show that it is of n^log_k(2*k)-1 time complexity. I found this very interesting and I hope you do too!!

The post Toom-k Polynomial Multiplication appeared first on Jacob N Calvert.