Linux за българи: Форуми

Програмиране => Общ форум => Темата е започната от: 4096bits в Jun 08, 2015, 20:53



Титла: Точни корени?
Публикувано от: 4096bits в Jun 08, 2015, 20:53
Не съм математик и искам да питам, дали някой знае начин за определяне на това, дали някое число има точен корен? Все тая квадратен или n-ти.

Да допълня, че става въпрос за много големи числа. От порядъка на 300 000 знака до много повече. За проба само записах стойността на едно такова число във файл, който стана 3 МВ голям.


Титла: Re: Точни корени?
Публикувано от: sharena_sol в Jun 08, 2015, 22:44
И аз не съм математик, но ми стана интересно и се порастърски из интернет:

http://en.wikipedia.org/wiki/Nth_root_algorithm

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


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 08, 2015, 23:07
Ами и аз попаднах на това, а и на още доста неща, включително и на едно wiki с алгоритми на всякакви езици, но при положение, че за изчисленията ще трябва време, си помислих, дали няма да е по-бързо, ако просто насека числото с два милиона цифри на парчета и да го направя за всяко. Но искам и да мога да определя, дали някое от тях има точни корени. Да елиминирам неподходящите.


Титла: Re: Точни корени?
Публикувано от: Odido в Jun 09, 2015, 00:53
Без да съм математик ,нито програмист ,но елементарна проверка с един иф от рода на:
ако след коренуването на i  резулата е integer ,да връща true , няма ли да стане?


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 09, 2015, 07:07
Без да съм математик ,нито програмист ,но елементарна проверка с един иф от рода на:
ако след коренуването на i  резулата е integer ,да връща true , няма ли да стане?
А замисляш ли се за сложността на коренуване на число с милиони цифри?

Иначе разбиване на прости множители и следене дали има по четно число от тях е приложим метод


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 09, 2015, 07:46
Целта ми е, да мога да определя, дали числото има точен корени и едва тогава да ги търся.
Елементарно може да се отхвърлят някои числа, като просто се погледне последната цифра. Всички степени завършват на  0, 1, 4, 5, 6, 9.

Odido, целта ми е да избегна точно това изчисление, ако ще е по-бавна тази проверка от проверката дали изобщо числото има точен корен. Ама това не зная, как да направя тази проверка.
Иначе лесно мога да го пусна да се проверява, дали ще е равно на n-та степен на нещо. Ама това, ако го правя, ще трябва да го правя за също толкова безумно много числа. За всяко от тях.
Ако не зная, че 10 000х10 000 е 10 000 000 000, за да проверя кой е корена на 10 000 000 000, няма да искам да умножавам всичко на себе си от 2 нагоре, докато стигна до 10 000. Това ще е бавна проверка. Искам точно нея да избегна.
А сметките са си бавни. Повдигнах за проба 2 степен 10 000 000 и го смята малко под минута. Не търсих как да му кажа, да смята с повече от едно ядро.
Май ще трябва да търся някакъв вариант с GPU, а там ще ми е мътна...


Титла: Re: Точни корени?
Публикувано от: Odido в Jun 09, 2015, 10:35
То другия вариант в този случай ,който ми хрумва е с факторизация ,еднакво неефективен също.За паралелното смятане Gateway ,май няма кой да го стигне тук.Hashkill е чудесен негов пример.


Титла: Re: Точни корени?
Публикувано от: neter в Jun 09, 2015, 11:22
Никой от по-познатите методи за намиране на корен не е ефективен за такива големи числа. Но, както и romeo_ninov предложи, аз бих го пробвал първо как върви с разлагане на прости множители, като обаче (ако нещо не се оплитам в мислите си) не съм съгласен, че трябва да се следи за четен брой от множители, а трябва да се следи за съответни на степента на корена бройки от еднакви множители. Опростен пример с корен пети от 7776:
Цитат
nthroot(7776, 5) = nthroot(2*2*2*2*2*3*3*3*3*3, 5) = nthroot(2*2*2*2*2, 5) * nthroot(3*3*3*3*3, 5) = 2*3 = 6
Присъствието дори на една група от еднакви множители, броят на които не отговаря на степента на корена, води до липсата на целочислен корен.

Правилно си забелязал, че всички степени завършват на 0, 1, 4, 5, 6 и 9, но при четни степени. Ползвай го, за да отсяваш някои от числата, които ти се налага да смяташ. Не съм сигурен някаква проверка за това дали числото не е просто дали няма да доведе до някакъв положителен ефект в отсяването, или само ще внесе допълнително забавяне, но може без изчисление да се пробва поне сравнение с база от текущо известните прости числа, ако твоето не е по-голямо от най-голямото, открито досега - 2^57,885,161 − 1


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 09, 2015, 11:29
Никой от по-познатите методи за намиране на корен не е ефективен за такива големи числа. Но, както и romeo_ninov предложи, аз бих го пробвал първо как върви с разлагане на прости множители, като обаче (ако нещо не се оплитам в мислите си) не съм съгласен, че трябва да се следи за четен брой от множители, а трябва да се следи за съответни на степента на корена бройки от еднакви множители. Опростен пример с корен пети от 7776:
Цитат
nthroot(7776, 5) = nthroot(2*2*2*2*2*3*3*3*3*3, 5) = nthroot(2*2*2*2*2, 5) * nthroot(3*3*3*3*3, 5) = 2*3 = 6
....
Съгласен. Аз приемам (не знам защо) че говорим само за квадратен корен/степен. От там и дефинирането ми за четни/нечетни степени на простите множители :)


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 09, 2015, 11:37
Предполагам проблема е, че ми липсват основни знания за числата.
И то основно за простите числа, което е по-важното. Иначе голямото число е произведение на много множители - няма как да е просто. Ще потърся още инфо в нета и ще видя, какво ще правя. Изглежда не е прост въпрос, който ей така да намери отговор. Преди време исках да се позанимавам с това, дето сега ми се върти в главата, но тогава машините бяха порядъци назад от това, което ми беше нужно. Сега са 64 битови, многоядрени. Ама малко почват да ме гризат съмнения отново. Ще видим.  :)

Коренът изобщо не е квадратен. Може 4954-ти например на 6816888133548165668417941006778464 :D
Това последното е малко. Сложете още няколко хиляди цифри след последната.


Титла: Re: Точни корени?
Публикувано от: neter в Jun 09, 2015, 12:38
Между другото, преди време покрай една задача с корени ми беше хрумнал хипотетичен алгоритъм за относителна проверка дали дадено число има целочислен квадратен корен, но остана само разписан с няколко числа за проба в текстово файлче, не ми беше останало време да го засиля за сериозна проба, а после и съм забравил за него, но като стана дума сега...

