Xor tra binari, primo approcio

[Procopio]

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

[N1cuz]

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

[targzeta]

Fai un esempio piccolo di quello che vuoi, così si capisce meglio! Un esempio vale mille parole

Emanuele

[Procopio]

per esempio la lista

Codice: Seleziona tutto

(0.27,0.54,0.08,0.16,0.32,0.64,0.28)

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:

Codice: Seleziona tutto

(27,54,8,16,32,64,28)

A questo punto scriviamo questa lista come numeri binari, ottenendo

Codice: Seleziona tutto

(11011,110110,1000,10000,100000,1000000,11100)

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?

Codice: Seleziona tutto

(0011011,0110110,0001000,0010000,0100000,1000000,0011100)

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

[robbybby]

Ps: N1cuz il tuo in bocca al lupo finale dopo la previsione di milioni di anni di calcolo mi ha fatto morire

Sicuramente morirai di vecchiaia aspettando i risultati.

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]

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):

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

Come vedi, i numeri b sono sempre rappresentabili su 3 bit, quindi lo zero iniziale ce lo mette lui quando fa lo xor!

Emanuele

[targzeta]

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:

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
>>>

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

[Procopio]

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?

[targzeta]

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

[Procopio]

Non capisco cosa tu intenda per "inserire numeri in basi diverse".

Emanuele

I numeri nella lista di cui quelle righe di codice calcolano xor sono decimali.
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