Integer (`Int64`) factorization: Julia code is extremely slow

General Usage Performance
7

Thank you all for your suggestions and ideas!
I’m pretty satisfied with the runtime performance of this Julia code (compared w.r.t. C++). Here are the complete codes and performance measurements, which were carried out on a single CPU core of AMD EPYC 7763.

  • Julia code
using BenchmarkTools

# brute-force integer factorization
function bruteforce(n)
  T        = typeof(n)
  kZero::T = 0
  kOne::T  = 1
  kTwo::T  = 2
  factors  = T[]

  d::T = kTwo
  while d * d <= n
    while (kZero == n % d)
      push!(factors, d)
      n = n ÷ d
    end
    d = d + kOne
  end
  (n > kOne) && push!(factors, n)
  return factors
end

function main()
  n = 239809320265259
  factors = bruteforce(n)
  for i in factors
    println(i)
  end
  t = @belapsed $factors = bruteforce($n)
  println("brute-force integer factorization: ", t, " sec")
end

main()

#
# Arbitrary-precision integer is not easily direct available in C++.
#
function main_bigint()
  n = big"6152070006351663475873543067335467145098219"
  factors = bruteforce(n)
  for i in factors
    println(i)
  end
  t = @belapsed $factors = bruteforce($n)
  println("brute-force integer factorization: ", t, " sec")
end

println("\nArbitrary-precision integer is not easily direct available in C++.\n")

main_bigint()
  • C++ code
#include <iostream>
#include <vector>
#include <cstdint>
#include <chrono>

using Int = int64_t;

// brute-force integer factorization
std::vector<Int> bruteforce(Int n) {
  constexpr Int kZero { 0 };
  constexpr Int kOne  { 1 };
  constexpr Int kTwo  { 2 };
  std::vector<Int> factors;

  Int d { kTwo };
  while (d * d <= n) {
    while (kZero == n % d) {
      factors.push_back(d);
      n = n / d;
    }
    d = d + kOne;
  }
  if (n > kOne) factors.push_back(n);
  return factors;
}

int main(void)
{
  Int n { 239809320265259 };
  std::vector<Int> factors = bruteforce(n);
  for (auto i : factors) {
    std::cout << i << std::endl;
  }
  auto start = std::chrono::high_resolution_clock::now();
  factors = bruteforce(n);
  auto stopp = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double, std::milli> wtime = stopp - start;
  std::cout << "brute-force integer factorization: " << wtime.count() * 1.0e-3 << " sec"
            << std::endl;
  return 0;
}
  • performance measurements on one CPU core of AMD EPYC 7763
# C++ (g++ (GCC) 11.3.0)
brute-force integer factorization: 0.0309446 sec
# Julia (julia version 1.10.4)
brute-force integer factorization: 0.030796567 sec
Arbitrary-precision integer is not easily direct available in C++.

3
7
7
13
17
383
1427
6959
20023
379369
979337
2345957
2852981
brute-force integer factorization: 0.587531295 sec
1 Like