Автор Тема: Точни корени?  (Прочетена 17930 пъти)

sharena_sol

  • Гост
Re: Точни корени?
« Отговор #75 -: Jun 19, 2015, 15:37 »
Имам чувството, че сте на път да откриете алгоритъм за трансформация на число от десетична в двоична бройна система, но може би пропускам нещо. :)

Един въпрос - как избирате от всичките възможни полиноми кой точно да ще е "победителя"?
Ако е този с най-големи степени (уж по-голяма компресия) то това ми се струва винаги ще са степените на двойките (като най-малко число), и същото важи и за остатъците след това. Може би не съм разбрал правилно идеята де.

//офф
Иначе Silicon Valley е много добър сериал. Halt and catch fire също не е лош.
« Последна редакция: Jun 19, 2015, 15:39 от sharena_sol »
Активен

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #76 -: Jun 19, 2015, 15:39 »
Имам чувството, че сте на път да откриете алгоритъм за трансформация на число от десетична в двоична бройна система, но може би пропускам нещо. :)

Един въпрос - как избирате от всичките възможни полиноми кой точно да ще е "победителя"?
Ако е този с най-големи степени (уж по-голяма компресия) то това ми се струва винаги ще са степените на двойките (като най-малко число), и същото важи и за остатъците след това. Може би не съм разбрал правилно идеята де.
Аз писах в предишен пост коя би била по-добрата стратегия: избор на най-големи старши (големи) числа. Така с по-малки степени се постига по-малък изходен текст
Активен

0x2B|~0x2B

sharena_sol

  • Гост
Re: Точни корени?
« Отговор #77 -: Jun 19, 2015, 16:02 »
Имам чувството, че сте на път да откриете алгоритъм за трансформация на число от десетична в двоична бройна система, но може би пропускам нещо. :)

Един въпрос - как избирате от всичките възможни полиноми кой точно да ще е "победителя"?
Ако е този с най-големи степени (уж по-голяма компресия) то това ми се струва винаги ще са степените на двойките (като най-малко число), и същото важи и за остатъците след това. Може би не съм разбрал правилно идеята де.
Аз писах в предишен пост коя би била по-добрата стратегия: избор на най-големи старши (големи) числа. Така с по-малки степени се постига по-малък изходен текст

Значи за компресиране на произволно N имаме следния алгоритъм:
1. Търсиш най-голямото просто число P1 < N
2. N = N - P1. //остатъкът
3. Текущото решение+="P1^1"
4. GOTO 1.

И в крайна сметка получаваш: P1^1+P2^1 ... Px^1
т.е. всички степени са единици и също така простите числа не са задължително различни. 

Но къде е ползата от малки степени - нали идеята е точно, че от степенуването щеше да идва компресията.
Активен

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #78 -: Jun 19, 2015, 16:10 »
Значи за компресиране на произволно N имаме следния алгоритъм:
1. Търсиш най-голямото просто число P1 < N
2. N = N - P1. //остатъкът
3. Текущото решение+="P1^1"
4. GOTO 1.

И в крайна сметка получаваш: P1^1+P2^1 ... Px^1
т.е. всички степени са единици и също така простите числа не са задължително различни. 

Но къде е ползата от малки степени - нали идеята е точно, че от степенуването щеше да идва компресията.
Аз го виждам по малко по-различне начин:
1. започвам от sqrt(N) и търся < просто число
2. от остатъка аналогично следващото и така надолу.

Многовариантността може да се провери с корен 3, и нагоре

или започвам от 2 и тръгвам нагоре.
« Последна редакция: Jun 19, 2015, 16:31 от romeo_ninov »
Активен

0x2B|~0x2B

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #79 -: Jun 20, 2015, 02:02 »
Цитат
Аз го виждам по малко по-различне начин:
1. започвам от sqrt(N) и търся < просто число
2. от остатъка аналогично следващото и така надолу.

Многовариантността може да се провери с корен 3, и нагоре

Според мен лоша идея е това със sqrt(N) и надолу. Има една теорема според която вероятността случайно число <N да е просто, клони към 1/ln(N). Това ми се вижда прекалено много, предвид че ние ще трябва да пазим информация за степените на всяко просто число. Сметката набързо е че между 1 и 2**64 имаме 4.158285343076351e+17
 прости числа, които трябва да се представят и това нещо заклевам се ще изяде далеч повече памет, отколкото самото число N представено по "нормалния" начин.

Затова според мен броя на простите числа, които ще използваме трябва да е далеч, далеч по-малък. Това означава по-високи степени и съответно повече място за пазенето им, но това е с порядъци по-пестеливо, отколкото да си позволим да пазим степените (или липсата им) на голям брой прости числа.


Цялата работа и това което доста ме кара да се съмнявам във въпросната чудодейна схема е че на първо четене, каквато и основа за степенуване да изберем по-голяма от 2, би трябвало да сме на далавера....поне така изглежда, обаче нещо ме гризе отвътре че нещата не са толкова прости и нищо не идва ей така отнякъде. Понеже аз поне съм тъп и не мога да докажа обратното, а могат да се дадат лесно примери, където буквално такова представяне би сгазило брутално всеки масово използван алгоритъм за компресия, нещата очевидно са забавни. Ако изключим проблемите при намирането на въпросните степени и според мен това въобще не е толкова тривиална задача, но да речем че има решение, остава въпросът доколко вероятни са въпросните примери и дали в масовия случай такова представяне на входните данни няма да е далеч по-неефективно. За съжаление нито съм достатъчно голяма глава, а и съм одъртял и изпростял и ме мързи да мисля толкова по въпроса. Та вариантът според мен е да се изтества цялата постановка с достатъчно малки числа N и да се измисли някакъв на първо четене работещ, не казано много велик и оптимален алгоритъм за откриването на корените. В процесът според мен ще излязат наяве евентуалните теоретични драми.
« Последна редакция: Jun 20, 2015, 02:21 от gat3way »
Активен

