Mersenne Asalları

Mersenne sayıları, ikinin kuvvetlerinin bir eksiği şeklinde olan sayılardır. n doğal sayısı için Mn = 2n - 1 şeklinde hesaplanır.

Mersenne asal sayıları, hem bir Mersenne sayısı hem de asal olan sayılardır. n sayısı için Mn = 2n - 1 işleminin sonucu bir asal sayı ise bu sayıya Mersenne asal sayısı denir.

Mersenne asal sayılarına örnek olarak,

n = 2 için 22 - 1 = 3
n = 3 için 23 - 1 = 7
n = 5 için 25 - 1 = 31

verilebilir. 3, 7 ve 31 asal sayılardır.

Günümüzde bulunan en büyük asal sayılar, Mersenne asallarından oluşmaktadır. Mersenne asallarının tespit edilmesinde kullanılan bazı pratik yöntemlerden dolayı, yeni asal sayı araştırması yapan gruplar, Mersenne asalları üzerine yoğunlaşmıştır.

2016 'nın Ocak ayı itibariyle 49 Mersenne asal sayısı bilinmektedir. Bilinen en büyük Mersenne asal sayısı 274.207.281 - 1'dir.

Teorem

Bir Mersenne sayısının asal olabilmesi için, ikinin kuvvetinin de asal olması gerekir.

Geometrik seriler için,

s = 1 + r + r2 + r3 + ... + rn-1

Eşitliğin her iki tarafını r ile çarparsak,

rs = r + r2 + r3 + r4 + ... + rn

İki eşitliğin farkı,

s - rs = 1 - rn
s(1 - r) = 1 - rn
rn -1 = s(r - 1)

Teoreme göre, ikinin kuvveti asal değilse, Mersenne sayısının da asal olmaması gerekir. İkinin kuvveti, yani n değeri asal değilse, n değeri axb şeklinde, iki tam sayının çarpımı şeklinde yazılabilir.

2ab değerini 2ab şeklinde yazarsak, 2ab - 1 = s(2a - 1) olur.
2ab değerini 2ba şeklinde yazarsak, 2ba - 1 = s(2b - 1) olur.

Yukarıdaki iki eşitliğe göre, 2ab - 1 değeri hem 2a - 1 hem de 2b - 1 değerine tam olarak bölünür. Yani bu durumda, birden fazla böleni olduğu için 2ab - 1 değeri asal olmaz.

Lucas-Lehmer Asallık Testi

Bir Mersenne sayısının asal olup olmadığını anlamak için kullanılan etkili bir yöntemdir. Klasik yöntemlere göre, bir Mersenne sayısının asal olup olmadığını tespit etmek için gerekli süre, bu test ile dramatik bir şekilde kısalmaktadır.

Lucas-Lehmer asallık testine göre, 2p - 1 sayısının asal olması için aşağıdaki şartın sağlanması gereklidir.

S(0) = 4
S(n) = (S(n-1)2 - 2) mod (2p-1)

rekürsif fonksiyona göre

S(p-2) = 0

değerini veriyorsa, 2p - 1 Mersenne sayısı asaldır.

Örnek vermek gerekirse, 27 - 1 sayısını asal olup olmadığına bakalım. Bu sayının asal olması için, S(p - 2) yani S(5) değerinin 0 olması gerekir.

S(0) = 4 
S(1) = (4x4 - 2) mod 127 = 14 
S(2) = (14x14 - 2) mod 127 = 67 
S(3) = (67x67 - 2) mod 127 = 42 
S(4) = (42x42 - 2) mod 127 = 111 
S(5) = (111x111 - 2) mod 127 = 0

Dolayısıyla, 27 - 1 sayısı asaldır.

Lucas-Lehmer testinin C# dilinde yazılmış kaynak kodu yer almaktadır.

using System;
using System.Numerics;

