Python - La complessità del tempo delle funzioni integrate rispetto alle funzioni costruite manualmente nei campi finiti

0

In generale, mi sto chiedendo quali sono i vantaggi rispetto agli svantaggi dell'uso delle funzioni aritmetiche integrate rispetto al rollover in Python.

In particolare, sto prendendo in GF (2) polinomi del campo finito in formato stringa, convertendo in valori di base 2, eseguendo aritmetica, quindi restituito in polinomi come formato stringa. Quindi un piccolo esempio di questo è in moltiplicazione:

Rolling my own:

def multiply(a,b):
    bitsa = reversed("{0:b}".format(a))
    g = [(b<<i)*int(bit) for i,bit in enumerate(bitsa)]
    return reduce(lambda x,y: x+y,g)

Contro il built-in:

def multiply(a,b):  # a,b are GF(2) polynomials in binary form ....
    return a*b  #returns product of 2 polynomials in gf2

Al momento, operazioni come l'inversione moltiplicativa (con ad esempio esponenti da 20 bit) richiedono molto tempo per essere eseguite nel mio programma poiché utilizza tutte le operazioni matematiche incorporate di Python come // floor division e% module, ecc. per creare la mia divisione, resto, ecc. Mi chiedo quanto guadagno in termini di efficienza e prestazioni posso ottenere costruendo manualmente (come mostrato sopra).

Mi rendo conto che i guadagni dipendono dal modo in cui sono state costruite le versioni manuali, non è questa la domanda. Mi piacerebbe scoprire 'fondamentalmente' quanto vantaggio ci sia sul built-in. Quindi, per esempio, se la moltiplicazione (come nell'esempio sopra) è adatta per l'aritmetica di base 10 (decimale) ma deve passare attraverso più cerchi per cambiare basi in binario e quindi anche più cerchi in funzionamento (quindi è meno efficiente), questo è quello che mi sto chiedendo. Ad esempio, mi chiedo se sia possibile ridurre significativamente il tempo costruendoli da solo in modi che forse alcuni professionisti hanno già incontrato.

    
posta stackuser 30.06.2013 - 19:25
fonte

1 risposta

2

Non c'è praticamente alcun modo in cui le tue operazioni rotte a mano saranno tutt'altro che pateticamente lente rispetto alle operazioni built-in in python. Se tenti di implementare operazioni rotte a mano, ti farai programmare molto più lentamente.

Se vuoi sapere come far funzionare il tuo codice più velocemente, fai questa domanda. Pubblica il tuo codice lento completo sul link e ottieni feedback su ciò che può essere migliorato.

    
risposta data 01.07.2013 - 00:00
fonte

Leggi altre domande sui tag