Qual è l'algoritmo di fattorizzazione più efficiente per la fase di estrazione del setaccio quadratico?

Question

Nell'algoritmo del crivello quadratico, dopo aver trovato i valori bSmooth utilizzando l'approssimazione logaritmica, è necessario fattorizzare il numero, chiamiamolo B, per costruire il vettore bSmooth.

Una soluzione comune consiste nell'utilizzare una divisione di prova utilizzando i numeri primi nella base dei fattori. A differenza dei numeri casuali, in questo caso la divisione di prova è super efficiente poiché la maggior parte dei fattori sarà nella base principale. Dico "la maggior parte" perché un'ottimizzazione comune consentirà a una piccola soglia di includere 1-3 prim con un prodotto fino a 2 ^ 30 circa, si chiama relazione parziale.

Nella mia attuale implementazione , questa fase di estrazione vettoriale richiede la maggior parte del tempo. Un'altra soluzione che ho cercato di fare è ricevere, camminare di nuovo sulla base prima e registrare i vettori negli indici noti per essere b-liscio., ma che si è rivelato ancora più lento.

Di seguito è riportato il mio codice attuale, ho aggiunto 4 ottimizzazioni per la divisione di prova, per favore dimmi se ci sono soluzioni migliori per questo.

1. Per il primo 2, controllo l'ultimo bit impostato Be sposto a destra per estrarlo.
2. Sto usando BigInteger divideAndRemaindersta ottimizzando sia la memoria che le prestazioni combinando la divisione e le azioni mod in 1
3. se Bè più piccolo del massimo numero primo nella base dei fattori, allora deve essere nella base dei fattori, quindi utilizzo una mappa hash per individuare il suo indice
4. se nessun numero primo B.bitLenght() / 2sta dividendo Ballora deve essere una relazione parziale, la includerò solo se è un numero primo.

    private VectorData extractVector(BigInteger value) {
        BitSet vector = new BitSet(PrimeBase.instance.primeBase.size());
        if(value.compareTo(BigInteger.ZERO) < 0){
            vector.set(0);
            value = value.abs();
        }
        value = extractPower2(value, vector);
        for (int i = 2; i < PrimeBase.instance.primeBase.size(); i++) {
            BigInteger p = PrimeBase.instance.primeBaseBigInteger.get(i);
            int count = 1;
    
            BigInteger[] results = value.divideAndRemainder(p);
            if (results[1].equals(BigInteger.ZERO)) {
                value = results[0];
                while (true) {
                    results = value.divideAndRemainder(p);
                    if(!results[1].equals(BigInteger.ZERO)){
                        break;
                    }
                    value = results[0];
                    count++;
                }
                if(count % 2 == 1) {
                    vector.set(i);
                }
    
                if (value.equals(BigInteger.ONE)) {
                    bSmoothVectorData.vector = vector;
                    return bSmoothVectorData;
                } else if (value.compareTo(PrimeBase.instance.maxPrimeBigInteger) <= 0) {
                    int index = PrimeBase.instance.primeBaseMap.get(value);
                    vector.set(index);
                    bSmoothVectorData.vector = vector;
                    return bSmoothVectorData;
                } else if (value.bitLength() / 2 < p.bitLength()) {
                    if (isPrime(value.longValue())) {
                        return new VectorData(vector, value);
                    }
                    return null;
                }
            }
        }
        return null;
    }

bSmoothVectorDataè usato per distinguere tra relazioni complete e parziali. L'ultimo caso else-if che richiede isPrimeè raro e richiede meno dello 0,001% delle prestazioni complessive di questo metodo, il collo di bottiglia è nella chiamata a divideAndRemainderche richiede circa il 72% delle prestazioni.

Answer 1

Sono stato in grado di ottenere un aumento delle prestazioni di quasi l'80% cambiando la divisione di prova con la ricezione. Ora, ho già menzionato nella domanda che l'ho provato prima senza successo. Bene, questa volta ha funzionato.

Ho sostituito il BigInteger.mod(x).equals(ZERO)test con integer operations (bSmoothData.localX - delta) % prime == startingPosition, probabilmente è molto specifico per la mia implementazione, ma l'idea è di verificare se il numero primo dovrebbe dividere l'indice bSmooth nell'array di setacciatura.

Successivamente, costruisco un prodotto di tutti quei numeri primi e divido il valore effettivo di bSmooth per esso, quindi me ne sono andato con un promemoria che può durare a lungo in Java. E continuo a estrarlo usando la divisione di prova. Se sei interessato alla mia implementazione ho fatto un video qui