Цитат
Гледаме числото, на което търсим корен, отзад напред. Първо се прави проверка дали първата (реално последната) цифра е 0, 1, 4, 5, 6 или 9. Ако не е, то числото няма целочислен корен. Ако е, продължаваме нататък. Намираме цифра, степента на която завършва на първата цифра от числото, на което търсим корен. Запазваме си наум първата цифра от степента на намерената цифра. Ако намерените цифри са повече от една, запазваме си наум всички първи цифри на степените им. След това умножаваме първата и втората цифра на числото, на което търсим корен, полученото число го умножаваме по 2 и резултатът го сумираме със запазената наум цифра, след което проверяваме дали последната цифра от резултата е 0, 1, 4, 5, 6 или 9. Ако запазените наум цифри са били повече от една, правим отделни проверки за сума с всяка от тях поотделно. Ако няма резултат, завършващ на някоя от търсените цифри, то методът не може да даде гаранция, че има целочислен корен на търсеното число. Ако има подходящ резултат, продължаваме нататък, като си запазваме наум първата цифра от умножението на първата и втората цифра, но само ако е двуцифрено, иначе 0. Умножаваме втората и третата цифра от числото, на което търсим корен, сумираме го със запазената наум цифра и последната цифра от резултата отново ще ни покаже дали да продължим напред, или методът не дава гаранция за това число. Ако продължаваме, то правим същата проверка за резултата от третата и четвъртата цифра от числото, на което търсим корен, ползвайки наум първата цифра от предходното умножение (на втората и третата цифра), и така нататък за всички цифри на числото. Ако методът работи, то успешното обхождане на всички цифри на числото ще ни даде гаранция, че даденото число има целочислен корен, като неуспешното обхождане не е показател за това дали числото има целочислен корен, или не.

Пример:
Търси се sqrt(343396) и гледаме числото отзад напред.
6 е коректна цифра, т.е. е една от 0, 1, 4, 5, 6 и 9
6*6 = 36; последната цифра от резултата съвпада с първата цифра на числото, запазваме наум 3
9*6 = 54; 54+54+3 = 111; последната цифра е коректна и запазваме наум 5
3*9 = 27; 27+27+5 = 59; последната цифра е коректна и запазваме наум 2
3*3 = 9; 9+9+2 = 20; последната цифра е коректна и запазваме наум 0
4*3 = 12; 12+12+0 = 24; последната цифра е коректна и запазваме наум 1
3*4 = 12; 12+12+1 = 25; последната цифра е коректна
Успешното обхождане на цифрите показва, че числото има точен корен.

При възникване на комбинация от свободно време и муза ще го разиграя по-стабилно при мен (стига да не го забравя пак), но ако на някой му е интересно и има възможност, да действа. Нямам идея дали няма да се окаже пълна глупост, или дали всъщност не съществува подобен метод отдавна, както и въобще не съм го мислил какво ще е положението с неквадратни корени, но... поне да споделя :)


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 09, 2015, 12:59
Ще го видя и аз. То начини не е като да няма сигурно. Просто се чудя, може да се случи в разумно време. Благодаря!
Като го направя, ще споделя, за какво ми е.


Титла: Re: Точни корени?
Публикувано от: neter в Jun 09, 2015, 20:41
Ще го видя и аз.
Зарежи горната идея. Сега, като я прочетох на отрезвена от онази задача глава, се усетих, че премахването на цифри от ляво надясно би запазило възможността за успешно обхождане на цифрите, но скъсеното число почти винаги няма целочислен корен, като същото важи и при добавяне на подходящи цифри отпред на числото, така че методът не гарантира нищо, а аз съм се заблудил от щастливи съвпадения ::)

А като каза, че твоите големи числа винаги ще са произведение на много множители, дали отделните множители ще са ти известни предварително и дали размерът им ще бъде в някакъв известен диапазон?

П.П.: Чакам с нетърпение да кажеш за какъв дявол ги смяташ тези корени, че ми стана любопитно още когато спомена за сметки с големи числа в темата за OpenCV :)


Титла: Re: Точни корени?
Публикувано от: remotexx в Jun 09, 2015, 20:54
Колега..
да беше дал по-подробна информация или един пример барем... че ми стана интересно
Търсиш да има единствен корен, всички възможни, или някой конкретен (min, max)?
напр. 16 = 2^4, 4^2 т.е. в общия случай имаме Min, Max и/ли цяло мнонжество от решения


http://stackoverflow.com/questions/15978781/how-to-find-integer-nth-roots
алгоритъма е тук
http://en.wikipedia.org/wiki/Nth_root_algorithm

или gmpy2.iroot, gmpy2.isqrt
http://stackoverflow.com/questions/27607711/check-if-an-integer-has-perfect-nth-root-python


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 09, 2015, 20:58
...
А като каза, че твоите големи числа винаги ще са произведение на много множители, дали отделните множители ще са ти известни предварително и дали размерът им ще бъде в някакъв известен диапазон?
....
не винаги. С много голяма вероятност, но не винаги :) Все ще се намерят сред тях и прости и точни квадрати и произведение на две прости числа.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 09, 2015, 21:57
Не търся единствен корен, не търся и точен корен на някое число. Може и да няма. Ако няма точен корен, може да го представя и като сбор от точни корени, пък било то накрая и така.

big_integer = x^a + y^b + z^c + 14

Например.

А, ако може да е точен корен, още по добре. Например нещо от вида: big_integer = 5086283470**64625205.

Отделните множители ще са известни. Те също ще са степени на някое число. А big_one ще е тяхно произведение. Ако до десетине дена не намеря решение, ще се опитам да обясня, какво точно искам да постигна. Или да намеря някой математик от ТУ тук в София, да го видя, какво ще каже той.


Титла: Re: Точни корени?
Публикувано от: neter в Jun 09, 2015, 22:34
В такъв случай става още по-препоръчително да използваш метода за разлагане на прости множители. И щом предварително ще са ти известни някакви множители, то е по-добре да разлагаш тях, вместо после да мъчиш голямото число - така наизуст не съм сигурен по-какъв начин ще се отрази това на общото време за разлагане, но дори и да не доведе до спестено време, то поне ще доведе до спестена памет. И тук базата с известните прости числа (или само част от нея, ако не очакваш известните начални множители да надхвърлят някаква определена стойност) ще ти е от полза - трябва да се прави сравнение с нея преди всеки цикъл на разлагане на дадено число, което може да спести доста завъртания на цикли.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 09, 2015, 22:48
Не търся единствен корен, не търся и точен корен на някое число. Може и да няма. Ако няма точен корен, може да го представя и като сбор от точни корени, пък било то накрая и така.

...
Само за сведение опитай това:
Код:
man factor


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 09, 2015, 23:14
Ако не се търси корен квадратен, а просто целочислените делители, тогава има много подходи - доколко практични зависи от това с колко големи числа оперираш. Най-простият вариант е описан в уикипедия (с питонска имплементация):

http://en.wikipedia.org/wiki/Trial_division

