Ottimizzazione ciclo for

[Matt_87]

Buongiorno a tutti, ho un problema con un ciclo for che richiede troppo tempo per essere eseguito. Il codice in questione è questo:

 for(int i = 0; i<kin.length(); i++){
            
            Q = doublePoint(Q, number, a);
            
            if(kin.charAt(i) == '1')
                Q = addPoint(Q, P, number, a);    
        }

Praticamente la variabile kin è in formato binario e la sua lunghezza si aggira spesso tra 70000 e 100000 cifre (infatti il numero che passo al metodo che contiene questa porzione di codice è molto grande), tuttavia non riesco ad ottimizzarlo( avevo pensato anche alla tecnica del unrolled loop ma la lunghezza del ciclo varia). Avete in mente un modo per poter ridurre i tempi di esecuzione? Grazie in anticipo.

[andbin]

Buongiorno a tutti, ho un problema con un ciclo for che richiede troppo tempo per essere eseguito.

Praticamente la variabile kin è in formato binario e la sua lunghezza si aggira spesso tra 70000 e 100000 cifre (infatti il numero che passo al metodo che contiene questa porzione di codice è molto grande)

Il problema non è tanto il for in sé o la lunghezza della stringa .... ma cosa sono quei Q/P/number/a e soprattutto cosa fanno doublePoint/addPoint.

[Matt_87]

Ciao, innanzitutto grazie della risposta! Dunque è una implementazione dell'algoritmo di Lenstra basato sulle curve ellittiche. In sostanza al metodo passo un punto P, un numero number da fattorizzare, un coefficiente a ed un numero in formato binario kin. Q è un punto inizializzato a zero in sostanza; double point effettua Q+Q (lo raddoppia in pratica) addPoint effettua P+Q ogni volta che nella stringa binaria incontro un 1.

[Matt_87]

Potrebbe essere che le performance dipendano dalle operazioni effettuate su BigInteger? Non ho potuto usare tipi di dati primitivi tipo int o long per via della dimensione dei numeri. questo è il codice di doublePoint ed addPoint:

public static ECPoint addPoint(ECPoint r, ECPoint s, BigInteger number, BigInteger a) {
        
        BigInteger temp_m = new BigInteger("0");
        BigInteger def_m = new BigInteger("0");
        //BigInteger newPoint[] = new BigInteger[2];
        BigInteger x = new BigInteger("0");
        BigInteger y = new BigInteger("0");


        if (r.equals(s))
            return doublePoint(r,number,a);
        else if (r.equals(ECPoint.POINT_INFINITY))
            return s;
        else if (s.equals(ECPoint.POINT_INFINITY))
            return r;
        
        temp_m = (s.getAffineY().subtract(r.getAffineY())).multiply(ECMUtility.inverseNumber((s.getAffineX().subtract(r.getAffineX())), number));
        def_m = temp_m.mod(number);
        x = (def_m.pow(2)).subtract(r.getAffineX()).subtract(s.getAffineX()).mod(number);
        y = (r.getAffineY().add((def_m.multiply((x.subtract(r.getAffineX())))))).negate().mod(number);
        BigInteger Xout = x.mod(number);
        BigInteger Yout = y.mod(number);
        ECPoint out = new ECPoint(Xout, Yout);
        return out;
    }


    public static ECPoint doublePoint(ECPoint r, BigInteger number, BigInteger a) {
        
        BigInteger temp_m = new BigInteger("0");
        BigInteger def_m = new BigInteger("0");
        //BigInteger newPoint[] = new BigInteger[2];
        BigInteger x = new BigInteger("0");
        BigInteger y = new BigInteger("0");
        
        if (r.equals(ECPoint.POINT_INFINITY)) 
            return r;
        temp_m = ((THREE.multiply(r.getAffineX().pow(2))).add(a)).multiply(ECMUtility.inverseNumber((TWO.multiply(r.getAffineY())), number));
        def_m = temp_m.mod(number);
        x = (def_m.pow(2)).subtract((TWO.multiply(r.getAffineX()))).mod(number);
        y = (r.getAffineY().add((def_m.multiply((x.subtract(r.getAffineX())))))).negate().mod(number);
        BigInteger Xout = x.mod(number);
        BigInteger Yout = y.mod(number);
        ECPoint out = new ECPoint(Xout, Yout);
        return out;
    }