Let a0=0, a1=1, an=an-1 + an-2 mod 232. We generate 224 32-bit wide values of this sequence starting at a2, and output in raw binary. Gzip and bzip2 cannot compress this data, while lzma version 4.43-14ubuntu2 can.
This is a very simple, rather poor, pseudorandom number generator.
Doing a search over a0=0, 0<=a1<=600, here are the number of bytes after lzma compression for the best and worst. The uncompressed data is 67108864 bytes.
| a1 | Bytes after lzma compression |
|---|---|
| 0 | 9555 |
| 512 | 17485560 |
| 160 | 32856845 |
| 368 | 33114453 |
| 16 | 33120288 |
| 112 | 33164622 |
| 48 | 33170719 |
| 224 | 33193840 |
| 528 | 33276552 |
| 144 | 33383935 |
| ... | |
| 107 | 66020589 |
| 25 | 66072601 |
| 215 | 66212294 |
| 223 | 66293165 |
| 391 | 66464701 |
| 263 | 67270175 |
| 3 | 67281769 |
| 11 | 67509002 |
| 17 | 67586479 |
| 197 | 67598950 |
If we do everything in 64 bits, lzma seems always able to compress. Here are some results, 0<=a0<=1, 0<=a1<=300. The uncompressed data is 134217728 bytes.
| a0 | a1 | Bytes after lzma compression |
|---|---|---|
| 0 | 0 | 19022 |
| 0 | 160 | 92625248 |
| 0 | 288 | 98440144 |
| 0 | 128 | 101506051 |
| 0 | 64 | 102243681 |
| 0 | 24 | 102401107 |
| 0 | 192 | 102548146 |
| 0 | 256 | 102636570 |
| 0 | 224 | 102641413 |
| 0 | 66 | 102650889 |
| 1 | 224 | 102668158 |
| 0 | 48 | 102733136 |
| ... | ||
| 0 | 231 | 114737440 |
| 0 | 167 | 115103524 |
| 1 | 65 | 115373650 |
| 0 | 91 | 116047368 |
| 1 | 107 | 116077496 |
| 0 | 219 | 116341874 |
| 1 | 256 | 116428799 |
| 1 | 60 | 117401543 |
| 1 | 42 | 117854697 |
| 1 | 127 | 120676882 |
The challenge remains to produce as rapidly as possible data "random" enough to fool lzma.
SSE is probably involved.
1 comment :
http://kenta.blogspot.com/2010/07/upuplxco-much-faster-than-urandom.html
Post a Comment