namespace SG.Algorithm
{
    public class MersenneNumber
    {
        /// <summary>
        /// (2^p - 1) değerinin asal sayı olup olmadığına bakılıyor.
        /// </summary>
        public bool IsPrimeNumber(int p)
        {
            if (p < 2)
            {
                throw new ArgumentException(nameof(p));
            }

            // Eğer p değeri çift ise, sadece 2 değeri için Mersenne asalı olur.
            if (p % 2 == 0)
            {
                return p == 2;
            }

            // (2^p - 1) sayısının asal olması için, p değerinin de asal olması gerekiyor.
            // Tüm tek sayılara göre mod alma işlemi uygulanarak, p sayısının asal olup olmadığına bakılıyor.
            // Döngünün p^(1/2) ye kadar çalışması yeterli. Hiçbir sayı, karekök değerinden büyük bir sayıya tam olarak bölünemez.
            for (int i = 3; i <= (int)Math.Sqrt(p); i += 2)
            {
                if (p % i == 0)
                {
                    // Tam olarak bölünüyor, asal değil.
                    return false;
                }
            }

            // Değer çok büyük olabileceği için BigInteger kullanılmıştır.
            var mode = BigInteger.Pow(2, p) - 1;

            // S fonksiyonu başlangıç değeri
            var S = new BigInteger(4);

            // S(p-2) değeri bulunacak
            for (int n = 1; n <= p - 2; n++)
            {
                // S(n) = (S(n-1)^2 - 2) mod (2p-1)
                S = (BigInteger.Pow(S, 2) - 2) % mode;
            }

            // S(p-2) değeri 0 ise, (2^p - 1) değeri asaldır.
            return S == 0;
        }
    }
}
Etiketler:  C#

Newton-Raphson Metodu ile Fonksiyon Kök Bulma

Newton-Raphson metodu, sayısal analizde, eşitlik köklerinin bulunmasında en yaygın kullanılan metotlardan birisidir. Başlangıç için tahmini bir kök değeri seçilerek, yapılan iterasyon sonucu gerçek kök değerine oldukça yakın bir değere ulaşılır.

Newton-Raphson

Newton-Raphson metodunun C# dilinde yazılmış kaynak kodu yer almaktadır.

public class NewtonRaphson
{
    public uint MaxIteration { get; set; } = 50;
    public double Epsilon { get; set; } = 0.000001;

    public double Solve(Func<double, double> f, Func<double, double> df, double initialGuess)
    {
        var xn = initialGuess;

        for (var i = 0; i < this.MaxIteration; i++)
        {
            var xn1 = xn - f.Invoke(xn) / df.Invoke(xn);

            if (Math.Abs(xn - xn1) < this.Epsilon)
            {
                return xn1;
            }

            xn = xn1;
        }

        return xn;
    }
}

Örneğin f(x) = x^2 - 2 fonksiyonun köklerini bulmak için, metodu aşağıdaki şekilde çağırabiliriz. Tahmini kök değeri olarak 1 seçilmiştir.

var solver = new NewtonRaphson();
var root = solver.Solve(x => x * x - 2, x => 2 * x, 1);

Benzer şekilde, f(x) = x - Cos(x) fonksiyonun köklerini bulmak için ise, metodu aşağıdaki şekilde çağırabiliriz. f(x) = 1 + Sin(x) fonksiyonun türevidir.

var solver = new NewtonRaphson();
var root = solver.Solve(x => x - Math.Cos(x), x => 1 + Math.Sin(x), 2);
Etiketler:  C#

Julia Fraktal Çizimi & C#

Fraktal; matematikte, çoğunlukla kendine benzeme özelliği gösteren karmaşık geometrik şekillerin ortak adıdır. En bilinen fraktal kümelerinden birisi olan Julia kümesinin C# ile oluşturulmuş hali aşağıdadır.

julia

using System.Drawing;
using System.Numerics;

namespace SG.Algoritma
{
    public class JuliaFractal
    {
        // Julia kümesinde, yarıçağı 2'den büyük her karmaşık sayı çemberi sonsuza götürmektedir.
        private const int MaxMagnitude = 2;