Това обаче не е много практично дори за големи 32-битови числа. За числата от стотици хиляди цифри...ами успех. Ако откриеш бърз и практичен начин, покрай другото ще счупиш RSA, което ще е далеч по-забавно предполагам.


Титла: Re: Точни корени?
Публикувано от: sharena_sol в Jun 10, 2015, 13:13
За целочислени делители има ефикасен алгоритъм, но трябва да имате под ръка квантов компютър  :).

За коренуване (с конкретен корен) може би е най-добре е с числени методи (Нютон примерно)


Титла: Re: Точни корени?
Публикувано от: edmon в Jun 10, 2015, 14:23
ако искаш да разбереш дали числото 1341230917263912983714692837146239418732649182734 е някое друго число, което е повдигнато на някоя степен....
всъщност това ли е въпроса преди да продължа да умувам?


Титла: Re: Точни корени?
Публикувано от: remotexx в Jun 10, 2015, 21:00
т.е. само да уточня че тези ВСИЧКИТЕ са неизвестни - нали така: a,b,c,d=14,x,y,z
big_integer = x^a + y^b + z^c + 14

тогава така
I want to find the greatest integer less than or equal to the kth root of n
http://stackoverflow.com/questions/15978781/how-to-find-integer-nth-roots

напр big_integer=10 и (the greatest integer less than or equal to the kth root of n) = 8 = 2^3
то 10 = 2^3+2
11 = 2^3+3

те избираш n напр. = 2 и намираш най-близкото до него 2^P < big_integer
big_integer = 2^P + (big_integer - 2^P)
после може да продължиш аналогично за (big_integer - 2^P)
също така може и да пробваш с n=3 и т.н. докато ти писне или решиш че вече ползва прекалено много процесорно време...


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 15, 2015, 19:41
ако искаш да разбереш дали числото 1341230917263912983714692837146239418732649182734 е някое друго число, което е повдигнато на някоя степен....
всъщност това ли е въпроса преди да продължа да умувам?
Да, основно искам да разбера, дали има начин да определя, някое число дали има точен корен, преди изобщо да търся базата и на какво е повдигната. Ако е, може да пробвам да ги търся.
Иначе голямото число, ще е прозиведение на степени на прости числа.
 Python-а малко ме обърка, ама днес по-рано го преборих. For loop не е като в С и се чудих по едно време що ми дава грешки  ;D. Нямах време до сега да се занимавам с въпроса, но половината програмка е готова.
Имам един въпрос относно Python. Как да сортирам dictionary, но според стойностите, не според ключа. Или сам трябва да си го напиша. То лесно ще хвърля всичко в нов речник, според някакви условия, но питам дали няма нещо готово. Мразя да губя време и да откривам топлата вода.


Титла: Re: Точни корени?
Публикувано от: PaperNick в Jun 15, 2015, 20:08
Имам един въпрос относно Python. Как да сортирам dictionary, но според стойностите, не според ключа.
https://docs.python.org/dev/library/collections.html#ordereddict-examples-and-recipes


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 15, 2015, 22:29
for цикъла е една от големите простотии в питон, защото всъщност for е итератор и оперира върху list-ове, някак тривиалното изпълнение с брояч и условие като в нормалните езици не е на почит и това е брутална простотия, особено за човек дето идва от C или подобен език. А за да е още по-забавно, тривиалният for цикъл в питон  - for counter in range(start,end) - всъщност създава списък от стойности между start и end и го пази в паметта и сега представи си как разликата между двете е няколко милиарда и изгърмяваш цялата физическа памет на машината с един прост цикъл. Да не говорим колко още по-глупаво е ако някъде в цикъла имаш условие и при достигането му, break-ваш, язък за разхищението на памет.

Та това е от първите неща, които човек научава - да ползва xrange вместо range, защото xrange е "генератор", т.е не се създава първоначално целия лист в паметта и после да се обхожда, а всеки елемент се генерира динамично. Обаче човек много скоро се научава да е мързелив, поради тази причина за "малки" цикли обикновено ползвам range, за "големи" цикли ползвам xrange.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 15, 2015, 22:46
Гейт, мерси за това уточнение. Големия цикъл още не е дошъл, но скоро ще му дойде и на него времето.
Всъщност, реших, че не ми трябва да подреждам речника, ми само да нахакам в подобаващ ред ключовете един след друг, според стойностите им някъде, че да мога да ги обходя после.


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 16, 2015, 00:17
Между другото. не знам какъв е казуса с твоя dict, но имам странното усещане че може би не ти трябва dict за да го реализираш това...щом ти трябва да сортираш по key-ове. Но не знам де.

Апропо, списъците в питон-а са много забавно нещо. Със съвсем леко усилие това се превръща в напълно функционален стек или опашка, в смисъл не е чак наготово, но с много малко усилия. Та ако реда на вкарване определя всичко, никакво малоумно сортиране не ти трябва, то и вероятно ще е бавно както повечето неща в този език :)

Но именно тоя момент с лесното организиране на разни FIFO/LIFO структури от данни като list - което в C обикновено троши нерви и време най-малкото заради memory management-а - много ми допада. Само няколко реда код и обикновено работи, трудно е да се изсереш отгоре даже.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 16, 2015, 00:35
Ами така си написах функцията, защото така ми дойде на акъл. Трябваше да обходя едни неща и да им направя статистика, колко често се срещат във файла.
Та понеже отскоро се запознавам с питон, от три-четири дена и речника ми дойде най-подходящ като структура, а от де да зная, че трудно се подрежда. Одеве гледах за тези неща. Питат хората като луди. Та май ще ги извадя от речника и ще нахакам ключовете, според стойността във обикновен лист. То речника май и по индекс не можеш го достъпи.
А относно списъците ... ами да. Днес дори четох в едно pdf-че, че май си има тулче за тази работа. FIFO от обикновен списък или tuple. Изобщо май от всичко, дето може да му се приложи read() и write().
Реда на вкарване е произволен, защото входящите данни са такива. И като ги обхождам, само вдигам брояча-стойността, ако са в речника или просто добавям нов ключ със стойност 1. Ако ги няма там.

Код:
def sfreq(in_file):

f = in_file
freq = {}

for k in f:
if freq.has_key(k):
freq[k] += 1
else:
freq[k] = 1

return freq

