2

我写了一个简单的单线程应用程序来检查给定的数字是否是素数。它旨在支持任意大的整数，所以我在 C# 中使用了BigInteger类。这是代码：

using System;
using System.Diagnostics;
using System.Numerics;

namespace PrimeChecker {
    public static class Program {
        /// <summary>
        /// Gets the number of threads that parallel loops will use from the thread pool when called.
        /// </summary>
        private static BigInteger MinusOne = BigInteger.MinusOne,
            Zero = BigInteger.Zero,
            One = BigInteger.One,
            Two = new BigInteger(2),
            Three = new BigInteger(3),
            Five = new BigInteger(5),
            Six = new BigInteger(6);

        public static void Main(string[] args) {
            string value = args.Length == 0 ? null : args[0];
            BigInteger num, factor;
            Stopwatch elapsed = new Stopwatch();
            do {
                if (value == null) {
                    Console.Write("\nEnter integer to check if prime (or blank to exit): ");
                    value = Console.ReadLine();
                }
                if (value.Length == 0)
                    return;
                value.Trim();
                if (BigInteger.TryParse(value, out num)) {
                    Console.Write("Checking...");
                    elapsed.Restart();
                    if (num.IsZero)
                        Console.WriteLine("nope, divisible by 0. :/ (elapsed: 0ms)");
                    else if (num.IsOne)
                        Console.WriteLine("nope, divisible by 1. :/ (elapsed: 0ms)");
                    else {
                        factor = IsPrime(num);
                        elapsed.Stop();
                        if (factor.IsOne)
                            Console.WriteLine("prime! :D (elapsed: " + elapsed.Elapsed.ToString() + ")");
                        else
                            Console.WriteLine("nope, divisible by at least " + factor + " and " + (num / factor) + ". :/ (elapsed: " + elapsed.Elapsed.ToString() + ")");
                    }
                } else
                    Console.WriteLine("Not a valid integer... :*");
                value = null;
            } while (true);
        }

        private static BigInteger LogBase2(BigInteger num) {
            if (num <= Zero)
                return MinusOne; //does not support negative values
            BigInteger i = Zero;
            while (!(num >>= 1).IsZero)
                i++;
            return i;
        }

        public static BigInteger Sqrt(this BigInteger num) {
            if (num.IsZero)
                return Zero;
            else if (num.IsOne)
                return One;
            else if (num.Sign > 0) {
                BigInteger root = LogBase2(num);
                BigInteger lowerBound;
                while (num < (lowerBound = root * root) || num > lowerBound + root + root) {
                    root += num / root;
                    root >>= 1;
                }
                return root;
            } else
                return MinusOne;
        }

        /// <summary>
        /// Returns 0 if num is 0, 1 if the value is prime or 1, -1 if the value is negative,
        /// else returns the smallest factor of the num.
        /// </summary>
        /// <param name="num">The integer to check if prime.</param>
        public static BigInteger IsPrime(BigInteger num) {
            if (num.IsZero)
                return Zero;
            else if (num.Sign < 0)
                return MinusOne;
            else if (num <= Three || num == Five)
                return One;
            else if (num.IsEven)
                return Two;
            else if ((num % Three).IsZero)
                return Three;
            BigInteger root = Sqrt(num);
            if (!root.IsEven)
                root++;
            BigInteger i = Five;
            while (i < root && !((num % i).IsZero || (num % (i += Two)).IsZero)) //main loop here
                i += Four;
            return i < root ? i : One;
        }
    }
}

但是，我想研究用 C++ 编写相同的应用程序。我设法通过使用 Windows 上的MPIR库来实现这一点。完整的代码代码和 Visual Studio 项目可以在 GitHub 上找到：https ://github.com/mathusummut/PrimeCheckerCpp ，但这里是主循环：

while (mpz_cmp(i, root) == -1) {  //loop is here
    mpz_mod(temp, num, i);
    if (mpz_sgn(temp) == 0)
        break;
    mpz_add_ui(i, i, 2u);
    mpz_mod(temp, num, i);
    if (mpz_sgn(temp) == 0)
        break;
    mpz_add_ui(i, i, 4u);
}

当我运行 C# 可执行文件以检查是否2305843009213693951为素数时，我得到以下输出：

Enter integer to check if prime (or blank to exit): 2305843009213693951
Checking...prime! :D (elapsed: 00:00:52.2468554)

而当我运行 C++ 可执行文件时，我得到以下输出：

Enter integer to check if prime (or blank to exit): 2305843009213693951
Checking...prime! :D (elapsed: 60.429640s)

为什么 C++ 实现较慢？MPIR 库在这里有问题，还是我做错了什么？

注意：两者都在 64 位发布模式下编译和测试，启用了完全优化，没有附加调试器。

注意：@hatchet 是对的，当我尝试使用 64 位无法表示的整数时，C++ 实现更快。比如trying 108446744073709551647，C#版本用了13.5分钟，而C++版本只用了6.5分钟！

4

0 回答 0