        // Maksimum iterasyon sayısı
        private const int MaxIterations = 1000;

        // Karmaşık sayı koordinat sisteminde, Julia kümesinin bölgesi.
        // Julia kümesinin sadece bir kısmını çizmek için farklı bir bölge verilebilir. 
        private static Complex AreaMin = new Complex(-2, -2);
        private static Complex AreaMax = new Complex(2, 2);

        private Complex C;

        public JuliaFractal(Complex c)
        {
            this.C = c;
        }

        /// <summary>
        /// Julia kümesi imajı oluşturuluyor
        /// </summary>
        /// <param name="dimension">Oluşacak imajın genişlik ve yükseklik değeri (Kare imaj oluşturulacak)</param>
        public Bitmap GenerateBitmap(int dimension)
        {
            return this.GenerateBitmap(dimension, JuliaFractal.AreaMin, JuliaFractal.AreaMax);
        }

        /// <summary>
        /// Julia kümesi imajı oluşturuluyor
        /// </summary>
        /// <param name="width">Oluşacak imajın genişliği. Yükseklik, çizilmek istenen bölgeyenin genişlik ve yükseklik değerlerine bakılarak belirlenecek.</param>
        /// <param name="areaMin">Karmaşık sayo kooordinat sisteminde, Julia kümesinin sadece belirli bir bölgeye karşılık düşen kısmı çizdirilmek istendiği zaman, bu bölgenin sol alt kösesi</param>
        /// <param name="areaMax">Sağ üst köşe</param>
        public Bitmap GenerateBitmap(int width, Complex areaMin, Complex areaMax)
        {
            var height = (int)(width * (areaMax - areaMin).Imaginary / (areaMax - areaMin).Real);

            // Boş bir bitmap oluştur
            var bitmap = new Bitmap(width, height);

            // Oluşturulacak imajın her piksel değerine karşılık düşen karmaşık sayı oluşturulacak.
            // Oluşturacağımız karmaşık sayıların, seçtiğimiz bölge içerisinde kalması gerekmektedir.

            var rScale = (areaMax - areaMin).Real / width;
            var iScale = (areaMax - areaMin).Imaginary / height;

            for (var x = 0; x < width; x++)
            {
                // Karmaşık sayısının real kısmı
                var real = areaMin.Real + x * rScale;

                for (var y = 0; y < height; y++)
                {
                    // Karmaşık sayısının imaginary kısmı
                    var imaginary = areaMin.Imaginary + y * iScale;

                    // Julia kümesi iterasyon değeri hesaplanıyor.
                    var iteration = this.CalculateIteration(new Complex(real, imaginary));

                    // Iterasyon değerine göre noktanın rengi ayarlanıyor.
                    bitmap.SetPixel(x, y, JuliaFractal.GetColor(iteration));
                }
            }

            return bitmap;
        }

        private int CalculateIteration(Complex z)
        {
            var iteration = 0;

            while (iteration < JuliaFractal.MaxIterations && z.Magnitude < JuliaFractal.MaxMagnitude)
            {
                z = z * z + this.C;
                iteration++;
            }

            return iteration;
        }

        /// <summary>
        /// // Iterasyona karşılık renk seçiliyor.
        /// </summary>
        private static Color GetColor(int iteration)
        {
            // Rasgele bir renk seçiliyor.
            // 256 tane rengin olduğu bir liste oluşturularak, listeden iteration % 256. renk de seçilebilir.
            // Ya da renk oluşturmak için farklı bir yöntem izlenebilir.

            return Color.FromArgb(0, iteration % 256, 0);
        }
    }
}

Julia kümesini fraktal resmini oluşturmak için, ilgili metot aşağıdaki şekilde çağrılabilir. Bu durumda en üstte yer alan resim oluşacaktır.

var fractal = new JuliaFractal(new Complex(0.285, 0.01));
var bitmap = fractal.GenerateBitmap(800);

bitmap.Save(@"D:\julia.png", ImageFormat.Png);