Даже си мисля, че това else може да е излишно, но не съм пробвал. Дали ще вмъкне нов елемент, ако го махна?


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 16, 2015, 01:26
Не мисля че речникът можеш да го индексираш. Ако нещата дето могат да се срещат не са ужасно много, аз бих обърнал нещата, бих си измислил хеш функция която да връща от нещото целочислена стойност в някакъв смислен range където да не страдаме толкова от колизии и тогава пак да си го организирам като списък, макар и с разхищения, просто понеже защото се индексира лесно и бързо...обаче това зависи от това колко възможни стойности можеш да индексираш и колко красива е хеш функцията. И пак има достатъчно неизвестни, та не знам дали е оптималното решение. Проблемът с подбирането на структурите данни, видиш ли. Според мен това е най-забавното нещо в дращенето на код като цяло и  е доста жалко че малоумната простотия с нечии добри практики и патърни се приема леко догматично - според мен без да е обременен с глупости, човек с времето сам си стига до изводите и решенията и после не мисли излишно.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 16, 2015, 02:00
Сега, от този речник лесно може да се измъкнат за ушите първо ключовете с най-големи стойности и от там в низходящ ред и ще си дойде всичко на мястото. На мен ми трябват само ключовете подредени, според стойностите им, но не и самите стойности. Вече. Та май ще добавя в това още няколко реда и ще връща сортиран в низходящ ред ключове, според стойностите им, но вече ще е list. Имаше май някакви методи max и min, но за какво бяха. Толкова ми мина през главата. Малко блокирам вече и ще си дам два дена почивка от четенето.
Иначе в няма да се генерира прекалено голям списък в речника. Той ще е временен.
Или да видя как да го направя вместо с речник с tuples. Че там всичко може си блъскам. Малко ми бръмна главата от четене и нещо блокирам вече.
А иначе основния ми въпрос с корена... Няма да е лесно и няма да е сигурно нещо бързо работещо. Достатъчно бързо. И като гледам, няма само един начин, та ще трябва и правилен подход. Започва вече да ме интересува, не колко бързо ще го смята. Не чак толкова, а да е точно. Това е критично.


Титла: Re: Точни корени?
Публикувано от: kierenski в Jun 16, 2015, 09:03
Всичко много хубаво, а някой питал ли се е с каква точност трябва да са тези големи числа, защото едно коренуване на число с плаваща запетая с експонента става много бързо и слесно от колкото всеки друг тип.

например 1.1е3000000 така е представено число с 3 милиона нули отзад.
Прави се двоично както го правят процесорите на компютрите само че с много повече от 128 битови регистри.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 16, 2015, 10:56
Големите числа са  с L на края и се представят достатъчно точно. До последния знак. Точността трябва да е при извличането на nth корен. Ще дам на пауза за малко.


Титла: Re: Точни корени?
Публикувано от: Odido в Jun 16, 2015, 13:24
докато четях разни java неща попаднах на това https://en.wikipedia.org/wiki/Fast_inverse_square_root ,което мисля донякъде е във връзка с темата :)


Титла: Re: Точни корени?
Публикувано от: kierenski в Jun 16, 2015, 18:54
Големите числа са  с L на края и се представят достатъчно точно. До последния знак. Точността трябва да е при извличането на nth корен. Ще дам на пауза за малко.

sqrt(1000e530000000)= 316,2277660168379e264999999
не разбрах, тази точност след запетаята достатъчна ли е?

speedcrunch е програма калкулатор която може да смята стойности с такъв диапазон заради ограниченията на процесора

да ли са необходими още цифри след запетаята на резултата?


Титла: Re: Точни корени?
Публикувано от: Acho в Jun 16, 2015, 19:03
И каква е целта с точни корени на тия грамаданските числа ?


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 16, 2015, 20:01
Точността при извличането, пресмятането на базата и коренът трябва да е абсолютна. За да може след това остатъкът от голямото число да се подложи на същото, докато не остане нищо. Става въпрос за обработка на данни и не може да има допуск на грешка. Един знак да се сбърка и всичко отива на кино.

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


Титла: Re: Точни корени?
Публикувано от: gat3way в 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, Силициевата Долина, аз не гледам много телевизия, но слушам защото жена ми го намира за забавен, та там ония идиоти май бяха открили големата компресия от нещо в нищо и се опитваха да си капитализират идеята, дочуваха се забавни реплики, ще взема да почна да го гледам ако още го дават.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 17, 2015, 03:16
Дойдохме си на думата. Точно за компресия става въпрос и то за такава с безпрецедентна ефективност, ако гледаме обем вход-изход. За времето вече все още не се знае. Но времето е относително, защото виждам, че няма да е лесно. Ако се направи работеща програма, тя лесно може да се преправи във нещо, което да мяза на Grid Computing и да се използват почти напълно свободните ресурси на безчисления брой хора с компютри по джобовете и домовете, офисите, къде ли не. След като това се прави за bitcoin, може да се направи за всичко, което иска тежки изчисления.
Само си представи, цялата Народна библиотека, да се събере на две дискети.  :D
Нямам знанията за да го изчисля, но си мисля, че колкото по-голям обем са входните данни, толкова по-голяма компресия се постига.

Това дали може да ми помогне:
https://github.com/undefx/vecpy

Бъкел ме няма в тези неща. Да го накарам да бачка на всичките cpu-та. Без едно например. Та и с Hypertrading. Ама това последното не съм сигурен дали може да се програмира.


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 17, 2015, 08:47
Е ти си поставяш каруцата пред коня с тия неща, първо трябва да измислиш далеч по-сложното и то е как да представяш числото като полином от вида a + bx +cy^2 + dz^3 +.... защото това ми се вижда далеч по-сложната част. Чисто интуитивно, би трябвало винаги да има функция, която да удовлетворява това, чисто практически, да я намериш е доста сложна работа, на мен ми се струва че това е NP проблем, лесно можеш да докажеш че нещо е решението, но много по-трудно можеш да намериш въпросното решение. Алгоритъмът за откриването на решението много вероятно може да се окаже че отнема непрактично много време дори за изчислителните възможности на цялото човечество (примерно).


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 17, 2015, 08:58
О, аз не съм тръгнал да пиша нещо за четирите ядра, просто ми попадна, докато гледах, какви модулчета за python са налични из нета.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 17, 2015, 14:50
Не я зная тази теорема, какво казва, но това работи. Трудността идва от тези неизбежни изчисления, за които става въпрос. И това са изчисления с цели реални числа. Проблемът преди години беше, че машините не можеха да се справят. Сега е различно и като сравня възможностите на тогавашните процесорчета със сегашните, обема на оперативната памет... Дано да са достатъчни.
Като имам няколко минутки в повече ще ти пиша какъв е начина. Пробвал съм го с по-малки текстове например и работи.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 17, 2015, 15:01
А не е ли по-разумно да се пробва компресията като полином от степени на простите числа. Така операциите ще започват с делене и то от малките числа (2,3,5,7,11...) Тогава няма да има никакъв смисъл от коренуване
a=2**n1+3**n2+5**n3.......


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 17, 2015, 15:59
Може да го опростим още, да търсим полином от вида Н = 2^x + y

И това е изключително лесно да се намери. В двоичен вид е елементарно да направиш проверка дали едно число е степен на 2 - просто всичките му битове са вдигнати, а броя на битовете е степента x.  Оттам вадим разликата между N и най-близката степен на 2, което също е тривиална операция. Всичко това може да стане изключително бързо дори на много слаб хардуер.

