Sunday, 5 January 2025

Euclidean algorithm in C# to find GCD and LCM

I am reading my Elementary Number Theory book by David M. Burton for a course i took at University, MNFMA104 Tallteori at NTNU in Trondheim. I like Number Theory in Math a lot and will look into writing some C# code, starting with this article. This article will look at how we can find the greatest common divisor (gcd). Mathematically speaking, the definition is the following:

Greatest Common Divisor (GCD)

Given two integers a and b, their greatest common divisor (GCD), denoted as d, is the largest positive integer that divides both a and b without leaving a remainder. Note that divides here means there is no remainer.

Formally, if d = gcd(a, b), then:

  1. d divides both a and b. This means d | a and d | b.
  2. If there is any other integer c that divides both a and b, then c ≤ d. This ensures that d is the greatest such integer.

For example the numbers 12 and 8 can be divided by 4. And we will see that d = gcd(12,8) = 4 next. But first, let's look at the Euclidean algorithm mathematical definition.

Euclidean Algorithm for GCD

Given two integers a and b (where a ≥ b > 0), their greatest common divisor (GCD), denoted as d, can be found using the Euclidean algorithm. The process is as follows:

  1. Let a and b be two integers such that a ≥ b and b > 0.
  2. Define a sequence of equations r0, r1, r2, …, where r0 = a and r1 = b.
  3. For i ≥ 0, compute ri+2 using the division algorithm:
    ri+2 = ri mod ri+1
  4. Continue this process until rn+1 = 0 for some integer n. At this point:
    d = rn = gcd(a, b)

In summary, the GCD of a and b is the last non-zero remainder obtained through this iterative process:

gcd(a, b) = d


Let's look at C# code to calculate the GDC, we will use the Euclidean algorithm to calculate it.

int Gcd(int a, int b)
{
	int q_n = Math.Abs(a);
	int r_n = Math.Abs(b);
	while (r_n != 0)
	{
		int remainder = q_n % r_n;
		q_n = r_n;
		r_n = remainder;
	}
	return q_n; // returning here the second-last quotient that was non-zero, which is the gcd
}

Calculating the gcd of 12 and 8 gives:

void Main()
{
	int a = 8;
	int b = 12;
	int gcd = Gcd(a, b);
	Console.WriteLine($"Demo - The greatest common divisor - GCD - using the Euclidean algorithm of the numbers : ");
	Console.WriteLine($"d = gcd({a}, {b}) = {gcd}");
    
}

//output 
// Demo - The greatest common divisor - GCD - using the Euclidean algorithm of the numbers : 
// d= gcd(8, 12) = 4


We can also calculate gcd of some bigger numbers. For example, the gcd of the numbers a= 5040 and b = 3780 are 1260. Both numbers 5040 and 3780 are divisible by 1260. We can also use C# patterns in case we want to apply a more functional approach. Together with tuples and C# patterns, the code becomes very compact, especially when we use recursion and tuples to compose the current state of the currend dividend and divisor, the two numbers we consider and get the remainder from.



<summary>
Calculate the greatest common divisor. Recursive C# pattern of GCD (using 'state approach' for tuple)
</summary>
int Gcd(int a, int b) => (a, b) switch
{
    (0, _) => Math.Abs(b),
    (_, 0) => Math.Abs(a),
    _ => GcdV2(b, a % b)
};



Calculating if two number are coprimes

Let's turn attention to coprime numbers a bit. It is a consequence that if the gcd of two numbers a and b, they are said to be relatively prime, or coprime.

In mathematical terms, two integers a and b are said to be coprime (or relatively prime) if their greatest common divisor (gcd) is 1.

Formally, given two integers a and b, a and b are coprime if:

gcd(a, b) = 1

This definition means that the only positive integer that divides both a and b is 1. In other words, they have no common prime factors.

For example, the numbers a = 1234, b = 3417 can be tested if they are coprimes, by calculating the gcd and if the gcd is 1, they are coprime. They have no other common factors than 1, i.e. they are both coprimes or relatively prime. Let's first define a method in C# :

