Clever Geek Handbook

Calculation of the BigInteger product []

Context: I am trying to compute factorials for very large n using the BigInteger class in Java (for n> 100,000) and so far this is what I am doing:

  • Produce all primes less than or equal to n using Sieve of Erastons

  • Find what powers they will be elevated to.

  • Raise all numbers to their respective capacities.

  • Use the recursive divide and conquer method to multiply them.

From research I did online, this is asymptotically faster than just multiplying all k by n. However, I noticed that the slowest part of my implementation is the part where I multiply all the core powers. My questions:

  • Is there a faster way to calculate the product of a set of numbers?
  • Can my implementation be improved?

code:

public static BigInteger product(BigInteger[] numbers) {
    if (numbers.length == 0)
        throw new ArithmeticException("There is nothing to multiply!");
    if (numbers.length == 1)
        return numbers[0];
    if (numbers.length == 2)
        return numbers[0].multiply(numbers[1]);

    BigInteger[] part1 = new BigInteger[numbers.length / 2];
    BigInteger[] part2 = new BigInteger[numbers.length - numbers.length / 2];
    System.arraycopy(numbers, 0, part1, 0, numbers.length / 2);
    System.arraycopy(numbers, numbers.length / 2, part2, 0, numbers.length - numbers.length / 2);

    return product(part1).multiply(product(part2));
}
  • Note that BigInteger uses the karatsuba algorithm for multiplication.
  • I know there are many questions about calculating factorials. But my question is about calculating the BigIntegers product for which there are not many resources. (I saw someone say "Use Divide and Conquer method", but I don't remember where, and I didn't see any implementation around.
+3


source to share


3 answers


One way to improve performance is to do the following:

  • Sort the array of numbers to be multiplied.
  • Create two new lists: a

    and b

    .
  • For each number in the entry list to be multiplied, it may appear more than once. Let's say the number v_i

    appears n_i

    once. Then add v_i

    to a

    n_i / 2

    fold (rounded off). If n_i

    odd, add v_i

    once per b

    .
  • To calculate the result, run:
BigInteger A = product(a);
BigInteger B = prudoct(b);
return a.multiply(a).multiply(b);


To see how this works, consider your input array [2, 2, 2, 2, 3, 3, 3]. So there are four 2s and three 3s. Arrays a

and b

respectively will be

a = [2, 2, 3]
b = [3]

Then you will recursively call the computation of the product from them. Note that we have reduced the number of numbers we want to multiply from 7 by 4 by almost half. The trick here is that for numbers that occur many times, we can only compute the product of half of them and then raise that to a power of two. Very similar to how you can calculate the cardinality of a number in O(log n)

time.

+1


source


I suggest another idea, pow's algorithm is very fast, you can calculate all prime numbers with exponent, for example:

11! -> {2^10, 3^5, 5^2, 7^1, 11^1}


You can calculate all the primes forces and then use divide and conquer to multiply all of them. Implementation:

private static BigInteger divideAndConquer(List<BigInteger> primesExp, int min, int max){
    BigInteger result = BigInteger.ONE;
    if (max - min == 1){
        result = primesExp.get(min);
    } else if (min < max){
        int middle = (max + min)/2;
        result = divideAndConquer(primesExp, min, middle).multiply(divideAndConquer(primesExp, middle, max));
    }
    return result;
}

public static BigInteger factorial(int n) {
    // compute pairs: prime, exp
    List<Integer> primes = new ArrayList<>();
    Map<Integer, Integer> primeTimes = new LinkedHashMap<>();
    for (int i = 2; i <= n; i++) {
        int sqrt = Math.round((float) Math.sqrt(i));
        int value = i;
        Iterator<Integer> it = primes.iterator();
        int prime = 0;
        while (it.hasNext() && prime <= sqrt && value != 0) {
            prime = it.next();
            int times = 0;
            while (value % prime == 0) {
                value /= prime;
                times++;
            }
            if (times > 0) {
                primeTimes.put(prime, times + primeTimes.get(prime));
            }
        }
        if (value > 1) {
            Integer times = primeTimes.get(value);
            if (times == null) {
                times = 0;
                primes.add(value);
            }
            primeTimes.put(value, times + 1);
        }
    }
    // compute primes power:
    List<BigInteger> primePows = new ArrayList<>(primes.size());
    for (Entry<Integer,Integer> e: primeTimes.entrySet()) {
        primePows.add(new BigInteger(String.valueOf(e.getKey())).pow(e.getValue()));
    }
    // it multiply all of them:
    return divideAndConquer(primePows, 0, primePows.size());
}
+1


source


Probably the fastest approach:

Sequence.java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public final class Sequence {

    private final List<BigInteger> elements;

    private Sequence(List<BigInteger> elements) {
        this.elements = elements;
    }

    public List<BigInteger> getElements() {
        return elements;
    }

    public int size() {
        return elements.size();
    }

    public Sequence subSequence(int startInclusive, int endExclusive) {
        return subSequence(startInclusive, endExclusive, false);
    }

    public Sequence subSequence(int startInclusive, int endExclusive, boolean sync) {
        return Sequence.of(elements.subList(startInclusive, endExclusive), sync);
    }

    public void addLast(BigInteger element) {
        elements.add(element);
    }

    public BigInteger removeLast() {
        return elements.remove(size() - 1);
    }

    public BigInteger sum() {
        return sum(false);
    }

    public BigInteger sum(boolean parallel) {
        return parallel
                ? elements.parallelStream().reduce(BigInteger.ZERO, BigInteger::add)
                : elements.stream().reduce(BigInteger.ZERO, BigInteger::add);
    }

    public BigInteger product() {
        return product(false);
    }

    public BigInteger product(boolean parallel) {
        return parallel
                ? elements.parallelStream().reduce(BigInteger.ONE, BigInteger::multiply)
                : elements.stream().reduce(BigInteger.ONE, BigInteger::multiply);
    }

    public static Sequence range(int startInclusive, int endExclusive) {
        return range(startInclusive, endExclusive, false);
    }

    public static Sequence range(int startInclusive, int endExclusive, boolean sync) {
        if (startInclusive > endExclusive) {
            throw new IllegalArgumentException();
        }
        final List<BigInteger> elements = sync ? Collections.synchronizedList(new ArrayList<>()) : new ArrayList<>();
        for (; startInclusive < endExclusive; startInclusive++) {
            elements.add(BigInteger.valueOf(startInclusive));
        }
        return new Sequence(elements);
    }

    public static Sequence of(List<BigInteger> elements) {
        return of(elements, false);
    }

    public static Sequence of(List<BigInteger> elements, boolean sync) {
        return new Sequence(sync ? Collections.synchronizedList(elements) : elements);
    }

    public static Sequence empty() {
        return empty(false);
    }

    public static Sequence empty(boolean sync) {
        return of(new ArrayList<>(), sync);
    }

}

FactorialCalculator.java

import java.math.BigInteger;
import java.util.LinkedList;
import java.util.List;

public final class FactorialCalculator {

    private static final int CHUNK_SIZE = Runtime.getRuntime().availableProcessors();

    public static BigInteger fact(int n) {
        return fact(n, false);
    }

    public static BigInteger fact(int n, boolean parallel) {
        if (n < 0) {
            throw new IllegalArgumentException();
        }
        if (n <= 1) {
            return BigInteger.ONE;
        }
        Sequence sequence = Sequence.range(1, n + 1);
        if (!parallel) {
            return sequence.product();
        }
        sequence = parallelCalculate(splitSequence(sequence, CHUNK_SIZE * 2));
        while (sequence.size() > CHUNK_SIZE) {
            sequence = parallelCalculate(splitSequence(sequence, CHUNK_SIZE));
        }
        return sequence.product(true);
    }

    private static List<Sequence> splitSequence(Sequence sequence, int chunkSize) {
        final int size = sequence.size();
        final List<Sequence> subSequences = new LinkedList<>();
        int index = 0, targetIndex;
        while (index < size) {
            targetIndex = Math.min(index + chunkSize, size);
            subSequences.add(sequence.subSequence(index, targetIndex, true));
            index = targetIndex;
        }
        return subSequences;
    }

    private static Sequence parallelCalculate(List<Sequence> sequences) {
        final Sequence result = Sequence.empty(true);
        sequences.parallelStream().map(s -> s.product(true)).forEach(result::addLast);
        return result;
    }

}

Test:

public static void main(String[] args) {
    // warm up
    for (int i = 0; i < 100; i++) {
        FactorialCalculator.fact(10000);
    }
    int n = 1000000;
    long start = System.currentTimeMillis();
    FactorialCalculator.fact(n, true);
    long end = System.currentTimeMillis();
    System.out.printf("Execution time = %d ms", end - start);
}

Result:

Execution time = 3066 ms
  • OS: Win 10 Pro 64-bit
  • Processor: Intel Core i7-4700HQ @ 2.40GHz 2.40GHz
0


source






More articles:


All Articles