Обаче като се замисля, това няма да даде прилична компресия - в смисъл в ограничени случаи ще даде огромно "смачкване" на данните и тези случаи са точно когато входната стойност е почти изцяло с вдигнати битове и някъде чак накрая има някоя нула. В този същият случай обаче не се знае дали не само Хъфмановото кодиране, ами по-прости неща като RLE няма да дадат сходни, ако не и по-добри резултати.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 17, 2015, 16:14
Може да го опростим още, да търсим полином от вида Н = 2^x + y

....
Ако го опростиш няма да получиш (в големия процент от случаи) "компресия". Но ако го разтегнеш за всички възможни степени и запазиш само степените (си мисля) че ще има голяма ползва. Е, остава въпроса с (по един или друг начин) разделяне на число на прости множители, което за големи числа си е проблем.
Примерно (генерирал съм си го)
300906919255768968177623915255094482900212916526944779768385151305785040175803217554309662569498001352439876822843377378122675403710898517651059802804979798484768641976994743857560231992664435245802456382249522383597979651442019225572816383785005406056754780222000619909597391286617260436123534003960357295911168594391309113033953417754701317843801520417515248539351050470639392268748190736100952871290555680911214354764595970607937172882128981909292041653936988944923703745042109601961887410699745590622148961742015336425112037422529072101537873657660270761184997490019018360201880218486096430110214122064160885687464714204013733656266401999694634058399274930385914806286217392505488165569381700994244910242994864437795284622122256580299155641751872970391706917530334627032421438448735142261070333009765236602176970314664389375273450412548052549287

се запазва като (десетични числа)
1001,1002,1003,1004
което прави компресия 19/850=1:50. Ако се компресира записа на степените под формата на двоични числа ще заеме 4*2 байта + 3 разделителя  (по байт) = 11 байта, докато числото в двоичен вид = 10^850 ~ 2^2550 = 318 байта, което си е почти 1:30 компресия


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 17, 2015, 16:38
Ами ние това може да го правим итеративно с остатъка от изваждането всъщност, така ще стигнем лесно до представяне от вида 2^x + 2^y + 2^z + ....

Но честно казано не знам дали отново ще намажем особено.

Между другото, възниква един интересен казус:

Цитат
python
Python 2.7.9 (default, Dec 11 2014, 08:58:12)
[GCC 4.9.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.

>>> 2**1001 + 2**1002 + 2**1003 + 2**1004
321452582155880196284527514718000543168421443511660082233125116511105315337480836747959513644708757438278401875265944047556143585707694213079537327240957244118037033244726929562632238151871134256338625464591394249507458238021963026774966318382311887437135894330596265029812894949578731605116170042081280L

Това число е различно от твоето и ми е чудно кое от двете е вярно и дали питона или това което ти си ползвал за да го сметнеш, грешат. Или третия вариант - просто не съм разбрал добре какво имаш предвид.

Най-вероятно аз не съм те разбрал обаче, защото ако питон-а смята вярно, то "уловката" става ясна много бързо...

Цитат
>>> bin(2**1001 + 2**1002 + 2**1003 + 2**1004)
'0b111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 17, 2015, 16:47
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).
Аз ползвах bc:

Код:
2^1001+3^1002+5^1003+7^1004
30090691925576896817762391525509448290021291652694477976838515130578\
50401758032175543096625694980013524398768228433773781226754037108985\
17651059802804979798484768641976994743857560231992664435245802456382\
24952238359797965144201922557281638378500540605675478022200061990959\
73912866172604361235340039603572959111685943913091130339534177547013\
17843801520417515248539351050470639392268748190736100952871290555680\
91121435476459597060793717288212898190929204165393698894492370374504\
21096019618874106997455906221489617420153364251120374225290721015378\
73657660270761184997490019018360201880218486096430110214122064160885\
68746471420401373365626640199969463405839927493038591480628621739250\
54881655693817009942449102429948644377952846221222565802991556417518\
72970391706917530334627032421438448735142261070333009765236602176970\
314664389375273450412548052549287


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 17, 2015, 16:54
Дам, ясно е къде е разминаването.

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


Титла: Re: Точни корени?
Публикувано от: Naka в Jun 17, 2015, 17:07
Може да го опростим още, да търсим полином от вида Н = 2^x + y

a=2**n1+3**n2+5**n3.......
H=2**n1+3**n2+5**n3.... + y

А не е ли ключа от бараката в остатъка +y

Независимо как се разлага числото, да се търси най-близката стойност до оригиналното число и след това само да се прибави остатъка y така че да стане същото.

Обаче полинома трябва така да се намери че да бъде възможно най-близък до оригиналното число т.е. y да бъде възможно най-късичък. щото ще трябва и y-то да съхраним.
ще е много интересно ако се намери такова разложение че y да бъде 1, 3... 17,.... 50, ..12345, ....0


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 17, 2015, 17:14
Дам, ясно е къде е разминаването.

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


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 17, 2015, 17:16
...

А не е ли ключа от бараката в остатъка +y

....
Към остатъка можем да приложим същия алгоритъм докато получим остатък < от най-високата степен. Което ще е приемливо за съхранение


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 17, 2015, 17:21
Виждам и още един проблем, но той е с представянето и не е огромен. За да има задачата решение, ще трябва да позволим нулевата степен, тоест да добавяме 1. В противен случай много лесно мога да дам примери за числа, които не могат да се разложат на сбор от степенувани прости числа. Но ще трябва да измислим и как да кодираме нулева степен и как да кодираме "степен която не вземаме предвид",


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 17, 2015, 17:24
Виждам и още един проблем, но той е с представянето и не е огромен. За да има задачата решение, ще трябва да позволим нулевата степен, тоест да добавяме 1. В противен случай много лесно мога да дам примери за числа, които не могат да се разложат на сбор от степенувани прости числа. Но ще трябва да измислим и как да кодираме нулева степен и как да кодираме "степен която не вземаме предвид",
Мда, може да имаме 2**1+3**0+0*(5**0)+7**2 (само пример)
Но това е малка грижа, само пакетиране. Също трябва да се помисли и за разделителя между степените :)


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 17, 2015, 17:30
Радвам се, че ви стана интересно. Само да се прибера и да седна да почина малко и ще напиша точно за какво става въпрос. Има я и нулевата степен.


Титла: Re: Точни корени?
Публикувано от: remotexx в Jun 17, 2015, 21:26
хехех ще трябва да почакаме още маалко - докато няколко Кю-бита станат по няколко цента единия и тогава вече ще е лесно, но колкото по-наближаваме границата ще става и по-трудно
https://en.wikipedia.org/wiki/Pareto_efficiency

