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

kierenski

  • Напреднали
  • *****
  • Публикации: 92
    • Профил
Re: Точни корени?
« Отговор #30 -: Jun 16, 2015, 09:03 »
Всичко много хубаво, а някой питал ли се е с каква точност трябва да са тези големи числа, защото едно коренуване на число с плаваща запетая с експонента става много бързо и слесно от колкото всеки друг тип.

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

4096bits

  • Напреднали
  • *****
  • Публикации: 6152
    • Профил
Re: Точни корени?
« Отговор #31 -: Jun 16, 2015, 10:56 »
Големите числа са  с L на края и се представят достатъчно точно. До последния знак. Точността трябва да е при извличането на nth корен. Ще дам на пауза за малко.
Активен

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

Odido

  • Напреднали
  • *****
  • Публикации: 627
  • Distribution: Arch Linux
  • Window Manager: Gnome
    • Профил
Re: Точни корени?
« Отговор #32 -: Jun 16, 2015, 13:24 »
докато четях разни java неща попаднах на това https://en.wikipedia.org/wiki/Fast_inverse_square_root ,което мисля донякъде е във връзка с темата :)
« Последна редакция: Jun 16, 2015, 13:28 от Odido »
Активен

"Congratulations, you broke the Internet
Look at what you did! Are you happy now?"

kierenski

  • Напреднали
  • *****
  • Публикации: 92
    • Профил
Re: Точни корени?
« Отговор #33 -: Jun 16, 2015, 18:54 »
Големите числа са  с L на края и се представят достатъчно точно. До последния знак. Точността трябва да е при извличането на nth корен. Ще дам на пауза за малко.

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

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

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

Acho

  • Напреднали
  • *****
  • Публикации: 5255
  • Distribution: Slackware, MikroTik - сървърно
  • Window Manager: console only
    • Профил
    • WWW
Re: Точни корени?
« Отговор #34 -: Jun 16, 2015, 19:03 »
И каква е целта с точни корени на тия грамаданските числа ?
Активен

CPU - Intel Quad-Core Q8400, 2.66 GHz; Fan - Intel Box; MB - Intel G41M-T2; RAM - DDR2-800, Kingston HyperX, 2X2048 MB; VC - onboard, Intel G41 Express Chipset; HDD - Toshiba, 500 GB, SATAII; SB - Realtek HD Audio; DVD-RW - TSSTcorp DVD-RW; LAN - Realtek PCI-E GBE Controller; PSU - Fortron 350 Watt.

4096bits

  • Напреднали
  • *****
  • Публикации: 6152
    • Профил
Re: Точни корени?
« Отговор #35 -: Jun 16, 2015, 20:01 »
Точността при извличането, пресмятането на базата и коренът трябва да е абсолютна. За да може след това остатъкът от голямото число да се подложи на същото, докато не остане нищо. Става въпрос за обработка на данни и не може да има допуск на грешка. Един знак да се сбърка и всичко отива на кино.

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

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

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #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, Силициевата Долина, аз не гледам много телевизия, но слушам защото жена ми го намира за забавен, та там ония идиоти май бяха открили големата компресия от нещо в нищо и се опитваха да си капитализират идеята, дочуваха се забавни реплики, ще взема да почна да го гледам ако още го дават.
« Последна редакция: Jun 17, 2015, 01:43 от gat3way »
Активен

"Knowledge is power" - France is Bacon

4096bits

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

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

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

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

gat3way

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

"Knowledge is power" - France is Bacon

4096bits

  • Напреднали
  • *****
  • Публикации: 6152
    • Профил
Re: Точни корени?
« Отговор #39 -: Jun 17, 2015, 08:58 »
О, аз не съм тръгнал да пиша нещо за четирите ядра, просто ми попадна, докато гледах, какви модулчета за python са налични из нета.
Активен

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

4096bits

  • Напреднали
  • *****
  • Публикации: 6152
    • Профил
Re: Точни корени?
« Отговор #40 -: Jun 17, 2015, 14:50 »
Не я зная тази теорема, какво казва, но това работи. Трудността идва от тези неизбежни изчисления, за които става въпрос. И това са изчисления с цели реални числа. Проблемът преди години беше, че машините не можеха да се справят. Сега е различно и като сравня възможностите на тогавашните процесорчета със сегашните, обема на оперативната памет... Дано да са достатъчни.
Като имам няколко минутки в повече ще ти пиша какъв е начина. Пробвал съм го с по-малки текстове например и работи.
Активен

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

romeo_ninov

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

0x2B|~0x2B

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #42 -: Jun 17, 2015, 15:59 »
Може да го опростим още, да търсим полином от вида Н = 2^x + y

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

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

"Knowledge is power" - France is Bacon

romeo_ninov

  • Напреднали
  • *****
  • Публикации: 2155
    • Профил
Re: Точни корени?
« Отговор #43 -: 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 компресия
Активен

0x2B|~0x2B

gat3way

  • Напреднали
  • *****
  • Публикации: 6050
  • Relentless troll
    • Профил
    • WWW
Re: Точни корени?
« Отговор #44 -: 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'
Активен

"Knowledge is power" - France is Bacon