bool AreCoprime(int a, int b) => Gcd(a,b) == 1; 

We can then verify that a = 1234, b = 3417 are relatively prime and the two numbers are relatively prime.

int a1 = 1234, b1 = 3417;
Console.WriteLine($"\nDemo - If two numbers - GCD - are equal to 1, they are co-primes (relative primes)  : ");
Console.WriteLine($"Are {a1} and {b1} coprime? {AreCoprime(a1, b1)}");

The output is:

Demo - If two numbers - GCD - are equal to 1, they are co-primes (relative primes)  : 
Are 1234 and 3417 coprime? True

Calculating the least common multiple (lcm)

The least common multiple - lcm - can be calculated from the gcd for two numbers a and b. The mathematical definition is this:

In mathematics, the least common multiple (LCM) of two integers a and b is the smallest positive integer m such that both a and b divide m without leaving a remainder. Formally, it can be defined as:

LCM(a, b) = |a · b| / GCD(a, b)

where GCD(a, b) is the greatest common divisor of a and b.

Consider the gcd of a= 5040 and b = 3780. We found that the gcd for the two numbers is : gcd(5040, 3780) = 1260 Here is the code for calculating the lcm:

int Lcm(int a, int b) => (a*b)/Gcd(a,b);


int lcm = Lcm(a,b);
Console.WriteLine($"Demo - Least common multiple - lcm: ");	
Console.WriteLine($"lcmd({a}, {b}) = {lcm}");

This outputs:

Demo - Least common multiple - lcm: 
lcm(5040, 3780) = 15120

The number 15120 above is divisible by both a and b, giving 3 and 4 and no remainder, and it is the lowest number which is both divisible, that is - no integer remainder from the division. We write this if we use m for lcm as : m | a and m | b. To calculate the lcm for multiple numbers, we can use:

int Lcm(int[] numbers) { 
	return numbers.Aggregate((a,b) => Lcm(a,b)); 
}

Note that Aggregate method here (from Linq) does not sum, but fold In functional programming, the term "fold" is often used to describe the process of reducing a collection of elements to a single value by iteratively applying a function. In C#, the Aggregate method is essentially a fold operation, as it reduces the array of numbers to a single value (in this case, the GCD or LCM) by applying the specified function. So, using Aggregate to calculate the GCD or LCM of multiple numbers is indeed an example of a fold operation. Example:

int a = 5040;
int b = 3780;
int c = 2520;
Console.WriteLine($"Demo - Least common multiple - lcm: ");
Console.WriteLine($"lcm({a}, {b}, {c}) = {lcm}");

Output is: Demo - Least common multiple - lcm: lcm(5040, 3780, 2520) = 15120

Saturday, 4 January 2025

Slider component for Blazor

I have added a Blazor component for Blazor, which uses INPUT of type range and additional CSS styling for more flexible setup of look and feel. The Blazor component is available on Github in my repo here:

https://github.com/toreaurstadboss/BlazorSlider

Blazor lib component

This repository contains Blazor lib Slider component that shows an input of type 'range'.

The slider got default horizontal layout, where the minimum value for the slider is shown to the most left of the scale, which goes along the x-axis for the slider got towards higher values and the maximum value is the value to the most right. The slider x-axis goes along the 'slider track'.

The value of the slider is indicated by the 'slider thumb'. Below the slider are shown 'tick marks', which are controlled by the Minimum and Maximum values and StepSize. Note that the supported data types are the data types that are IConvertible and struct, and the code expects types that can be converted to double. You can use integers for example, but also decimals or floats and so on. In addition, enums can be used, but it works only if your enum got consecutive values, for example 0,1,2,3,4 . The best results are if these consecutive values got the same StepSize. To start using the Blazor slider, add this using in your .razor file where you want to use the component.
 
@using BlazorSliderLib

Please note that the slider has been tested using Bootstrap, more specifically this version:

"bootstrap@5.3.3"
Here is sample markup you can add to test out the Blazor slider (3 sliders are rendered using a custom model and the updated values are shown in labels below :

    <div class="container"> 

        <div class="row">
            <div class="form-control col-md-4">
                <p><b>EQ5D-5L question 1.</b> <br />Mobility. Ability to walk.</p>
                <BlazorSliderLib.Slider T="Eq5dWalk" UseAlternateStyle="AlternateStyle.AlternateStyleInverseColorScale" Title="Ability to walk" ValueChanged="@((e) => UpdateEq5dQ1(e))"
                MinimumDescription="No Problems = The best ability to walk you can imagine" MaximumDescription="Incapable = The worst ability to walk you can imagine" />
            </div>
        </div>

        <div class="row">
            <div class="form-control col-md-4">
                <p><b>EQ5D-5L question 6.</b> <br />We would like to how good or bad your health is TODAY.</p>
            </div>
        </div>

        <div class="row">
            <div class="form-control col-md-4">
                <BlazorSliderLib.Slider T="int" UseAlternateStyle="AlternateStyle.AlternateStyle" Minimum="0" Maximum="100" @bind-Value="@(Model.Data.Eq5dq6)" Stepsize="5" Title="Your health today"
                MinimumDescription="0 = The worst health you can imagine" MaximumDescription="100 = The best health you can imagine" />
            </div>
        </div>

        <div class="row">
            <div class="form-control col-md-4">
                <p><b>EQ5D-5L question 6.</b> <br />We would like to how good or bad your health is TODAY. V2 field.</p>
            </div>
        </div>

        <div class="row">
            <div class="form-control col-md-4">
                <BlazorSliderLib.Slider T="int" Minimum="0" Maximum="100" ValueChanged="@((e) => UpdateEq5dq6V2(e))" Stepsize="5" Title="Your health today (v2 field)"
                MinimumDescription="0 = The worst health you can imagine" MaximumDescription="100 = The best health you can imagine" />
            </div>
        </div>

        <div class="row">
            <div class="form-control col-md-4">
                <p>Value of Model.Data.Eq5dq1</p>
                @Model.Data.Eq5dq1
            </div>
        </div>

        <div class="row">
            <div class="form-control col-md-4"> <p>Value of Model.Data.Eq5d6</p>
                @Model.Data.Eq5dq6 
            </div> 
        </div>

        <div class="row">
            <div class="form-control col-md-4">
                <p>Value of Model.Data.Eq5d6V2</p>
                @Model.Data.Eq5dq6V2
            </div>
        </div>

    </div>

The different setup of sliders

The slider is set up either with an alternate style or using the default styling for sliders, that is, the slider uses an input type of 'range' and the default documented styling on Mozilla Developer Network (MDN) to render a Blazor slider. In addition, it is possible to set up the alternate style to use a inverted color range where higher values will get a reddish color and lower values will get a greenish color. The standard alternate style will show greenish colors for higher values. The following screenshot shows the possible styling that is possible. Note that the default styling is shown in the slider at the bottom, which will render a bit different in different browsers. In Chrome for example, the slider will render with a bluish color. In Edge Chromium, a grayish color is used for the 'slider tick' and 'slider thumb'. Screenshots showing the sliders: The following parameters can be used:
Title
Required. The title is shown below the slider component and centered horizontally along the center of the x-axis which the slider is oriented.
Value
The value of the slider. It can be data bound using either the @bind-Value directive attribute that supports two-way data binding. You can instead use the @ValueChanged event callback, if desired.
Minimum
The minimum value along the slider. It is default set to 0 for numbers. For enums, the lowest value is chosen of the enum (minimum enum alternative, converted to double internally).
Maximum
The maximum value along the slider. It is default set to 100 for numbers. For enums, the higheset value is chosen of the enum (maximum enum alternative, converted to double internally).
Stepsize
The step size for the slider. It is default set to 5 for numbers. For enums, it is set to 1. (note that internally the slider must use double values to work with the _tickmarks_, which expects double values).
ShowTickmarks
Shows tick marks for slider. It is default set to 'true'. Tick marks are generated from the values of Minimum, Maximum and StepSize.
MinimumDescription
Shows additionally description for the minimum value, shown as a small label below the slider. It will only be shown in the value is not empty.
UseAlternateStyle
If the UseAlternateStyle is set to either AlternateStyle and AlternateStyleInverseColorScale, alternate styling is used.

CSS rules to enable the slider

Actually, it is necessary to define a set of CSS rules to make the slider work. The slider's css rules are defined in two different files.

Default CSS rules

`Slider.css` The CSS rules below are taken from MDN Mozilla Developer Network page for the input type 'range' control. Input type 'range' control MDN article:

https://developer.mozilla.org/en-US/docs/Web/HTML/Element/input/range

Additional settings are set up. The width is set to 100% so the slider can get as much horizontal space as possible and 'stretch'. There are also basic styles set up for both the tick label and datalist.The datalist is the tickmarks for the slider. The tick marks are automatically generated for the slider.


.sliderv2
{
    width:100%;
}

.sliderv2Label {
    font-weight: 400;
    text-align: center;
    left: 50%;
    font-size:0.7em;
    font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, margin-bottom: 2px;
}

datalist {
    display: flex;
    flex-direction: column;
    justify-content: space-between;
    writing-mode: vertical-lr;
    width: 100%;
}

.tick-label {

    justify-content: space-between;
    font-size:0.6em;

    top: 20px; /* Adjust this value as needed */
}

input[type="range"] {
    width: 100%;
    margin: 0;
}


Alternate CSS rules

`SliderAlternate.css` The alternate CSS rules are setting up additional styling, where color encoding is used for the 'slider track' where higher values along the 'slider track' get a more 'greenish color', while lower values gets 'reddish values'. It is possible to set up the inverse color encoding here, with higher values getting 'reddish color'. Lower values gets more 'greenish colors' in this setup.


.alternate-style input[type="range"] {
    -webkit-appearance: none; /* Remove default styling */
    width: 100%;
    height: 8px;
    background: #ddd;
    outline: none;
    opacity: 0.7;
    transition: opacity .2s;
}

    .alternate-style input[type="range"]:hover {
        opacity: 1;
    }

    .alternate-style input[type="range"]::-webkit-slider-runnable-track {
        width: 100%;
        height: 8px;
        background: linear-gradient(to left, #A5D6A7, #FFF9C4, #FFCDD2); /* More desaturated gradient color */
        border: none;
        border-radius: 3px;
    }

        .alternate-style-inverse-colorscale input[type="range"]::-webkit-slider-runnable-track {
            background: linear-gradient(to right, #A5D6A7, #FFF9C4, #FFCDD2) !important; /* More desaturated gradient color, inverted color range */
        }


.alternate-style input[type="range"]::-webkit-slider-thumb {
    -webkit-appearance: none; /* Remove default styling */
    appearance: none;
    width: 25px;
    height: 25px;
    background: #2E7D32; /* Even darker green thumb color */
    cursor: pointer;
    border-radius: 50%;
    margin-top: -15px !important; /* Move the thumb up */
}

    .alternate-style input[type="range"]::-moz-range-track {
        width: 100%;
        height: 8px;
        background: linear-gradient(to left, #A5D6A7, #FFF9C4, #FFCDD2); /* More desaturated gradient color */
        border: none;
        border-radius: 3px;
    }

        .alternate-style-inverse-colorscale input[type="range"]::-moz-range-track {
            background: linear-gradient(to right, #A5D6A7, #FFF9C4, #FFCDD2 !important; /* More desaturated gradient color, inverted color range */
        }

    .alternate-style input[type="range"]::-moz-range-thumb {
        width: 25px;
        height: 25px;
        background: #2E7D32; /* Even darker green thumb color */
        cursor: pointer;
        border-radius: 50%;
        transform: translateY(-15px); /* Move the thumb up */
    }


The implementation for the Blazor slider looks like this, in the codebehind file for the Slider:


using Microsoft.AspNetCore.Components;

namespace BlazorSliderLib
{

    /// <summary>
    /// Slider to be used in Blazor. Uses input type='range' with HTML5 element datalist and custom css to show a slider.
    /// To add tick marks, set the <see cref="ShowTickmarks"/> to true (this is default)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public partial class Slider<T> : ComponentBase
        where T : struct, IComparable
    {

        /// <summary>
        /// Initial value to set to the slider, data bound so it can also be read out
        /// </summary>
        [Parameter]
        public T Value { get; set; }

        public double ValueAsDouble { get; set; }

        public double GetValueAsDouble()
        {
            if (typeof(T).IsEnum)
            {
                if (_isInitialized)
                {
                    var e = _enumValues.FirstOrDefault(v => Convert.ToDouble(v).Equals(Convert.ToDouble(Value)));
                    return Convert.ToDouble(Convert.ChangeType(Value, typeof(int)));
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return Convert.ToDouble(Value);
            }
        }        

        [Parameter, EditorRequired]
        public required string Title { get; set; }

        [Parameter]
        public string? MinimumDescription { get; set; }

        [Parameter]
        public string? MaximumDescription { get; set; }

        [Parameter]
        public double Minimum { get; set; } = typeof(T).IsEnum ? Enum.GetValues(typeof(T)).Cast<int>().Select(e => Convert.ToDouble(e)).Min() : 0.0;

        [Parameter]
        public double Maximum { get; set; } = typeof(T).IsEnum ? Enum.GetValues(typeof(T)).Cast<int>().Select(e => Convert.ToDouble(e)).Max() : 100.0;

        [Parameter]
        public double? Stepsize { get; set; } = typeof(T).IsEnum ? 1 : 5.0;

        [Parameter]
        public bool ShowTickmarks { get; set; } = true;

        [Parameter]
        public AlternateStyle UseAlternateStyle { get; set; } = AlternateStyle.None;

        [Parameter]
        public EventCallback<T> ValueChanged { get; set; }

        public List<double> Tickmarks { get; set; } = new List<double>();

        private List<T> _enumValues { get; set; } = new List<T>();

        private bool _isInitialized = false;

        private async Task OnValueChanged(ChangeEventArgs e)
        {
            if (e.Value == null)
            {
                return;
            }
            if (typeof(T).IsEnum && e.Value != null)
            {
                var enumValue = _enumValues.FirstOrDefault(v => Convert.ToDouble(v).Equals(Convert.ToDouble(e.Value))); 
                if (Enum.TryParse(typeof(T), enumValue.ToString(), out _)) {
                    Value = enumValue; //check that it was a non-null value set from the slider
                }
                else
                {
                    return; //if we cannot handle the enum value set, do not process further
                }
            }
            else
            {
                Value = (T)Convert.ChangeType(e.Value!, typeof(T));
            }

            ValueAsDouble = GetValueAsDouble();

            await ValueChanged.InvokeAsync(Value);
        }


        private string TickmarksId = "ticksmarks_" + Guid.NewGuid().ToString("N");

        protected override async Task OnParametersSetAsync()
        {
            if (_isInitialized)
            {
                return ; //initialize ONCE 
            }

            if (!typeof(T).IsEnum && Value.CompareTo(0) == 0)
            {
                Value = (T)Convert.ChangeType((Convert.ToDouble(Maximum) - Convert.ToDouble(Minimum)) / 2, typeof(T));
                ValueAsDouble = GetValueAsDouble();
            }

            if (Maximum.CompareTo(Minimum) < 1)
            {
                throw new ArgumentException("The value for parameter 'Maximum' is set to a smaller value than {Minimum}");
            }
            GenerateTickMarks();

            BuildEnumValuesListIfRequired();

            _isInitialized = true;

            await Task.CompletedTask;
        }

        private void BuildEnumValuesListIfRequired()
        {
            if (typeof(T).IsEnum)
            {
                foreach (var item in Enum.GetValues(typeof(T)))
                {
                    _enumValues.Add((T)item);
                }
            }
        }

        private void GenerateTickMarks()
        {
            Tickmarks.Clear();
            if (!ShowTickmarks)
            {
                return;
            }
            if (typeof(T).IsEnum)
            {
                int enumValuesCount = Enum.GetValues(typeof(T)).Length;
                double offsetEnum = 0;
                double minDoubleValue = Enum.GetValues(typeof(T)).Cast<int>().Select(e => Convert.ToDouble(e)).Min();
                double maxDoubleValue = Enum.GetValues(typeof(T)).Cast<int>().Select(e => Convert.ToDouble(e)).Max();
                double enumStepSizeCalculated = (maxDoubleValue - minDoubleValue) / enumValuesCount;

                foreach (var enumValue in Enum.GetValues(typeof(T)))
                {
                    Tickmarks.Add(offsetEnum);
                    offsetEnum += Math.Round(enumStepSizeCalculated, 0);
                }
                return;
            }

            for (double i = Convert.ToDouble(Minimum); i <= Convert.ToDouble(Maximum); i += Convert.ToDouble(Stepsize))
            {
                Tickmarks.Add(i);
            }

        }      

    }

    public enum AlternateStyle
    {
        /// <summary>
        /// No alternate style. Uses the ordinary styling for the slider (browser default of input type 'range')
        /// </summary>
        None,

        /// <summary>
        /// Applies alternate style, using in addition to the 'slider track' an additional visual hint with an additional 'slider track' right below that shows a reddish color for lowest parts of the scale to the slider and towards yellow and greenish hues for higher values
        /// The alternate style uses a larger 'slider thumb' and alternate style to the 'slider-track'. The alternate style gives a more interesting look, especially in Microsoft Edge Chromium.
        /// </summary>
        AlternateStyle,

        /// <summary>
        /// Similar in style to the alternate style, but uses the inverse scale for the colors along the slider
        /// </summary>
        AlternateStyleInverseColorScale
    }

}


The markup of the Slider looks like this:


@using Microsoft.AspNetCore.Components.Forms
@using BlazorSliderLib
@typeparam T where T : struct, IComparable

<div class="slider-container sliderv2 @((UseAlternateStyle == AlternateStyle.AlternateStyle || (UseAlternateStyle == AlternateStyle.AlternateStyleInverseColorScale))? "alternate-style" : "") @(UseAlternateStyle == AlternateStyle.AlternateStyleInverseColorScale ? "alternate-style-inverse-colorscale" : "")">
<input type="range" @bind="@ValueAsDouble" min="@Minimum" max="@Maximum" step="@Stepsize" list="@TickmarksId" @oninput="OnValueChanged" />
<datalist id="@TickmarksId">
    @{
        var itemIndex = 0;
    }
    @foreach (var value in Tickmarks){
        if (typeof(T).IsEnum){
            var itemLabel = _enumValues.ElementAt(itemIndex);
            <option class="tick-label" value="@value" label="@itemLabel"></option>
        }
        else {
            <option class="tick-label" value="@value" label="@value"></option>
        }
        itemIndex++;    
    }
</datalist>

<div class="row">
@if (!string.IsNullOrWhiteSpace(MinimumDescription)){
    <div class="col-md-4">
        <label class="sliderv2Label text-muted">@MinimumDescription</label>
    </div>
}
@if (!string.IsNullOrWhiteSpace(Title)){
    <div class="col-md-4">
        <label class="sliderv2Label text-muted" style="text-align:center">@Title: @Value</label>
    </div>
}

@if (!string.IsNullOrWhiteSpace(MaximumDescription)){
    <div class="col-md-4" style="text-align:right">
        <label class="sliderv2Label tet-muted text-end">@MaximumDescription</label>
    </div>
}

</div>

<link rel="stylesheet" href="_content/BlazorSliderLib/Slider.css" />
<link rel="stylesheet" href="_content/BlazorSliderLib/SliderAlternate.css" />

<link rel="shortcut icon" type="image/x-icon" href="favicon.ico"/>


</div>


The slider control is provided "as is" and is free to change and use of no charge.

https://github.com/toreaurstadboss/BlazorSlider?tab=MIT-1-ov-file#readme