Едно време wavelet компресията ми се струваше бавна, вече не чак толкова..


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 18, 2015, 00:41
Не задължително. В смисъл не отхвърлям възможността някоя голяма математическа глава да измисли хитър алгоритъм по който въпросната операция да стане напълно практична с наличния хардуер за прилично големи входни стойности. Все пак такива неща се случват, макар и бавно с други подобни проблеми, примерно факторизацията на целочислени стойности. Всъщност, въпросната наша постановка е напълно реална и възможна и в момента с "тривиални" методи - просто не за толкова големи стойности колкото би ни се искало, за да можем да намажем достатъчно ефективна компресия.

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

Идеята че въпросното "компресиране" може да стане по съвсем различен начин - демек ние ще позволим материята да се "компресира" достатъчно много че да започне не само термоядрена реакция, ами и нещото да се видоизмени и да заприлича на някаква мини неутронна звезда примерно - и от това нещо по желание да възтановим точно първоначалната конфигурация от песъчинки и силно разреден газ само защото сме открили някакви чисто математически съотношения между някакви параметри на тази система и въпросните съотношения са далеч по-сбити от информацията за възможните конфигурации на атомите и техните връзки в молекулите, е забавна идея. Звучи като някаква доста грозна математическа перверзия. Това религиозните хора ще го намразят, защото ще се окаже че сме по-добър Господ от техния Господ и можем по-ефективно да организираме там божествената реалност.


В смисъл аз поне много обичам да си обяснявам нещата с аналогии, а не съм физик за да правя точно такива аналогии, но пък и не се сещам за някаква по-добра в момента, така че се извинявам ако цялото това изглежда доста нелепо.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 18, 2015, 15:21
...
В смисъл аз поне много обичам да си обяснявам нещата с аналогии, а не съм физик за да правя точно такива аналогии, но пък и не се сещам за някаква по-добра в момента, така че се извинявам ако цялото това изглежда доста нелепо.
Ти изби рибата и разката мамата на ентропията :D.
Иначе има добра идея в думите ти (аз също не съм физик). Но в горната идея (според мен) не играем с ентропия въобще. Ние просто сменяме представянето на числото (входящия текст). И се опитваме да намерим такова представяне, което да може да се представи с много по-малко симвили (и наричаме това компресия).


Титла: Re: Точни корени?
Публикувано от: sharena_sol в Jun 18, 2015, 16:06
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).

Добре де но какво е предимството на простите числа в този случай. Те са точно толкова на брой колкото и Естествените числа и в този контекст не са с нищо по-специални (виж ако беше разлагане на прости множители е друго, но при полиномите не виждам с какво са по-различни от кои да е други цели изброими положителни числа - примерно степените на 2)

Ако разбирам идеята е да изберете някакъв "базис" и да представяте данните като координати/вектор в този "базис" макар че в случая един и същи вектор има повече от едно преставяне като полином примерно така че не е баш линейно пространство.

Примерно полином с допустими коефициенти 0 или 1ца и "базис" степени на двойката си е точно както и ти казваш бинарното представяне на това число/данни ( и в случая има единствено представяне) но ако искаш да покриеш цялото пространство (всички възможни числа) то тогава не правиш никаква компресия, а просто си го записваш с нули и единици (както си се записва и сега в паметта/диска-а).

Струва ми се че какъвто и друг "базис" да избереш ситуацията ще е подобна.

Имам спомен преди време, че съм чел за подобен подход при, който обаче имаш таблица на най-често срещаните (статистически спрямо домейна на приложение) компоненти и тях ги енкодваш с по-малко битове, за сметка на по-рядко срещаните. В най-лошия случай нямаш голяма полза, но пък средно печелиш нещо.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 18, 2015, 16:15
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).

Добре де но какво е предимството на простите числа в този случай. Те са точно толкова на брой колкото и Естествените числа и в този контекст не са с нищо по-специални (виж ако беше разлагане на прости множители е друго, но при полиномите не виждам с какво са по-различни от кои да е други цели изброими положителни числа - примерно степените на 2)
...
Дребното предимство е че изрязвам голяма част от многовариантността и имам уникалност на основите. Освен това скоростта на нарастване на простите числа е по-голяма.
Вярно е че има варианти и за по-къси записи. Например 18446744073709551615 има доста къс запис (264-1)
Но крайната идея е да имаме унифициран метод за запис, който да е много по-кратък (статистически)


Титла: Re: Точни корени?
Публикувано от: sharena_sol в Jun 18, 2015, 18:35
Мне, степени на две са ти бинарното число. Докато аз искам да играя с прости числа ( и неограничено число за степен).

Добре де но какво е предимството на простите числа в този случай. Те са точно толкова на брой колкото и Естествените числа и в този контекст не са с нищо по-специални (виж ако беше разлагане на прости множители е друго, но при полиномите не виждам с какво са по-различни от кои да е други цели изброими положителни числа - примерно степените на 2)
...
Дребното предимство е че изрязвам голяма част от многовариантността и имам уникалност на основите. Освен това скоростта на нарастване на простите числа е по-голяма.
Вярно е че има варианти и за по-къси записи. Например 18446744073709551615 има доста къс запис (264-1)
Но крайната идея е да имаме унифициран метод за запис, който да е много по-кратък (статистически)

От друга страна са много по-трудни за генериране (е добре може да ползваш таблица с вече известните прости числа, но все пак имаш ограничение след което незнаеш следващото поред просто числа защото все още никой не го е открил)

Предполагам че нарастват по-бързо от степените на 2 но пък и предполагам можеш да измислиш друга редица, която нараства още по-бързо (незнам, примерно N**N**N**N...**N (N пъти) :) ) но къде е златния момент където една редица започва да нараства прекалено бързо за да е полезна, и къде е прекалено бавна - незнам.

Иначе да - трябва да е унифицирано представянето за това не споря.


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 19, 2015, 08:51
Е как, и да не го е открил, ще циклиш числа нагоре и ще ги тестваш дали са прости, примерно с miller-rabin. Но това е прекалено теоретично - значи ако стигнеш дотам да ползваш толкова големи прости числа, че още никой да не ги е открил, значи ще имаш далеч по-големи проблем после да ги степенуваш така или иначе.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 19, 2015, 09:16
....
От друга страна са много по-трудни за генериране (е добре може да ползваш таблица с вече известните прости числа, но все пак имаш ограничение след което незнаеш следващото поред просто числа защото все още никой не го е открил)

