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

General Usage Performance
1

Hi, are there any mistakes in my Julia code for integer (Int64) factorization?

  • C++ code finishes instantly.
  • Julia code seems to run forever.

Here are the codes. Thank you for your hints!

#include <iostream>
#include <vector>
#include <cstdint>

constexpr int64_t kZero { 0 };
constexpr int64_t kOne  { 1 };
constexpr int64_t kTwo  { 2 };

std::vector<int64_t> bruteforce(int64_t n) {
  std::vector<int64_t> factors;
  for (int64_t d { kTwo }; d <= n; d++) {
    while (kZero == n % d) {
      factors.push_back(d);
      n /= d;
    }
  }
  if (n > kOne) factors.push_back(n);
  return factors;
}

int main(void)
{
  int64_t n { 239809320265259 };
  std::vector<int64_t> factors = bruteforce(n);
  for (auto i : factors) {
    std::cout << i << std::endl;
  }
  return 0;
}

const kZero = 0
const kOne  = 1
const kTwo  = 2

function bruteforce(n)
  factors = Int64[]
  for d in kTwo:n
    while (kZero == n % d)
      push!(factors, d)
      n = n ÷ d
    end
  end
  n > kOne && push!(factors, n)
  return factors
end

# this is 64-bit Linux
function main()
  n = 239809320265259
  factors = bruteforce(n)
  for i in factors
    println(i)
  end
end

main()
2

Problem found… the for-loop syntax in Julia…

3

Note that even after fixing the loop to break when the reduced n is reached, Primes.jl can still give you a ~1300x speedup:

julia> using Primes, BenchmarkTools
julia> @btime bruteforce(239809320265259)
  101.140 ms (2 allocations: 144 bytes)
2-element Vector{Int64}:
 15485773
 15485783

julia> @btime factor(239809320265259)
  72.110 μs (1 allocation: 128 bytes)
15485773 * 15485783
8 Likes
4

Instead of calculating div and rem separately, you can use the divrem function. It should be a bit faster.

3 Likes
5

I’m sure why you prefer this to just using the literal values, but I believe there are cases where literal values can be more efficient. Maybe not in your code, but x^2 will be replaced by x * x, while x^kTwo probably won’t.

The literal values also seem more readable, imo.

2 Likes
6

Can you elaborate? I don’t know C++ and your versions look equivalent nvm I see now that the for (int64_t d { kTwo }; d <= n; d++) loop stops when n is divided to less than d, whereas for d in kTwo:n instantiates an unchanged range to iterate over.

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
8

Could try GMP, that’s what Julia partially wraps for BigInt, according to the docs.