Julia fraktalının sadece belirli bir bölgesini çizdirmek için, ilgili metot aşağıdaki şekilde çağrılabilir. Böylece fraktalın istenilen bölgesi daha detaylı bir şekilde çizdirilebilir.

var bitmap = fractal.GenerateBitmap(800, new Complex(-0.85, 0.1), new Complex(-0.45, 0.37));

julia

Etiketler:  C#

Mandelbrot Fraktal Çizimi & C#

Fraktal; matematikte, çoğunlukla kendine benzeme özelliği gösteren karmaşık geometrik şekillerin ortak adıdır. En bilinen fraktal kümelerinden birisi olan Mandelbrot kümesinin C# ile oluşturulmuş hali aşağıdadır.

mandelbrot

using System;
using System.Drawing;
using System.Numerics;

namespace SG.Algoritma
{
    public class Fractal
    {
        // Mandelbort kümesinde, yarıçağı 2'den büyük her karmaşık sayı çemberi sonsuza götürmektedir.
        private const int MaxMagnitude = 2;

        // Maksimum iterasyon sayısı
        private const int MaxIterations = 1000;

        // Karmaşık sayı koordinat sisteminde, Mandelbort kümesinin bölgesi.
        // Mandelbort kümesinin sadece bir kısmını çizmek için farklı bir bölge verilebilir. 
        private static Complex AreaMin = new Complex(-2, -2);
        private static Complex AreaMax = new Complex(2, 2);

        /// <summary>
        /// Mandelbort kümesi imajı oluşturuluyor
        /// </summary>
        /// <param name="dimension">Oluşacak imajın genişlik ve yükseklik değeri (Kare imaj oluşturulacak)</param>
        public static Bitmap GenerateBitmap(int dimension)
        {
            return Fractal.GenerateBitmap(dimension, Fractal.AreaMin, Fractal.AreaMax);
        }

        /// <summary>
        /// Mandelbort kümesi imajı oluşturuluyor
        /// </summary>
        /// <param name="width">Oluşacak imajın genişliği. Yükseklik, çizilmek istenen bölgeyenin genişlik ve yükseklik değerlerine bakılarak belirlenecek.</param>
        /// <param name="areaMin">Karmaşık sayo kooordinat sisteminde, Mandelbort kümesinin sadece belirli bir bölgeye karşılık düşen kısmı çizdirilmek istendiği zaman, bu bölgenin sol alt kösesi</param>
        /// <param name="areaMax">Sağ üst köşe</param>
        public static Bitmap GenerateBitmap(int width, Complex areaMin, Complex areaMax)
        {
            var height = (int)(width * (areaMax - areaMin).Imaginary / (areaMax - areaMin).Real);

            // Boş bir bitmap oluştur
            var bitmap = new Bitmap(width, height);

            // Oluşturulacak imajın her piksel değerine karşılık düşen karmaşık sayı oluşturulacak.
            // Oluşturacağımız karmaşık sayıların, seçtiğimiz bölge içerisinde kalması gerekmektedir.
            
            var rScale = (areaMax - areaMin).Real / width;
            var iScale = (areaMax - areaMin).Imaginary / height;

            for (var x = 0; x < width; x++)
            {
                // Karmaşık sayısının real kısmı
                var real = areaMin.Real + x * rScale;

                for (var y = 0; y < height; y++)
                {
                    // Karmaşık sayısının imaginary kısmı
                    var imaginary = areaMin.Imaginary + y * iScale;

                    // Mandelbort kümesi iterasyon değeri hesaplanıyor.
                    var iteration = Fractal.CalculateIteration(new Complex(real, imaginary));

                    // Iterasyon değerine göre noktanın rengi ayarlanıyor.
                    bitmap.SetPixel(x, y, Fractal.GetColor(iteration));
                }
            }

            return bitmap;
        }