Предполагам че нарастват по-бързо от степените на 2 но пък и предполагам можеш да измислиш друга редица, която нараства още по-бързо (незнам, примерно N**N**N**N...**N (N пъти) :) ) но къде е златния момент където една редица започва да нараства прекалено бързо за да е полезна, и къде е прекалено бавна - незнам.

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


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 19, 2015, 10:48
То това ще се наложи, най-малкото защото изчислителните ни възможности не са безкрайни.

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


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 19, 2015, 10:50
Правилно! Записването на почти което и да е число като база и степен, заема по-малко памет, отколкото записа на самото число. Това е така дори за сравнително малки числа, като например 36. Което се представя двоично със 100100. Ако е със база и степен 110 10. Бит по-малко. Това е и идеята по-общо.
Употребата на прости числа се налага от самосебе си, но аз не мога да го обясня, така, че да ми допадне обяснението на мен самия, въпреки, че разбираз причината. Нямам знанията и езика за това.
Та ето какво се случва:
Текста просто се закодира като бази и степени.
Първо се взима текста и се определя честотата на срещаните вътре символи, за да може да се облекчат в последствие сметките.
Например името Бойко Борисов. Според честотата на срещане, се подреждат символите и в този ред.
'оБйкрв ис'
Всеки знак по своя ред в оригиналния текст се изразява като поредното просто число в редицата на всичките прости числа. Разбира се трябват ни само толкова, колкото е дължината на текста. Започва се от 2, 3, 5 и т.н.
Позицията на всеки знак от посланието, във подредения по честотата на срещане запис, се определя от степента.
Така буквата `o` като най-често срещана в случая, ще се представи като степен 1. Буквата `Б` ще се представя като степен 2. В предния си пост казах, че ще има и степен 0. Това нормално в един текст ще бъде интервалът, защото се среща най-често.
И Бойко Борисов се представя вече като бази и степени.
2^2х3^1х5^3х7^5х11^1х13^8х17^2х19^1х23^6х29^9х31=10х37^1х41^7
Дано някъде не съм сбъркал. Бях пропуснал в двишение знаците след интервала, та ги добавих. Но така стана и по-прегледно.
Полученото число е
15755314003698233343822284213372425367950000178844077447600722128478500L
И вече това число може да се представи самото то като база и степен, ако има точен корен. Ако няма, може да се представи като сбор от бази и степени.
При няколко страници текст или няколко мегабайта текст, целия вход може да се представи като сбор от бази и степени на половин ред тект, може би и по-малко. Ако имаме късмет да има точен корен, ще се представи просто като база, степен и това ще бъде всичко. Няколко, петнайситена или нека са тридесет напримен символа, за сметка на няколко мегабайта.
Това е целта. Проблема явно не е в кодирането, то е лесната част. Пуснах на мойта машинка 2 на степен 10 000 000 и го осметна за 57 и нещо секунди, като вероятно е ползвано само едното ядро. Цялото число като размер памет зае 3МВ. Това точно число, трябва да се представи така.

ххххх^nnnn + xxx^nnnnnn + nn^n + xxx^nn - 76

Например. Като запис е с нищожен размер.
По този начин може да се запише всичко. Ако са големи файлове, особено такива в които няма печатни символи, може би резулатта от кодирането ще е особено голямо число, което може и да не си представя. Но то също може да се представи по този начин.
Целия интернет, като обем информация, на теория може да се събере така на няколко реда или страница. Затова в предни постове споменах за Народната библиотека на две дискети. Не мога да пиша засега повече, че помагам на един приятел да се изнесе от апартамента.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 19, 2015, 10:53
То това ще се наложи, най-малкото защото изчислителните ни възможности не са безкрайни.

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

Допълнение заради предния пост на Гейт. В момента има достатъчно на брой открити прости числа, за да може да се кодира по описания вече начин една доста голяма част от каквото и да е. Трябва да имаме просто толкова на брой прости числа, колкото е дълъг файла. За да можем да заместим всяка позиция от файла с поредното просто число.

Макар че за изчислителните крайности май ще си прав. Трябва да се пробва просто.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 19, 2015, 11:18
То това ще се наложи, най-малкото защото изчислителните ни възможности не са безкрайни.

Аз също и не съм убеден че е добра стратегия да ходим в крайности с прекалено голям брой прости числа, които да повдигаме на степен (че и да стигнем до толкова големи, че да не са "открити" още). Определено ще се появят проблеми с това и те са свързани с начина по който кодираме "не вземай предвид тази степен". Дори само един бит да е достатъчен за целта (а аз не виждам как ще стане това лесно) - разхищенията въобще няма да са малки. Далеч по-изгодно става да описваш по-големи степени, отколкото да описваш много прости числа, чиято степен не вземаш предвид.
Не знам дали един бит ще е достатъчно място за такъв флаг.  И аз се притеснявам повече за разделителя между степените, защото него ще трябва да го ползваме независимо дали има степен или не.
А ако вземем идеята ти за многовариантността можем да подберем големи степени на големи числа, което си мисля че ще съкрати тоталната дължина на изходния текст

Правилно! Записването на почти което и да е число като база и степен, заема по-малко памет, отколкото записа на самото число. Това е така дори за сравнително малки числа, като например 36. Което се представя двоично със 100100. Ако е със база и степен 110 10. Бит по-малко. Това е и идеята по-общо.
Употребата на прости числа се налага от самосебе си, но аз не мога да го обясня, така, че да ми допадне обяснението на мен самия, въпреки, че разбираз причината. Нямам знанията и езика за това.
....
Хм, трябва много да внимаваш с честотния анализ и разбиването на двоично дърво. Такова прекодиране може да има доста негативен резултат ако го прилагаш върху данни с голяма ентропия. Може примерно да се наложи да ползваш 13-14 бита за да кодираш текст от 100 символа вместо 7 бита константен размер.


Титла: Re: Точни корени?
Публикувано от: Naka в Jun 19, 2015, 11:41
Целия интернет, като обем информация, на теория може да се събере така на няколко реда или страница. Затова в предни постове споменах за Народната библиотека на две дискети.

Излишъка от информация при обикновенният език е доста голям. За Аглийският език сметките бяха, че количеството информация е около 2 бита на буква.

Т.е. ако една буква се кодира в ASCII (127) това са 7бита.
максималната компресия която теоретично може да се постигне тогава ще бъде 7/2 = 3.5






Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 19, 2015, 11:52
Славянските езици в писмена форма на кирилица имат доста по-висока ентропия от английския, едно защото азбуката описва почти всеки звук и две защото по принцип не си позволяваме излишъци. Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.

Въпреки че тази цялата схема със степените ако се окаже работеща, не виждам какво общо има изобщо с ентропията на входните данни, то това е забавното в цялата работа.


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 19, 2015, 12:02
Работеща е и ентропията няма никакво значение.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 19, 2015, 12:04
Славянските езици в писмена форма на кирилица имат доста по-висока ентропия от английския, едно защото азбуката описва почти всеки звук и две защото по принцип не си позволяваме излишъци. Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.

Въпреки че тази цялата схема със степените ако се окаже работеща, не виждам какво общо има изобщо с ентропията на входните данни, то това е забавното в цялата работа.
Аз отворих сума за ентропията, защото по-горе 4096bits отвори дума за двоично дърво и честотен анализ на текста. Иначе да, наистина няма нищо общо с метода, който мислим :)
Целия интернет, като обем информация, на теория може да се събере така на няколко реда или страница. Затова в предни постове споменах за Народната библиотека на две дискети.

