« Отговор #36 -: Jun 17, 2015, 01:03 »
Компресия ли е идеята....звучи интересно като идея, защото ако работи, ще се опровергае една теорема на Клод Шанън. От друга страна, аз поне бидейки относително посредствен математик, въпреки че по диплома се водя такъв, не мога да докажа защо няма да работи.
Иначе малко разсъждения - ако се абстрахираме от нуждата да работиш с точни стойности и апроксимации вършеха работа, тогава елементарното като подход което ми хрумва на ума е първо да намериш натуралния логаритъм на голямото число N:
x = ln(N)
Изглежда брутално чисто изчислително, но има "шорткъти", от които човек би могъл да се възползва, например можем да първо да коренуваме, примерно нека N=M^2 тогава:
ln(N) = ln(M^2) = ln(M)+ln(M)
колкото по-висока степен изберем, толкова по-лесни сметки, макар че за голямо число самото коренуване ще е драма, несъмнено.
След като намерим ln(N) = x, остава да пазиш просто x и на теория ще смачкаш ужасно огромното число N до ужасно по-малкото число x, разликата между двете е буквално експоненциална. Когато после искаш да намериш N от x, не е казано че трябва да степенуваш e на степен x (което би било леко убийствено занимание), върши ни работа и апроксимация, примерно можем да развием e^x в ред на Тейлър и колкото повече я "развиваме" толкова повече се приближаваме до истинската стойност на N:
N ~= 1 + x + x^2/2! + x^3/3! + x^4/4! + x^5/5! + .....
Така имаме хубав механизъм да балансираме между точност и производителност. Това би било удобна схема за компресия само ако въпросната позволява загуби, защото нищо не гарантира че резултатът ще е равен на N (колкото повече го "развиваме", толкова повече ще се приближава до N, но с това загубата при компресията ще намалява за сметка на изчислителното време, което ще нараства).
Ако държиш да няма загуби, тогава първо трябва да откриеш начин лесно да представяш число като полином от произволна степен (може и да има такъв начин, знам ли - огромна част от спомените ми от университета са изтрити, но аз поне не се сещам на прима виста за нещо такова, дори ми се вижда мааалко съмнително, но наистина не знам). И второ, да добавиш ограничението корените да са целочислени, което усложнява нещата. С числа с плаваща запетая не можеш да си позволиш да се занимаваш, защото дори да се работи с много голяма прецизност, нещата загрубяват бързо заради степенуването. Ти имаш интерес от полином от по-висока степен, защото това ще ти даде по-добра компресия.
Та ми е интересно като цяло де, най-малкото защото въпреки че ми се вижда невъзможна схема и би нарушила вижданията за информационна ентропия които са в общи линии фундаментални при компресирането на данни, не мога да дам аргумент защо такава схема да е невъзможна.. При всички положения има сложни проблеми за решаване, но ако се абстрахираме от това и въпросните имат решение и изчислителното време не е фактор, в момента не мога да измисля защо тази схема не би сработила.
P.S абе имаше един сериал по HBO, Силициевата Долина, аз не гледам много телевизия, но слушам защото жена ми го намира за забавен, та там ония идиоти май бяха открили големата компресия от нещо в нищо и се опитваха да си капитализират идеята, дочуваха се забавни реплики, ще взема да почна да го гледам ако още го дават.