        private static int CalculateIteration(Complex c)
        {
            var z = new Complex();
            var iteration = 0;

            // MaxIterations adedince f(z) = z^2 + c işlemini uygula
            // İşlem sonucu Mandelbort kümesi içerisinde kalmaya devam ettiği sürece işlemi tekrarla
            while (iteration < Fractal.MaxIterations && z.Magnitude < Fractal.MaxMagnitude)
            {
                z = z * z + c;
                iteration++;
            }

            return iteration;
        }

        /// <summary>
        /// // Iterasyona karşılık renk seçiliyor.
        /// </summary>
        private static Color GetColor(int iteration)
        {
            // Rasgele bir renk seçiliyor.
            // 256 tane rengin olduğu bir liste oluşturularak, listeden iteration % 256. renk de seçilebilir.
            // Ya da, oluşan imajın tek renkten oluşmasını istiyorsak, Color.FromArgb(iteration % 256, 0, 0) rengi seçilebilir. Bu durumda kırmızı toplanda imaj oluşacaktır.

            return Color.FromArgb((iteration * iteration * iteration) % 256, (iteration * iteration) % 256, (iteration) % 256);
        }
    }
}

Mandelbrot kümesini fraktal resmini oluşturmak için, ilgili metot aşağıdaki şekilde çağrılabilir. Bu durumda en üstte yer alan resim oluşacaktır.

var bitmap = Fractal.GenerateBitmap(800);

bitmap.Save(@"D:\mandelbort.png", ImageFormat.Png);

Mandelbrot fraktalının sadece belirli bir bölgesini çizdirmek için, ilgili metot aşağıdaki şekilde çağrılabilir. Böylece fraktalın istenilen bölgesi daha detaylı bir şekilde çizdirilebilir.

var bitmap = Fractal.GenerateBitmap(800, new Complex(-0.4, -1.3), new Complex(0.1, -0.5));

mandelbrot

Etiketler:  C#

Monte Carlo İntegrali Alan Hesabı

Bir eğrinin altında yer alan alanı istatiksel bir yöntemle hesaplamak için Monte Carlo integral algoritması kullanılabilir. Bu algoritma ile, rasgele üretilen N adet noktanın kaç tanesinin fonksiyon eğrisinin altında yer aldığına bakılır. Rasgele seçilen noktaların yüzde kaçının eğri altında yer aldığına bakılarak, yaklaşık olarak alan hesabı yapılabilir.

Algoritma adımları aşağıdaki şekilde sıralanabilir:

  • Fonksiyonun verilen aralıktaki tüm değerlerini içine alacak şekilde bir dikdörtgen belirlenir.
  • Bu dörtgen içerisinde, N adet nokta rastgele olarak oluşturulur.
  • Bu noktaların ne kadarının, fonksiyonun belirlediği alanın altında olduğuna bakılır.
  • N değerinin, eğri altında olan nokta sayısına oranı, bize yaklaşık olarak, dikdörtgenin alanın fonksiyon eğrisi alanına oranını verecektir.

Aşağıda, Monte Carlo algoritmasının C# dilinde yazılmış kaynak kodu yer almaktadır.

using System;

namespace SG.Algoritma
{
    partial class MonteCarlo
    {
        // Deneme adet
        public uint N { get; set; }

        public MonteCarlo(uint n)
        {
            if (n == 0)
            {
                throw new ArgumentException(nameof(N));
            }

            this.N = n;
        }