Излишъка от информация при обикновенният език е доста голям. За Аглийският език сметките бяха, че количеството информация е около 2 бита на буква.

Т.е. ако една буква се кодира в ASCII (127) това са 7бита.
максималната компресия която теоретично може да се постигне тогава ще бъде 7/2 = 3.5
по спомени е 5 и нещо бита на буква (английския), но това би имало значение само ако искаме предварително да обработим входящия текст за да намалим дължината му
Работеща е и ентропията няма никакво значение.
Работеща е ако можеш да се справиш с факторизация на големи числа (в обозримо време). Ама тогава ще можеш директно да разбиваш (примерно) RSA ключове :)


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 19, 2015, 12:25
Не съм споменал двоично дърво. Само показах, че представянето на число като база и степен, заема по-малко памет, от записа на самото число.
Кодирането и разкодирането работят. Пробвал съм го. Няма грешка и няма откъде да има. Прекалено прост е метода. Тези двете са лесните задачи. Представянето на резултата като база и степен или сбор на такива е трудната. Имам позната в БАН, може би ще може да ме свърже с някой математик. Ако алгоритмите, които съм насвалял нещо ме затруднат.


Титла: Re: Точни корени?
Публикувано от: Naka в Jun 19, 2015, 12:28
Въпрос:
Ако входните данни (текста,числото и т.н.) са бял шум - Абсолютно случайни битове и равномерно разпределени - ще може ли това да се смачка?

Според мен не.
И колко числа са именно такива - изглеждат като шум.
Сега тънкият момент е че ако успееш да видиш (или намериш) някъкъв патън, някакъв излишък от информация, някаква структура в този шум
то явно и той може да се смачка.

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



Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 19, 2015, 12:39
Не съм споменал двоично дърво. Само показах, че представянето на число като база и степен, заема по-малко памет, от записа на самото число.
...
Спомена по-горе. Примера с името на премиера е честотен анализ. И след това представянето на символите в зависимост от честотите е двоично дърво
Въпрос:
Ако входните данни (текста,числото и т.н.) са бял шум - Абсолютно случайни битове и равномерно разпределени - ще може ли това да се смачка?

Според мен не.
И колко числа са именно такива - изглеждат като шум.
Сега тънкият момент е че ако успееш да видиш (или намериш) някъкъв патън, някакъв излишък от информация, някаква структура в този шум
то явно и той може да се смачка.

например може да се успее да се разложи едно число на някакви коефиценти.....Ама да не се укаже че в общият случай - за случайно избрани числа, групичката от тези коефиценти ще се получи точно толкова дълга колкото и оригиналното число?
Според мен би трябвало да може да се компресира. Иначе въпроса с изходния текст и неговата дължина е резонен. И аз си мисля че ще има входни текстове, които няма да може да се представят с по-къс изходящ текст, но не мисля че това ще зависи от ентропията. Защото ние дискутираме просто различно представяне на входящия тескт. И факта че (понякога) изходния текст ще е по-къс от входния т.е. ще имаме форма на компресия не зависи (според мен) е само страничен ефект от метода на представянето
И ако се върнем на алегорията на gat3way за компресирането не трябва да забравяме че ние внасяме енергия в системата и по този начин променяме (в една или друга посока) ентропията на изследваната система :D


Титла: Re: Точни корени?
Публикувано от: 4096bits в Jun 19, 2015, 13:12
Ами начина на кодиране вече го знаете. Направете опит. :)
Резултатът в крайна сметка ще е един и същ. Голямо число. И тук вече се стига до представянето му.


Титла: Re: Точни корени?
Публикувано от: Naka в Jun 19, 2015, 13:23
Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.
Любимият ми френски спелинг е:

Jacqueline (10) vs Жаклин (6)


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 19, 2015, 13:26
Не сме като онзи свещеник в градската легенда за френския език, дето измислил писмената форма на езика под влиянието на тънкия момент че му плащали за написан символ.
Любимият ми френски спелинг е:

Jacqueline (10) vs Жаклин (6)
Има и с по-голям коефициент на "компресия" :P
renault - рено (7/4)
peugeot - пежо (7/4)


Титла: Re: Точни корени?
Публикувано от: sharena_sol в Jun 19, 2015, 15:37
Имам чувството, че сте на път да откриете алгоритъм за трансформация на число от десетична в двоична бройна система, но може би пропускам нещо. :)

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

//офф
Иначе Silicon Valley е много добър сериал. Halt and catch fire също не е лош.


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 19, 2015, 15:39
Имам чувството, че сте на път да откриете алгоритъм за трансформация на число от десетична в двоична бройна система, но може би пропускам нещо. :)

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


Титла: Re: Точни корени?
Публикувано от: sharena_sol в 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
т.е. всички степени са единици и също така простите числа не са задължително различни. 

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


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в 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 и тръгвам нагоре.


Титла: Re: Точни корени?
Публикувано от: gat3way в 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 и да се измисли някакъв на първо четене работещ, не казано много велик и оптимален алгоритъм за откриването на корените. В процесът според мен ще излязат наяве евентуалните теоретични драми.


Титла: Re: Точни корени?
Публикувано от: 4096bits в 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!" вместо да почне да дърпа!  >:(


Титла: Re: Точни корени?
Публикувано от: gat3way в Jun 20, 2015, 14:02
Вече показахме че 2 на някоя степен е лоша илюстрация и че RLE компресията ще даде същия, ако не по-добър резултат. Несъмнено е впечатляващо, докато не се замислиш какво биха направили традиционните алгоритми за компресия. Всъщност, вероятно хъфмановото кодиране ще даде по-лош резултат от записа със степента, но RLE кодирането ще даде малко по-добър.

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


Титла: Re: Точни корени?
Публикувано от: sharena_sol в Jun 20, 2015, 14:41
Мисля че това е правилния въпрос:

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

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

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

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

Не виждам причина това разсъждение да не работи и за 3-ична система. Или някаква по екзотична като с редица от прости числа. Освен ако нямаш някакви статистически наблюдения и знаше какви числа са по-вероятни да идват на входа за компресия, за да подбереш подходящ базис


Титла: Re: Точни корени?
Публикувано от: romeo_ninov в Jun 22, 2015, 09:20
Мисля че това е правилния въпрос:

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

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

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


Титла: Re: Точни корени?
Публикувано от: 4096bits в Feb 27, 2016, 10:59
Привет!
Нахвърляно е на грубо, но после ще чистя и оптимизирам, ако мога, но работи. Сега само трябва да измисля начин да разделя the_big_num на сбор от бази и степени и ще има работещо програмче. С ограниченото ми време, ще видим кога ще го стъкмя. Все пак остана последната стъпка само. :)