"Knowledge is power" - France is Bacon

4096bits

  • Участник
  • *****
  • Публикации: 3228
    • Профил
Re: Точни корени?
« Отговор #80 -: Jun 20, 2015, 09:43 »
( Тук имаше редакция. Някой можеше да разбере погрешно. )
По-рано споменах за една проба. Повдигнах 2 на степен десет милиона. Полученото число заемаше 3 мегабайта памет. Само то. Каква е стойността му, не мога и да си помисля. Изписването на 3МВ-товото число като str('2 10000000') това са десет байта, срещу 3МВ. Това е идеалния случай. Точен корен. Вероятността да се случи не я зная, каква е, но дори представянето му като сбор от бази и степени да заеме цял ред, това ще са колко... 80-100 байта отново срещу 3МВ памет. Нека към това се включи и предаването по някакъв начин на подредените вероятности на символите. Още 100 байта. Максимум, ако говорим за текст само. А 2^10 000 000 се изписва точно със 3 010 300 символа. В момента нямам време, но утре вероятно ще напиша набързо две малки функцийки за кодирането на, да речем 2 страници текст. И ще го изтествам, да видя колко голямо число ще се получи.
Всичко би трябвало да работи перфектно. Изчислителните мощности са под въпрос.
Простите числа ще видя в движение ли ще ги генерирам или ще ги взема от списък някакъв.

off: Тези от Google наред ли са с акъла?! Свалям си едно .deb файлче и ми изписва "This file can harm your computer!" вместо да почне да дърпа!  >:(
« Последна редакция: Jun 20, 2015, 10:57 от 4096bits »
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.

gat3way

  • Участник
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #81 -: Jun 20, 2015, 14:02 »
Вече показахме че 2 на някоя степен е лоша илюстрация и че RLE компресията ще даде същия, ако не по-добър резултат. Несъмнено е впечатляващо, докато не се замислиш какво биха направили традиционните алгоритми за компресия. Всъщност, вероятно хъфмановото кодиране ще даде по-лош резултат от записа със степента, но RLE кодирането ще даде малко по-добър.

Виж примерно за 3 на някоя степен, не е така или поне не е толкова очевидно. Въпросът е доколко е вероятно големите числа да имат толкова "кратко" представяне.
Активен

"Knowledge is power" - France is Bacon

sharena_sol

  • Гост
Re: Точни корени?
« Отговор #82 -: Jun 20, 2015, 14:41 »
Мисля че това е правилния въпрос:

Въпросът е доколко е вероятно големите числа да имат толкова "кратко" представяне.

Всеки алгоритъм за компресиране работи върху определена част от всички възможни данни. Примерно неможеш да zip-неш zip, нали.

Тази идея със степени на двойките ще работи за числа, които като ги представиш в двоичен вид имат (значително) по-малко 1-ци от колкото 0-ли. И тази "компресия" е еквивалентна на записването на индексите на тези 1-ци, възползвайки се от факта, че са по-малко. Обаче една проста сметка ще покаже, че за числа с дадена дължина N бита, възможните числа при които разпределението на 0ли и 1ци е 50:50 (неработеща "компресия") е много по-голям от тези при които е примерно 90:10 (работеща "компресия").

Затова преди няколко поста се шегувах, че сте на път да измислите алгоритъм за представяне на число от 10чна система в двоична.

Не виждам причина това разсъждение да не работи и за 3-ична система. Или някаква по екзотична като с редица от прости числа. Освен ако нямаш някакви статистически наблюдения и знаше какви числа са по-вероятни да идват на входа за компресия, за да подбереш подходящ базис
« Последна редакция: Jun 20, 2015, 14:46 от sharena_sol »
Активен

romeo_ninov

  • Участник
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #83 -: Jun 22, 2015, 09:20 »
Мисля че това е правилния въпрос:

Въпросът е доколко е вероятно големите числа да имат толкова "кратко" представяне.

Всеки алгоритъм за компресиране работи върху определена част от всички възможни данни. Примерно неможеш да zip-неш zip, нали.
....
Хм, то че трябва да е така, трябва. Но съм попадал на уникални случаи (поне за мен). Gzip, zip ползват доколкото знам zlib но няма проблем да компресираш gz файл със zip и обратното

А за дискусията със степените и простите числа като основи може да се окаже че ще е по-бързо (и достатъчно ефективно)  да се раздели входящия тескт на прости множители и да се записва това. Разбира се при големи множители и/или прости числа нещата се чупят тотално (примерно при RSA ключове). Но иначе опираме до избор на степен т.е. кога xy=z при x и y достатъчно близки. И не знам дали подобно диофантово уравнение има просто и бързо решение, имайки предвид че х трябва и да е просто
Активен

0x2B|~0x2B

4096bits

  • Участник
  • *****
  • Публикации: 3228
    • Профил
Re: Точни корени?
« Отговор #84 -: Feb 27, 2016, 10:59 »
Привет!
Нахвърляно е на грубо, но после ще чистя и оптимизирам, ако мога, но работи. Сега само трябва да измисля начин да разделя the_big_num на сбор от бази и степени и ще има работещо програмче. С ограниченото ми време, ще видим кога ще го стъкмя. Все пак остана последната стъпка само. :)
Активен

As they say in Mexico, "Dasvidaniya!" Down there, that's two vidaniyas.