        /// <summary>
        /// Verilen fonksiyon eğrisinin altında bulunan alan hesaplanıyor.
        /// </summary>
        /// <param name="func">Fonksiyon</param>
        /// <param name="x1">X ekseni üzerinde, aralık başlangıcı</param>
        /// <param name="x2">Aralık bitiş</param>
        public double CalculateArea(Func<double, double> func, double x1, double x2)
        {
            // Verilen aralıkta, fonksiyonun aldığı minimum ve maksimum değerler
            double min;
            double max;

            // Fonksiyonun minimum ve maksimum değeri hesaplanıyor
            this.CalculateMinMaxValue(func, x1, x2, out min, out max);

            // Denemelerden kaç tanesi, fonksiyon eğrisinin altında
            var hit = 0;

            // Rasgele sayı üretici
            var rand = new Random();

            // N adet dememe yap
            for (int i = 0; i < this.N; i++)
            {
                // Dikdörtgen içerisinde rasgele bir nokta üret
                var x = x1 + (x2 - x1) * rand.NextDouble();
                var y = min + (max - min) * rand.NextDouble();

                // Rasgele seçilen nokta ve fonksiyonun değeri, eğrinin aynı tarafındaysa. (İki negatif sayının çarpımı pozitiftir)
                if (func(x) * y > 0)
                {
                    // Fonksiyon değeri pozitifse
                    if (func(x) > 0)
                    {
                        // Rasgele üretilen y değeri fonsiyon eğrisinin altındaysa
                        if (func(x) > y) hit++;
                    }
                    else
                    {
                        // Rasgele üretilen y değeri fonsiyon eğrisinin üstündeyse
                        if (y < 0 && func(x) < y) hit++;
                    }
                }
            }

            var areaRectangle = Math.Abs(x2 - x1) * (max - min);

            // Seçilen rasgelen noktaların yüzde hit / N kadarı dikdörtgenin içerisinde.
            // Noktaların yüzde kaçının dikdörtgen içerisinde olduğuna bakılarak alan hesabı yapılıyor.

            return areaRectangle * (double)hit / this.N;
        }

        /// <summary>
        /// Verilen aralıkta, fornksiyonun minimum ve maksimum değerleri hesaplanıyor.
        /// </summary>
        /// <param name="func">Fonksiyon</param>
        /// <param name="x1">Aralık başlangıç</param>
        /// <param name="x2">Aralık bitiş</param>
        /// <param name="min">Hesaplanan minimum değer</param>
        /// <param name="max">Hesaplanan maksimum değer</param>
        private void CalculateMinMaxValue(Func<double, double> func, double x1, double x2, out double min, out double max)
        {
            min = double.MaxValue;
            max = double.MinValue;

            // Aralık N parçaya bölünüyor.
            var h = (x2 - x1) / this.N;

            // Verilen aralıkta, N adet nokta için, her bir noktanın fonksiyon değeri hesaplanıyor.
            for (int i = 0; i <= this.N; i++)
            {
                var x = x1 + i * h;
                var y = func(x);

                if (y < min) min = y;
                if (y > max) max = y;
            }
        }
    }
}

Monte Carlo alan hesabı algoritması ile, istediğiniz fonksiyon grafiği altında yer alan bölgenin alanını çok rahat bir şekilde hesaplayabiliriz. Fonksiyonun ne kadar karmaşık olduğunu bir önemi yok. Örneğin f(x) = x - sin(x) - 1 fonksiyon eğrisinin x ekseni {0,3} aralığındaki alanı hesaplamak için, alan hesaplama metodunu aşağıdaki gibi çalıştırabiliriz.

var mc = new MonteCarlo(1000);
var area = mc.CalculateArea(x => x - Math.Sin(x) - 1, 0, 3);

Bu durumda aşağıdaki eğri altında yer alan alan yaklaşık olarak hesaplanacaktır. Daha hassas bir hesaplamak için N değerinin artırılması gerekmektedir.

Monte Carlo Integration

Aynı algoritmada yapılacak küçük bir değişiklikle, fonksiyonun integral değeri de rahatlıkla hesaplanabilir. İntegral hesabında, pozitif alanlardan negatif alanlar çıkarılacağı için, bu alanlara düşen noktalar ayrı ayrı sayılır.

Etiketler:  C#

Kategoriler

Algoritma (5), Cheat Sheet (2), Framework (3), İpucu (4), Kendime Not (1), Kitap (4), Kod (5), Matematik (1), Proje (5), Veritabanı (3), Workshop (3)

Etiketler

C# (12) HTML (1) JavaScript (2) SQL (3)

İngilizce / Türkçe

İngilizce / Türkçe kelime listesi kendime not