Trovare il massimo comun divisore di una matrice in MATLAB

Question

Sto cercando un modo per dividere un certo elemento di matrice con il suo divisore comune più basso.

per esempio, ho vettori

[0,0,0; 2,4,2;-2,0,8] 

posso dire il minimo comune divisore è 2, quindi la matrice dopo la divisione sarà

[0,0,0;1,2,1;-1,0,4] 

Qual è il costruito nel metodo che può calcolare questo?

Grazie in anticipo

p.s. Personalmente non mi piace usare i loop per questo calcolo, sembra che ci sia un calcolo integrato in grado di eseguire la divisione di elementi matrix.

Answer 1

Dal momento che non vi piacciono i loop, che ne dici di funzioni ricorsive?

iif = @(varargin) varargin{2 * find([varargin{1:2:end}], 1, 'first')}(); 
gcdrec=@(v,gcdr) iif(length(v)==1,v, ... 
        v(1)==1,1, ... 
        length(v)==2,@()gcd(v(1),v(2)), ... 
        true,@()gcdr([gcd(v(1),v(2)),v(3:end)],gcdr)); 
mygcd=@(v)gcdrec(v(:)',gcdrec); 

A=[0,0,0; 2,4,2;-2,0,8]; 
divisor=mygcd(A); 
A=A/divisor; 

La prima funzione iif definiranno un costrutto condizionale linea. Ciò consente di definire una funzione ricorsiva, gcdrec, per trovare il massimo comun divisore dell'array. Questo iif funziona in questo modo: verifica se il primo argomento è true, se lo è, quindi restituisce il secondo argomento. In caso contrario, verifica il terzo argomento e, se ètrue, restituisce il quarto e così via. È necessario proteggere le funzioni ricorsive e talvolta altre quantità che appaiono al suo interno con @(), altrimenti è possibile ottenere errori.

Utilizzando iif la funzione ricorsiva gcdrec funziona così:

• se il vettore di ingresso è uno scalare, lo ritorna in
• altro se il primo componente del vettore è 1, non c'è alcuna possibilità di recuperare , quindi restituisce 1 (permette un rapido ritorno per grandi matrici)
• altrimenti se il vettore di ingresso è di lunghezza 2, restituisce il massimo comun divisore tramite gcd
• altrimenti si definisce con un vettore accorciato , in cui i primi due elementi sono sostituiti con il loro massimo comun divisore.

La funzione mygcd è solo un front-end per comodità.

Dovrebbe essere abbastanza veloce, e suppongo che solo la profondità di ricorsione potrebbe essere un problema per problemi molto grandi. Ho effettuato un rapido controllo dei tempi per confrontare con la versione loop di @Adriaan, utilizzando A=randi(100,N,N)-50, con N=100, N=1000 e N=5000 e tic/toc.

1. N=100:
   • annodare 0,008 secondi
   • ricorsive 0,002 secondi
2. N=1000:
   • loop 0,46 secondi
   • ricorsive 0,04 secondi
3. N=5000:
   • looping 11,8 secondi
   • ricorsive 0,6 secondi

Aggiornamento: cosa interessante è che l'unica ragione per cui non ho scattare il ricorsione limit (che è di default 500) è che i miei dati non avevano un divisore comune. L'impostazione di una matrice casuale e il raddoppio determineranno il raggiungimento del limite di ricorsione già per N=100. Quindi per le matrici di grandi dimensioni questo non funzionerà. Poi di nuovo, per le piccole matrici @ la soluzione di Adriaan è perfettamente a posto.

Ho anche cercato di riscrivere alla metà del vettore di ingresso in ogni passo ricorsivo: questo infatti risolve il problema del limite di ricorsione, ma è più lente (2 secondi per N=100, 261 secondi per N=1000). Potrebbe esserci una via di mezzo da qualche parte, dove la dimensione della matrice è grande (ish) e il runtime non è poi così male, ma non l'ho ancora trovato.

Answer 2

A = [0,0,0; 2,4,2;-2,0,8]; 
B = 1; 
kk = max(abs(A(:))); % start at the end 
while B~=0 && kk>=0 
    tmp = mod(A,kk); 
    B = sum(tmp(:)); 
    kk = kk - 1; 
end 
kk = kk+1; 

Questo probabilmente non è il modo più veloce, ma lo farà per ora. Quello che ho fatto qui è inizializzare un contatore, B, per memorizzare la somma di tutti gli elementi nella matrice dopo aver preso lo mod. il kk è solo un contatore che scorre attraverso interi. mod(A,kk) calcola il modulo dopo la divisione per ciascun elemento in A. Quindi, se tutti i tuoi elementi sono interamente divisibili per 2, restituirà uno 0 per ogni elemento. sum(tmp(:)) quindi crea una singola colonna fuori dal modulo-matrice, che viene sommata per ottenere un numero. Se e solo se quel numero è 0 c'è un divisore comune, da allora tutti gli elementi in A sono interamente divisibili per kk. Non appena ciò accade, il tuo loop si ferma e il tuo divisore comune è il numero in kk. Poiché kk è diminuito a ogni conteggio, in realtà è un valore troppo basso, quindi ne viene aggiunto uno.

Nota: Ho appena modificato il ciclo per eseguire indietro poiché stai cercando il più grande cd, non il più piccolo cd. Se avessi una matrice come [4,8;16,8], si fermerebbe a 2, non a 4. Ci scusiamo per questo, questo funziona ora, anche se entrambe le altre soluzioni qui sono molto più veloci.

Infine, dividendo matrici può essere fatto in questo modo:

divided_matrix = A/kk; 

Answer 3

D'accordo, neanche a me piacciono gli anelli!Diamo loro uccidono -

unqA = unique(abs(A(A~=0))).';    %//' 
col_extent = [2:max(unqA)]';    %//' 
B = repmat(col_extent,1,numel(unqA)); 
B(bsxfun(@gt,col_extent,unqA)) = 0; 
divisor = find(all(bsxfun(@times,bsxfun(@rem,unqA,B)==0,B),2),1,'first'); 
if isempty(divisor) 
    out = A; 
else 
    out = A/divisor; 
end 

Esempio corre

Caso # 1:

A = 
    0  0  0 
    2  4  2 
    -2  0  8 
divisor = 
    2 
out = 
    0  0  0 
    1  2  1 
    -1  0  4 

Caso # 2:

A = 
    0  3  0 
    5  7  6 
    -5  0 21 
divisor = 
    1 
out = 
    0  3  0 
    5  7  6 
    -5  0 21 

Answer 4

Ecco un altro approccio. Lascia che sia A il tuo array di input.

1. Ottieni valori diversi da zero di A e prendi il loro valore assoluto. Chiama il vettore risultante B.
2. Verificare ciascun numero da 1 a max(B) e verificare se divide tutte le voci di B (ovvero se il resto della divisione è zero).
3. Prendere il numero più grande.

Codice:

A = [0,0,0; 2,4,2;-2,0,8];     %// data 
B = nonzeros(abs(A));      %// step 1 
t = all(bsxfun(@mod, B, 1:max(B))==0, 1); %// step 2 
result = find(t, 1, 'last');    %// step 3