Xor tra binari, primo approcio
Moderatore: Staff
Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.
La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.
La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.
- Procopio
- Linux 3.x
- Messaggi: 844
- Iscritto il: ven 29 lug 2011, 11:50
- Nome Cognome: Matteo Micheletto Oddino
- Slackware: 14.2
- Kernel: 4.4.14
- Desktop: Awesome
- Località: Torino
Xor tra binari, primo approcio
Ciao a tutti,
il mio problema: ho una lista di numeri assegnati più o meno casualmente, quello che dovrei fare è:
fare xor tra gli elementi di questa lista esaurendo tutte le combinazioni possibili (25! o 50! e il ! sta per fattoriale) e vedere se ci sono delle ricorrenze tra i risultati degli xor e gli elementi stessi della lista.
Il tutto per almeno un po' di liste in maniera che le eventuali ricorrenze che posso trovare siano consistenti.
A mano divento vecchio, e dal punto di vista informatico, non mi sembra complicato, però non mi intendo di programmazione. Ora, non voglio che mi scriviate il programma ma che mi diciate quali funzioni e comandi devo usare, e soprattutto se posso farlo in bash o se devo utilizzare un linguaggio (possibilmente pyton:)), io poi mi studio i singoli comandi e cerco di scrivere il programma, poi se mi pianto chiedo dinuovo Oppure se ci sono direttamente programmi già fatti ancora meglio, su github ho trovato qualcosa, ma non capisco se sono adatti al mio scopo...
Nota a margine, per chi si intendesse un pochino di matematica: I numeri della lista sono generati da una mappa, ossia una funzione matematica che mangia un numero (compreso tra 0 e 1) e restituisce un numero (compreso tra 0 e 1) e che quindi reiterata per n passaggi mi dà la lista di n elementi.
I numeri li posso esprimere come binario decimale, come viene fatto ber la mappa di Bernoulli, ossia per esempio: 0.15=0.1111.
La cosa devo farla su più mappe (bernoulli, tenda, baker lineare, standard, logistica) e valutare il comportamento e le caratteristiche salienti per queste mappe, distinguendole tra caotiche, ergodiche hamiltoniane ecc
il mio problema: ho una lista di numeri assegnati più o meno casualmente, quello che dovrei fare è:
fare xor tra gli elementi di questa lista esaurendo tutte le combinazioni possibili (25! o 50! e il ! sta per fattoriale) e vedere se ci sono delle ricorrenze tra i risultati degli xor e gli elementi stessi della lista.
Il tutto per almeno un po' di liste in maniera che le eventuali ricorrenze che posso trovare siano consistenti.
A mano divento vecchio, e dal punto di vista informatico, non mi sembra complicato, però non mi intendo di programmazione. Ora, non voglio che mi scriviate il programma ma che mi diciate quali funzioni e comandi devo usare, e soprattutto se posso farlo in bash o se devo utilizzare un linguaggio (possibilmente pyton:)), io poi mi studio i singoli comandi e cerco di scrivere il programma, poi se mi pianto chiedo dinuovo Oppure se ci sono direttamente programmi già fatti ancora meglio, su github ho trovato qualcosa, ma non capisco se sono adatti al mio scopo...
Nota a margine, per chi si intendesse un pochino di matematica: I numeri della lista sono generati da una mappa, ossia una funzione matematica che mangia un numero (compreso tra 0 e 1) e restituisce un numero (compreso tra 0 e 1) e che quindi reiterata per n passaggi mi dà la lista di n elementi.
I numeri li posso esprimere come binario decimale, come viene fatto ber la mappa di Bernoulli, ossia per esempio: 0.15=0.1111.
La cosa devo farla su più mappe (bernoulli, tenda, baker lineare, standard, logistica) e valutare il comportamento e le caratteristiche salienti per queste mappe, distinguendole tra caotiche, ergodiche hamiltoniane ecc
- N1cuz
- Linux 2.x
- Messaggi: 333
- Iscritto il: lun 6 ott 2008, 0:41
- Nome Cognome: Nicola Bartolomei
- Slackware: 14.1
- Kernel: 4.3.3
- Desktop: xfce4
- Località: Pieve a Nievole (PT)
Re: Xor tra binari, primo approcio
Forse non ho capito bene il problema io ma 25! xor da computare sono un botto anche per il calcolaore circa 1.55*10^25 operazioni, se hai un processore che te ne fa 3*10^9 al secondo ci mette diversi milioni di anni a terminare...
Ripeto forse ho inteso male il problema io, comunque se intanto posti quello che hai trovato potrebbe essere d'aiuto.
In bocca al lupo
Nicola
Ripeto forse ho inteso male il problema io, comunque se intanto posti quello che hai trovato potrebbe essere d'aiuto.
In bocca al lupo
Nicola
- targzeta
- Iper Master
- Messaggi: 6631
- Iscritto il: gio 3 nov 2005, 14:05
- Nome Cognome: Emanuele Tomasi
- Slackware: 64-current
- Kernel: latest stable
- Desktop: IceWM
- Località: Carpignano Sal. (LE) <-> Pisa
Re: Xor tra binari, primo approcio
Fai un esempio piccolo di quello che vuoi, così si capisce meglio! Un esempio vale mille parole
Emanuele
Emanuele
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
- Procopio
- Linux 3.x
- Messaggi: 844
- Iscritto il: ven 29 lug 2011, 11:50
- Nome Cognome: Matteo Micheletto Oddino
- Slackware: 14.2
- Kernel: 4.4.14
- Desktop: Awesome
- Località: Torino
Re: Xor tra binari, primo approcio
per esempio la lista
sono le prime 7 iterazioni della mappa di Bernuolli (la cui espressione è 2x mod1), partendo da 0.27 come condizione iniziale.
In pratica questa mappa parte da un numero reale compreso tra zero e uno e lo moltiplica per 2, considerandone per il risultato però solo la parte decimale, in modo da rimanere all'interno dell'intervallo (0,1).
Ora, considerando che tutti gli elementi di quella lista sono scritti come 0.xx, possiamo riscrivere la lista omettendo la scrittura decimale, e otteniamo:
A questo punto scriviamo questa lista come numeri binari, ottenendo
Ora questa lista andrebbe riscritta per avere tutti numeri con ugual numero di cifre, per poterne fare gli xor tra i vari elementi, quindi mettendo gli zeri a sinistra di ogni numero, è lecito?
bene, se fino qua è tutto lecito non resta che fare xor tra gli elementi di questa lista scritti in questo modo, saturando tutte le combinazioni possibili.
EDIT: essendo la lista composta di 7 elementi, svolgendo xor tra di loro in tutte le combinazioni possibili senza ripeterle, si hanno 21 elementi (non 7!, mi ero sbagliato).
A questo punto quello che vorrei è farci i miei giochetti matematici, tipo: vedere se si hanno ricorrenze tra i risultati, se si possono isolare punti fissi (cioè xor che danno lo stesso risultato), vedere sulle orbite periodiche come si comporta
(per orbite periodiche si intendono serie di p numeri che si ripetono, per esempio tutti i numeri razionali (che possono cioè essere scritti come n/m, con "n" ed "m" interi)tra 0 1 un danno luogo a infinite orbite periodiche (di periodo m, cioè che dopo aver reiterato m volte la mappa sul numero n/m ottengo dinuovo n/m) (anche se questo insieme è misura nulla, vabbè))
ecc ecc ecc
Ps: N1cuz il tuo in bocca al lupo finale dopo la previsione di milioni di anni di calcolo mi ha fatto morire
Codice: Seleziona tutto
(0.27,0.54,0.08,0.16,0.32,0.64,0.28)
In pratica questa mappa parte da un numero reale compreso tra zero e uno e lo moltiplica per 2, considerandone per il risultato però solo la parte decimale, in modo da rimanere all'interno dell'intervallo (0,1).
Ora, considerando che tutti gli elementi di quella lista sono scritti come 0.xx, possiamo riscrivere la lista omettendo la scrittura decimale, e otteniamo:
Codice: Seleziona tutto
(27,54,8,16,32,64,28)
Codice: Seleziona tutto
(11011,110110,1000,10000,100000,1000000,11100)
Codice: Seleziona tutto
(0011011,0110110,0001000,0010000,0100000,1000000,0011100)
EDIT: essendo la lista composta di 7 elementi, svolgendo xor tra di loro in tutte le combinazioni possibili senza ripeterle, si hanno 21 elementi (non 7!, mi ero sbagliato).
A questo punto quello che vorrei è farci i miei giochetti matematici, tipo: vedere se si hanno ricorrenze tra i risultati, se si possono isolare punti fissi (cioè xor che danno lo stesso risultato), vedere sulle orbite periodiche come si comporta
(per orbite periodiche si intendono serie di p numeri che si ripetono, per esempio tutti i numeri razionali (che possono cioè essere scritti come n/m, con "n" ed "m" interi)tra 0 1 un danno luogo a infinite orbite periodiche (di periodo m, cioè che dopo aver reiterato m volte la mappa sul numero n/m ottengo dinuovo n/m) (anche se questo insieme è misura nulla, vabbè))
ecc ecc ecc
Ps: N1cuz il tuo in bocca al lupo finale dopo la previsione di milioni di anni di calcolo mi ha fatto morire
- robbybby
- Linux 4.x
- Messaggi: 1223
- Iscritto il: sab 16 dic 2006, 10:48
- Slackware: 13.1 / 64 bit
- Kernel: 3.3.x
- Desktop: KDE 4.4.5
- Località: Fra Trantor e Terminus
Re: Xor tra binari, primo approcio
Sicuramente morirai di vecchiaia aspettando i risultati.Procopio ha scritto:Ps: N1cuz il tuo in bocca al lupo finale dopo la previsione di milioni di anni di calcolo mi ha fatto morire
A parte il tempo di calcolo, dove memorizzi 25! di risultati? Quindi, oltre a un tempo quasi eterno, devi andare alla Corsair e alla Kingston a prenotare tutta la produzione di RAM per i prossimi secoli, e alla Samsung a prenotare gli hard disk.
Una volta che hai i numeri interi nel computer, non devi fare niente, prima di farne lo xor: lo fai e basta. Visto quanto sono piccoli (da 0 a 99) ti basta un byte per ogni numero.
- targzeta
- Iper Master
- Messaggi: 6631
- Iscritto il: gio 3 nov 2005, 14:05
- Nome Cognome: Emanuele Tomasi
- Slackware: 64-current
- Kernel: latest stable
- Desktop: IceWM
- Località: Carpignano Sal. (LE) <-> Pisa
Re: Xor tra binari, primo approcio
Intanto si parla di combinazioni semplici di n elementi su k=2, quindi un numero molto inferiore a n!, ovvero (n!/2(n-2)!) e questa è una buona cosa.
Tutto quello che hai scritto si può fare. Se non ti preoccupi della rappresentazione binaria e vuoi solo il risultato in decimale puoi anche usare il python. Guarda qui un esempio (direttamente riproducibile se lanci python in un terminale):Come vedi, i numeri b sono sempre rappresentabili su 3 bit, quindi lo zero iniziale ce lo mette lui quando fa lo xor!
Emanuele
Tutto quello che hai scritto si può fare. Se non ti preoccupi della rappresentazione binaria e vuoi solo il risultato in decimale puoi anche usare il python. Guarda qui un esempio (direttamente riproducibile se lanci python in un terminale):
Codice: Seleziona tutto
Python 2.7.12 (default, Sep 6 2016, 18:21:48)
[GCC 5.4.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> a=10
>>> b=5
>>> print a^b
15
>>> a=9
>>> b=6
>>> print a^b
15
Emanuele
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
- targzeta
- Iper Master
- Messaggi: 6631
- Iscritto il: gio 3 nov 2005, 14:05
- Nome Cognome: Emanuele Tomasi
- Slackware: 64-current
- Kernel: latest stable
- Desktop: IceWM
- Località: Carpignano Sal. (LE) <-> Pisa
Re: Xor tra binari, primo approcio
Tra l'altro, in python ho visto che c'è anche la libreria che ti fa le combinazioni semplici, quindi guarda qui con i numeri che hai come esempio:Tutte le 21 combinazioni possibili "x-orate" con il risultato in decimale. Che per quello che serve a te mi sa che basta, no?
Emanuele
Codice: Seleziona tutto
Python 2.7.12 (default, Sep 6 2016, 18:21:48)
[GCC 5.4.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from itertools import combinations
>>> list=(27, 54, 8, 16, 32, 64, 28)
>>> for (a, b) in combinations(list, 2):
... print "a: %i, b: %i, a xor b: %i" % (a, b, a^b)
...
a: 27, b: 54, a xor b: 45
a: 27, b: 8, a xor b: 19
a: 27, b: 16, a xor b: 11
a: 27, b: 32, a xor b: 59
a: 27, b: 64, a xor b: 91
a: 27, b: 28, a xor b: 7
a: 54, b: 8, a xor b: 62
a: 54, b: 16, a xor b: 38
a: 54, b: 32, a xor b: 22
a: 54, b: 64, a xor b: 118
a: 54, b: 28, a xor b: 42
a: 8, b: 16, a xor b: 24
a: 8, b: 32, a xor b: 40
a: 8, b: 64, a xor b: 72
a: 8, b: 28, a xor b: 20
a: 16, b: 32, a xor b: 48
a: 16, b: 64, a xor b: 80
a: 16, b: 28, a xor b: 12
a: 32, b: 64, a xor b: 96
a: 32, b: 28, a xor b: 60
a: 64, b: 28, a xor b: 92
>>>
Emanuele
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
- Procopio
- Linux 3.x
- Messaggi: 844
- Iscritto il: ven 29 lug 2011, 11:50
- Nome Cognome: Matteo Micheletto Oddino
- Slackware: 14.2
- Kernel: 4.4.14
- Desktop: Awesome
- Località: Torino
Re: Xor tra binari, primo approcio
Sì è perfetto.
Due domane:
-Il lavoro ora dovrebbe essere di fare questa cosa su liste lunghe e vedere se ci sono ricorsioni nei risultati.
Ricordo che ogni elemento nella lista è dato dall'applicazione della mappa sull'elemento precedente, quindi lo studio lo faccio vedendo se, ad esempio, xor tra il 16esimo e il 32esimo elemento restituisce sempre lo stesso numero qualunque sia la lista (cioè le condizioni iniziali).
Questo può essere automatizzato in qualche modo? Tipo, che so, data la lista degli xor tra gli n elementi, quindi lista di n!/2(n-2)! elementi , vedere se ci sono elementi che coincidono, o ancora meglio se tra liste di questo tipo diverse capire se l'elemento 32esimo coincide sempre con l'elemento 46esimo.
-seconda domanda xor tra due elementi da lo stesso risultato qualunque sia la base in cui si scrivono le variabili giusto? Ad ogni modo per inserire numeri in basi diverse devo aggiungere qualche comando?
Due domane:
-Il lavoro ora dovrebbe essere di fare questa cosa su liste lunghe e vedere se ci sono ricorsioni nei risultati.
Ricordo che ogni elemento nella lista è dato dall'applicazione della mappa sull'elemento precedente, quindi lo studio lo faccio vedendo se, ad esempio, xor tra il 16esimo e il 32esimo elemento restituisce sempre lo stesso numero qualunque sia la lista (cioè le condizioni iniziali).
Questo può essere automatizzato in qualche modo? Tipo, che so, data la lista degli xor tra gli n elementi, quindi lista di n!/2(n-2)! elementi , vedere se ci sono elementi che coincidono, o ancora meglio se tra liste di questo tipo diverse capire se l'elemento 32esimo coincide sempre con l'elemento 46esimo.
-seconda domanda xor tra due elementi da lo stesso risultato qualunque sia la base in cui si scrivono le variabili giusto? Ad ogni modo per inserire numeri in basi diverse devo aggiungere qualche comando?
- targzeta
- Iper Master
- Messaggi: 6631
- Iscritto il: gio 3 nov 2005, 14:05
- Nome Cognome: Emanuele Tomasi
- Slackware: 64-current
- Kernel: latest stable
- Desktop: IceWM
- Località: Carpignano Sal. (LE) <-> Pisa
Re: Xor tra binari, primo approcio
1) Se non hai un minimo di pratica con la programmazione non credo che tu ci possa fare molto. Magari puoi farti dare i risultati degli xor in CSV e li importi su libreoffice, poi ci lavori da lì.
2) l'xor in questione è binario, quindi, a prescindere da come vedi i numeri, viene sempre fatto sulla loro rappresentazione binaria (così come il risultato è seplicemente la rappresentazione in base 10 del numero binario che esce fuori). Non capisco cosa tu intenda per "inserire numeri in basi diverse".
Emanuele
2) l'xor in questione è binario, quindi, a prescindere da come vedi i numeri, viene sempre fatto sulla loro rappresentazione binaria (così come il risultato è seplicemente la rappresentazione in base 10 del numero binario che esce fuori). Non capisco cosa tu intenda per "inserire numeri in basi diverse".
Emanuele
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
- Procopio
- Linux 3.x
- Messaggi: 844
- Iscritto il: ven 29 lug 2011, 11:50
- Nome Cognome: Matteo Micheletto Oddino
- Slackware: 14.2
- Kernel: 4.4.14
- Desktop: Awesome
- Località: Torino
Re: Xor tra binari, primo approcio
I numeri nella lista di cui quelle righe di codice calcolano xor sono decimali.targzeta ha scritto:Non capisco cosa tu intenda per "inserire numeri in basi diverse".
Emanuele
Io lo vorrei fare anche con gli stessi numeri scritti in base binaria, sessagesimale, esadecimale ecc perchè tra le verifiche che devo fare sulle ricorrenze c'è la normalità dei punti fissi, dove per normalità in una base b di un numero si intende quella proptietà per cui tutte le cifre di quel numero appaiono con la stessa frequenza (1/b). E' un gioco a metà tra la teoria dei numeri e la teoria del caos: un casino
Se però (A in base X) xor (B in base X) = (A in base Y) xor (B in base Y) = (A in base Z) xor (B in base Z) allora posso farlo prima e verificare la normalità dopo