Ordinal bir algoritma kullanmadan asal test fonksiyonu yazmak mümkün mü?

[Aang]

Asal sayıları bilirisiniz, 1'den ve kendinden başka hiçbir tam sayıya tam olarak bölünemeyen özel sayılardır. Aslın da bölünür de sonuç tam sayı çıkmaz :)) Bu da ayrı tespit olsun. Onları tespit etmek için pek çok algoritma hazırlandı ancak uzun bir liste elde etmek için başında saatlerce beklemeniz gerekir çünkü ya sayının kareköküne kadar olan sayılarla mod alma işlemi yaparak ya da bir elek kullanıp composite sayıları işaretleyip kalanları asal olarak bir liste halinde vererek çalışıyorlar. Asal sayıların sıralı bir listesini en verimli şekilde elde eden algoritma Sieve Eratesthones algoritmasıdır.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Ancak bu yöntemde en baştan başlamanız gerekir ve sıralı olarak tüm asalları elde etmeye devam ederek hedeflediğin sayının kare köküne kadar olan sayıları kontrol etmeniz sayının asal olup olmadığını belirlemek için mecburidir.

Halbuki ben herhangi bir sayının (Bu kodda 2 ^ 64'de kadar olan sayıların) asal olup olmadığını sıralı (ordinal) bir algoritma kullanmadan da belirleyebiliyorum. Bunun için Fermat asallık testini ve bazı sahte asalları kullanıyorum.

Şimdi diyebilirsiniz; "Fermat asallık testi zaten kullanılan bir algoritmadır"

Evet doğru ancak sayının asal olmadığını kesin olarak verebilse de sayının asal olduğunu belirttiği bazı durumlarda kesin sonuç veremiyor çünkü algoritma sahte asalları da asal sayı olarak algılıyor ve true döndürüyor.

Bu sorunun da üstesinden gelmek için klasik bir Fermat asallık testinden sonra sayının bir pseudo(sahte) prime olup olmadığını da ilgili sayıların sıralı bir listesinde Binary Search yöntemiyle sorgulayıp kesin sonucu verebiliyorum. Biliyorsunuz ki Binary Search sıralı bir listede işlem yapsa da listeyi sıralı olarak dolaşmaz ve sayının listede olup olmadığını çok hızlı bir şekilde belirleyebilir.

Ancak şöyle bir sorun var; bu liste, sadece odd psedo prime listesi ve bazı çift olan sahte asallar da var ve onların bir listesine aslında ihtiyacımız yok. Çünkü 2'den büyük tüm asal sayılar tek sayıdır ve çift sayıları elersek böyle bir listede sorgulama yapmaya gerek kalmaz.

Algoritma şöyle çalışıyor;

1. Sayı 2'ye eşitse "true" döndür.

2. Sayı 2'den küçük bir sayı veya çift bir sayıysa "false" döndür.

3. Fermat asallık testini uygula ve 2 sonucunu döndürüyorsa (Fermat Little Theorem)(a ^ N mod N ≡ a) sayının listede olmadığını doğrula ve "true" döndür.

4. 3. maddedeki koşullar sağlanmamış olursa kod buraya düşer ve doğrudan "false" döndür.

Kod ilk çalıştırıldığında pseudo primelerin bir listesini download eder. Bu sıkıştırılmış text dosyası yaklaşık 884 MB yer tutar. Bu biraz uzun sürebilir ancak kod sonra bu sıkıştırılmış dosyadaki text formatındaki sahte asalları binary bir dosyaya yazar ve artık asal testleri için bu dosyayı kullanır ve daha sonraki testlerinizde sayıları bu dosyadan hızla yükler.

Kod harici olarak SharpZipLib kütüphanesini ve .NET Core 7 versiyonunu kullanır. Kodu test etmek için uygun Visual Studio sürümünüz varsa test edebilirsiniz. Şu an en son sürüm 22 ve indirerek test edebilirsiniz. Sadece .NET Core 7 SDK yükleyerek Linux ya da MacOS makinelerinizde de test edebilirsiniz.

Bu dünyada henüz olmayan ve kullanılmayan bir algoritmadır. Varsa paylaşabilirsiniz. Çünkü anladığım kadarıyla matematiksel izahını anlamış benden başka bir insan henüz yok, bunu da tartışabiliriz. Bu uyumsuz sayıları Carmichael sayıları olarak grupluyorlar ancak zaten bir sayı asalsa ve a'yı 2 olarak alırsan bu listede yoksa asal bir sayıdır çünkü tüm asallar Fermat asallık testinde "true" döndürür ve sayının bir pseudo prime olup olmadığını sınamak doğru çalışan bir asallık testi için yeterlidir.
 

using System;
using System.IO;
using System.IO.Compression;
using System.Net;
using ICSharpCode.SharpZipLib.BZip2;

public class PrimeTester
{
    private static ulong[] Pseudos;

    public static void Main()
    {
        // Dosyadan Pseudos dizisini doldur
        LoadPseudosArray();

        Console.WriteLine("Prime numbers list up to 100K");

        for(ulong i = 0; i < 100000UL; i++)
            if(IsPrime(i))
                Console.WriteLine(i.ToString());
    }

    private static void LoadPseudosArray()
    {
        string binaryFilePath = "pseudos.bin";

        if (!File.Exists(binaryFilePath))
        {
            // İlk defa çalıştırıldığında text dosyasından oku ve binary dosyaya yaz
            DownloadAndWriteBinaryFile();
        }

        Console.WriteLine("Loading pseudo primes...");
        // Binary dosyasından oku
        using (FileStream fileStream = File.OpenRead(binaryFilePath))
        using (BinaryReader binaryReader = new BinaryReader(fileStream))
        {
            int arrayLength = binaryReader.ReadInt32();
            Pseudos = new ulong[arrayLength];

            for (int i = 0; i < arrayLength; i++)
            {
                Pseudos[i] = binaryReader.ReadUInt64();
            }
        }

    }

    private static void DownloadAndWriteBinaryFile()
    {
        string url = "https://www.cecm.sfu.ca/Pseudoprimes/psps-below-2-to-64.txt.bz2";
        string tempFilePath = "pseudos.txt.bz2";
        string binaryFilePath = "pseudos.bin";

        Console.WriteLine("Downloading pseudo primes...");

        using (WebClient client = new WebClient())
        {
            client.DownloadFile(url, tempFilePath);
        }

        Console.WriteLine("Extracting pseudo primes...");

        // Dosyayı oku ve binary dosyaya yaz
        using (FileStream fileStream = File.OpenRead(tempFilePath))
        using (BZip2InputStream bzip2Stream = new BZip2InputStream(fileStream))
        using (StreamReader reader = new StreamReader(bzip2Stream))
        using (FileStream binaryFileStream = File.Create(binaryFilePath))
        using (BinaryWriter binaryWriter = new BinaryWriter(binaryFileStream))
        {
            while (!reader.EndOfStream)
            {
                string line = reader.ReadLine();
                ulong pseudo = ulong.Parse(line);
                binaryWriter.Write(pseudo);
            }
        }

        Console.WriteLine("Pseudo binary file is ready!");

        // Geçici dosyayı sil
        // File.Delete(tempFilePath);
    }

    // ARICAN Primallity Test Function
    private static bool IsPrime(ulong number)
    {
        if (number == 2)
        {
            return true;
        }

        if (number < 2 || number % 2 == 0)
        {
            return false;
        }

        if (ModPow(2, number, number) == 2)
        {
            // Pseudo-prime kontrolü
            if (Array.BinarySearch(Pseudos, number) < 0)
            {
                return true;
            }
        }

        return false;
    }

    private static ulong ModPow(ulong baseNumber, ulong exponent, ulong modulus)
    {
        ulong result = 1;

        while (exponent > 0)
        {
            if (exponent % 2 == 1)
            {
                result = (result * baseNumber) % modulus;
            }

            exponent >>= 1;
            baseNumber = (baseNumber * baseNumber) % modulus;
        }

        return result;
    }
}

 

[Kovulmuş Üye]

Cevap , mümkün değil. 12 li sayı sistemi kullanırsan belki. Şu an 9 rakamli onluk sistem var. 11 rakamlı 12 lik sisteme geçersen başarırsın.

[Aang]

14 dakika önce, Kafir İmam yazdı:

Cevap , mümkün değil. 12 li sayı sistemi kullanırsan belki. Şu an 9 rakamli onluk sistem var. 11 rakamlı 12 lik sisteme geçersen başarırsın.

Paylaşımı okumamışsın decimal sayılar için bir çözüm önerdim ki sayı sistemi, sayının asal olup olmadığını belirleyen bir durum değil ya da hangi sayı sistemini kullandığından bağımsız olarak asallık testi için sadece onluk sistemi kullanmak yeterli! Tüm açıklamayı ve kodu ilk iletimde paylaştım.

[Kovulmuş Üye]

2 dakika önce, John-Ahmet yazdı:

Paylaşımı okumamışsın decimal sayılar için bir çözüm önerdim ki sayı sistemi, sayının asal olup olmadığını belirleyen bir durum değil ya da hangi sayı sistemini kullandığından bağımsız olarak asallık testi için sadece onluk sistemi kullanmak yeterli! Tüm açıklamayı ve kodu ilk iletimde paylaştım.

Sen bilgisayar mantığını anlammissin , bilgisayar tamsayıyi bile bulamaz. Toplam serilerinde 1.99999999... 9 sonucunu ta ki sen bunu 2 yap kodunu girene kadar. Asallik testini de sen tamam diyene kadar yapmaya devam eder

[Aang]

28 dakika önce, Kafir İmam yazdı:

Sen bilgisayar mantığını anlammissin , bilgisayar tamsayıyi bile bulamaz. Toplam serilerinde 1.99999999... 9 sonucunu ta ki sen bunu 2 yap kodunu girene kadar. Asallik testini de sen tamam diyene kadar yapmaya devam eder

Sayıları ekranda gösterirken "onluk sistemi kullanıyor" demek istedim. Yoksa diğer sayı sistemlerinde görmek için o sayı sistemlerindeki sembolik gösterimle de listeleyebilirsiniz.

Bilgisayar mantığını anlamıyorum ancak dünyada ilk olan bir algoritma geliştirebiliyorum. Bu sence de ilginç değil mi? Sana sayı sisteminin sayının asallık testinde önemsiz olduğunu açıkladım. Bu da ayrı bir önermeydi ve benim tecrübem hakkında bilgi veriyordu. Sayıların sembolik bir gösteriminin asal test fonksiyonumla doğrudan bir ilgisi yok ancak gösterimi onluk sistemde veriyorum.

Temel kodu burada kısaca tekrar belirtelim;

 

    // ARICAN Primallity Test Function
    private static bool IsPrime(ulong number)
    {
        if (number == 2)
        {
            return true;
        }

        if (number < 2 || number % 2 == 0)
        {
            return false;
        }

        if (ModPow(2, number, number) == 2)
        {
            // Pseudo-prime kontrolü
            if (Array.BinarySearch(Pseudos, number) < 0)
            {
                return true;
            }
        }

        return false;
    }

    // for Fermat primallity test - ModPow function
    private static ulong ModPow(ulong baseNumber, ulong exponent, ulong modulus)
    {
        ulong result = 1;

        while (exponent > 0)
        {
            if (exponent % 2 == 1)
            {
                result = (result * baseNumber) % modulus;
            }

            exponent >>= 1;
            baseNumber = (baseNumber * baseNumber) % modulus;
        }

        return result;
    }

 

[Aang]

Kodda bir düzenleme; LoadPseudosArray metodundaki
 

int arrayLength = binaryReader.ReadInt32();

satırını
 

// Binary dosyasının boyutunu al
long fileSize = new FileInfo(binaryFilePath).Length;
int arrayLength = (int)(fileSize / 8);

olarak güncelleyin!