Step by Step solution about How to resolve the algorithm Ethiopian multiplication step by step in the C# programming language

The Ethiopian Multiplication, also known as the doubling and halving multiplication algorithm, is a technique used to multiply two numbers of any size by using only addition, subtraction, and bit shifting. This means that it can be used even in situations where a computer or calculator is not available.

This source code implements the Ethiopian Multiplication in three different ways: using recursion, using LINQ (Language Integrated Query), and using a loop.

The recursion function, EM_Recursion, is the most elegant of the three, but it is also the most difficult to understand. The function works by calling itself twice, once with the number A halved and the number B doubled, and once with the number A halved and the number B doubled again. The result of the first call is then added to the result of the second call, and the result of that is returned.

The LINQ function, EM_Linq, is a more concise and readable way to implement the Ethiopian Multiplication than the recursion function. The function works by creating a range of numbers from 1 to the number of times that the number A can be halved. Then, for each number in the range, it creates a new list of pairs of numbers, each pair consisting of the number A and the number B. The list of pairs is then aggregated using the Aggregate method, which iterates over every value in the list and passes the accumulated value and the current item's value to a function. The function then returns a new pair of numbers, consisting of the first number halved and the second number doubled. Finally, the list of pairs is filtered to remove all of the pairs where the first number is even, and the remaining pairs are summed to produce the final result.

The loop function, EM_Loop, is the simplest and most straightforward of the three, but it is also the least efficient. The function works by repeatedly halving the number A and doubling the number B, and adding the number B to the result each time the number A is odd. The function terminates when the number A is equal to 1, and the result is returned.

Here is an example of how to use the Ethiopian Multiplication to multiply the numbers 17 and 34:

int A = 17;
int B = 34;
int Result = EthiopianMultiplication_Task.EM_Recursion(A, B);
Console.WriteLine("The result of multiplying {0} and {1} using the Ethiopian Multiplication is {2}.", A, B, Result);

The output of this code will be:

The result of multiplying 17 and 34 using the Ethiopian Multiplication is 578.

using System;
using System.Linq;

namespace RosettaCode.Tasks
{
	public static class EthiopianMultiplication_Task
	{
		public static void Test ( )
		{
			Console.WriteLine ( "Ethiopian Multiplication" );
			int A = 17, B = 34;
			Console.WriteLine ( "Recursion: {0}*{1}={2}", A, B, EM_Recursion ( A, B ) );
			Console.WriteLine ( "Linq: {0}*{1}={2}", A, B, EM_Linq ( A, B ) );
			Console.WriteLine ( "Loop: {0}*{1}={2}", A, B, EM_Loop ( A, B ) );
			Console.WriteLine ( );
		}

		public static int Halve ( this int p_Number )
		{
			return p_Number >> 1;
		}
		public static int Double ( this int p_Number )
		{
			return p_Number << 1;
		}
		public static bool IsEven ( this int p_Number )
		{
			return ( p_Number % 2 ) == 0;
		}

		public static int EM_Recursion ( int p_NumberA, int p_NumberB )
		{
			//     Anchor Point,                Recurse to find the next row                                 Sum it with the second number according to the rules
			return p_NumberA == 1 ? p_NumberB : EM_Recursion ( p_NumberA.Halve ( ), p_NumberB.Double ( ) ) + ( p_NumberA.IsEven ( ) ? 0 : p_NumberB );
		}
		public static int EM_Linq ( int p_NumberA, int p_NumberB )
		{
			// Creating a range from 1 to x where x the number of times p_NumberA can be halved.
			// This will be 2^x where 2^x <= p_NumberA. Basically, ln(p_NumberA)/ln(2).
			return Enumerable.Range ( 1, Convert.ToInt32 ( Math.Log ( p_NumberA, Math.E ) / Math.Log ( 2, Math.E ) ) + 1 )
				// For every item (Y) in that range, create a new list, comprising the pair (p_NumberA,p_NumberB) Y times.
				.Select ( ( item ) => Enumerable.Repeat ( new { Col1 = p_NumberA, Col2 = p_NumberB }, item )
					// The aggregate method iterates over every value in the target list, passing the accumulated value and the current item's value.
					.Aggregate ( ( agg_pair, orig_pair ) => new { Col1 = agg_pair.Col1.Halve ( ), Col2 = agg_pair.Col2.Double ( ) } ) )
				// Remove all even items
				.Where ( pair => !pair.Col1.IsEven ( ) )
				// And sum!
				.Sum ( pair => pair.Col2 );
		}
		public static int EM_Loop ( int p_NumberA, int p_NumberB )
		{
			int RetVal = 0;
			while ( p_NumberA >= 1 )
			{
				RetVal += p_NumberA.IsEven ( ) ? 0 : p_NumberB;
				p_NumberA = p_NumberA.Halve ( );
				p_NumberB = p_NumberB.Double ( );
			}
			return RetVal;
		}
	}
}