I have been struggling for speed and haven't found anything useful online. I'm also using boost::multiprecision 1024 bit integers. What's the fastest possible way to find all of the multiples for such large numbers?

I have tried:

• looping from 1 to square root of the number
• incrementing by 2 if the number is odd
• keeping everything I can out of the loop
• compiling in release mode (vs2019)

Here's my code so far.

#include <iostream>
#include <time.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace boost::multiprecision;

void multiples()
{
    __int64 startthing, endthing;
    __int64 freq = _Query_perf_frequency();

    int1024_t divisor = 0, thing = 0;

    while (1)
    {
        //displayer.join();
        cout << "\nEnter a number\n";
        cin >> thing;

        if (thing == 0 && !cin.fail())
            break;
        cout << endl;

        while (cin.fail())
        {
            cout << "I said integer you rule breaker\n";

            // get rid of failure state
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cin >> thing;
        }

        int1024_t limit = sqrt(thing);
        int1024_t step = (thing & 1 ? 2 : 1); // odd number = odd factors
        startthing = _Query_perf_counter();   // start timer

        for (int1024_t i = 1; i <= limit; i  = step) 
        {
            if ((thing % i) == 0)
            {
                divisor = thing / i;
                cout << i << ", " << divisor << "\n";
            }
        }
        endthing = _Query_perf_counter();

        cout << "\nThat took " << (endthing - startthing) / (double)freq << " seconds.\n";
    }
}

CodePudding user response：

The best approach here is probably to calculate the prime factorization of the number and then printing out the products of all possible combinations of those prime factors.

Here's a implementation without much optimization using uint64_t instead of multiprecision that completes within 305 ms for input 10,000,000,000,000,000 on my machine.

Note that the preformance will get significantly worse for a larger number of distinct prime factors. (12132 ms for the product of the smallest 14 primes). This is caused by the fact that there are just more combinations to calculate/print.

#include <chrono>
#include <iostream>
#include <utility>
#include <vector>

using PrimeFactors = std::vector<std::pair<uint64_t, uint64_t>>;

std::vector<std::pair<uint64_t, uint64_t>> FindFactors(uint64_t n)
{
    PrimeFactors primeFactors;

    uint64_t square = static_cast<uint64_t>(std::sqrt(n));
    for (uint64_t i = 2; i <= square && i <= n;   i)
    {
        bool isPrime = true;
        for (auto [prime, exponent] : primeFactors)
        {
            if (prime * prime > i)
            {
                break;
            }
            if (i % prime == 0u)
            {
                isPrime = false;
                break;
            }
        }

        if (isPrime)
        {
            uint64_t count = 0;
            while (n % i == 0)
            {
                  count;
                n /= i;
            }
            primeFactors.emplace_back(i, count);
            if (count != 0)
            {
                square = static_cast<uint64_t>(std::sqrt(n));
            }
        }
    }
    if (n != 1)
    {
        primeFactors.emplace_back(n, 1);
    }
    return primeFactors;
}

void PrintFactors(uint64_t factor, PrimeFactors::const_iterator pos, PrimeFactors::const_iterator const end)
{
    while (pos != end)
    {
        while (pos != end && pos->second == 0)
        {
              pos;
        }
        auto newFactor = factor;
        for (auto count = pos->second; count != 0; --count)
        {
            newFactor *= pos->first;
            std::cout << newFactor << '\n';
            PrintFactors(newFactor, pos   1, end);
        }
          pos;
    }
}

int main()
{
    using Clock = std::chrono::steady_clock;

    uint64_t const input = 10'000'000'000'000'000ull;
    //uint64_t const input = 2ull * 3ull * 5ull * 7ull *11ull * 13ull *17ull * 19ull * 23ull * 29ull *31ull*37ull * 41ull*43ull;

    auto start = Clock::now();
    auto factors = FindFactors(input);

    // print
    std::cout << 1 << '\n';
    PrintFactors(1, factors.begin(), factors.end());
    auto end = Clock::now();
    std::cout << "took " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms\n";
}

CodePudding user response：

Potential bug

int1024_t limit = sqrt(thing); risks imprecision with as it employs FP math with less precision than int1024_t.

A good compiler calculates nearby a % b and a / b for about the same time cost a % b alone.

So instead of i <= limit.

    // for (int1024_t i = 1; i <= limit; i  = step) 
    for (int1024_t i = 1; i <= thing/i; i  = step) 
    {
        if ((thing % i) == 0)
    ...

Factor

A more complex approach, but speeds things up is to reduce thing by each factor found. With 72, form the set 1,2,2,2,3,3 to report the factors. This quickly avoids many iterations for composite numbers - does nothing for primes.

Better to have a list of primes - either initial fixed - or calculated as you go, to discern the next division candidate.