grinder:workspace zeph$ python try.py
original_size:150516
divisor_size:15052
135464 / 1 120412 / 1 105361 / 1 90309 / 1 75258 / 1 60206 / 1 45155 / 1 30103 / 1 15052 / 1 iterations:9
reconstructing . . . . . . . . . . reconstructed_size:150516
source code: python tryout for compression fibonacci generator [warning! it might damage your pc… 🙂 ]
basically… was a lot of time I had to make a demo on this… keeping the result of a division, and the module, we can compress a file infinite times…
res = src
while res > pip:
res = src / pip
mod = src % pip
saving.append(mod)
src = res
every file is a string of ones and zeros, right? so, it is a number
we can recursively apply this algorithm till we reach the size we want
it is extremely time consuming, so, better use it only for log files and ISO images
the target is to use a divisor as much as big as the “number” to divide… this is easy to achieve using a standard math serie like Fibonacci… 1*10^6 number of fibonacci is pretty big… 1*10^9 HUGE!
at the end you only need to keep, this string “1*10^9” (6 digits!) + the number of iterations (1 or 2 digits?) + the last result of the division and the last result of the module
while True:
mod = saving.pop()
back = back * pip + mod
comments? 🙂
in the sample I went down from 150k to 15k … not bad, ah?
(k, I used an array as support datastructure, but the tryout is to show that it is possible)
I already imagine storage of logs of ISPs, with a FPGA implementation of this trick…
Guido Maria Serra 
it’s time to patent it, isnt’it?
patent what? the bases of math? 😀
C’e’ qualcosa che non ho capito.
L’idea e’ di concepire un file come un numero e di comprimerlo rappresentandolo come divisione intera piu’ un resto di un numero grande quasi quanto l’originale.
Il problema e’ che se il resto e’ lungo quasi quanto il numero originale non ci si guadagna molto.
Quindi il problema dell’ algoritmo e’ quello di trovare il giusto divisore per ogni file da comprimere, in modo da minimizzare il resto.
O forse sto sbagliando qualcosa?
Ovviamente non sta in piedi.
Usi numeri a precisione arbitraria e on li salvi.
Chiaramente il resto e` dello stesso ordine di grandezza del divisore.
Ma a te non serve l’ultimo resto: servono tutti.
Nell’esempio fatto hai un divisore da 15k-cifre, e il resto e` 15k-cifre.
Ogni iterazione togli 15k-cifre dal file.
Ma lo stato rimane in “saving”. Il tuo “saving” e` lungo come quanto manca al file.
E` facile comprimere e decomprimere nello stesso programma. Ti tieni lo stato nel programma stesso…
Cosi` ti comprimo anche a zero: “read(file); unlink(file); print(“scomparso”); write(file); print(“rieccolo”);
So che vali di piu` e ti voglio bene lo stesso. Si vede che non sei ne` un matematico ne` un ingengere, ma i migliori non si laureano (e dopo qualche anno si vede…)
Sorrt for the previous comment. It’s clear you are making fun of your reader, and I just got tricked by it. You are _definitely_ smarter than this…
ciao Ale, a dire il vero il saving e’ di 1 byte per ogni iterazione, hai letto bene il mio proof-of-concept?
se vuoi ne faccio uno che lavora su file… visto che questo potrebbe non convincere a sufficienza
che dici?
appena uscito dalla doccia , devo scappare al lavoro…
pubblico la mail appena mandata a “rubi”
(@Fabio: spero cio’ risponda anche ai tuoi quesiti):
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
devo scappare al lavoro, ma ho le tue risposte
mi sono espresso male
concordiamo che:
un numero diviso per se stesso da 1 e resto 0?
un numero diviso 1 da risultato se stesso e resto 0?
un numero diviso per la sua base numerica e’ una stronzata perche’ lo shifti solo a destra e a sinistra?
un numero diviso un altro numero molto vicino a se stesso, da un risultato tendenzialmente vicino a 1 e un resto che “non sappiamo”, ma che facilmente possiamo ritenere NOTEVOLMENTE inferiore al valore del numero di partenza ?
ora, tutto casino non e’ per dimostrare la divisione ma…
se tu applichi come divisore, un numero ottenuto da una serie numerica, puoi mappare su un altro piano di riferimento quel divisore tramite il suo numero di occorrenza nella serie… giusto? e in questo caso puoi mappare blocchi enormi di un numero a stringhe di pochi byte
il tutto sta nel cercare numeri di serie (ad esempio numeri di fibonacci) tali che il risultato della divisione sia tendente a 1
piu’ il numero da dividere e’ grosso, piu’ la differenza tra la serie e l’occorrenza nella serie e’ enorme… piu’ sara’ la tua possibilita’ di mappare blocchi ottenuti tramite la divisione a numeri riferenti alla serie decisamente inferiori al numero di partenza
ora ti e’ chiaro?
ovvio che per numeri piccoli, come volevi fare tu, sta cosa si perde, proprio perche’ non guadagni gran che con la serie numerica
cheers,
G.