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

**URL:** <https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819>\
**Category:** Performance\
**Created:** [August 4, 2024, 6:12pm UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819 "2024-08-04T18:12:27Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![xinwu](https://avatars.discourse-cdn.com/v4/letter/x/a4c791/32.png) [@xinwu](https://discourse.julialang.org/u/xinwu)\
**Post date:** [August 4, 2024, 6:12pm UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/1 "2024-08-04T18:12:27Z")

</div>

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!

```c++
#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;
}

```

```julia
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()

```

---

<div class="post-metadata">

**Author:** ![xinwu](https://avatars.discourse-cdn.com/v4/letter/x/a4c791/32.png) [@xinwu](https://discourse.julialang.org/u/xinwu)\
**Post date:** [August 4, 2024, 6:21pm UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/2 "2024-08-04T18:21:52Z")

</div>

Problem found… the for-loop syntax in Julia…

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 4, 2024, 6:28pm UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/3 "2024-08-04T18:28:04Z")

</div>

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
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

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 4, 2024, 6:30pm UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/4 "2024-08-04T18:30:04Z")

</div>

> [@xinwu](#):
>
> ```julia
> while (kZero == n % d)
> push!(factors, d)
> n = n ÷ d
> end
> 
> ```

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

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [August 4, 2024, 6:36pm UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/5 "2024-08-04T18:36:52Z")

</div>

> [@xinwu](#):
>
> ```julia
> const kZero = 0
> const kOne = 1
> const kTwo = 2
> 
> ```

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.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 5, 2024, 1:40am UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/6 "2024-08-05T01:40:25Z")

</div>

> [@xinwu](#):
>
> Problem found… the for-loop syntax in Julia…

~~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.

---

<div class="post-metadata">

**Author:** ![xinwu](https://avatars.discourse-cdn.com/v4/letter/x/a4c791/32.png) [@xinwu](https://discourse.julialang.org/u/xinwu)\
**Post date:** [August 5, 2024, 9:39am UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/7 "2024-08-05T09:39:43Z")

</div>

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

```julia
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

```cpp
#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

```julia
# 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

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 5, 2024, 11:24am UTC](https://discourse.julialang.org/t/integer-int64-factorization-julia-code-is-extremely-slow/117819/8 "2024-08-05T11:24:37Z")

</div>

> [@xinwu](#):
>
> `Arbitrary-precision integer is not easily direct available in C++.`

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